Recherche textuelle
Source : Gilles Lassus
I. La méthode find de Python
⌛ Avant de commencer
Vous devez travailler sur Basthon
Télécharger dans le même dossier :
Dans Basthon ouvrir find_sujet.ipynb, puis dans find_sujet.ipynb ouvrir pg798.txt (cliquer sur OK).
😀 La correction est arrivée ...
Télécharger dans le même dossier :
Dans Basthon ouvrir find_corr.ipynb, puis dans find_corr.ipynb ouvrir pg798.txt (cliquer sur OK).
II. Recherche textuelle naïve
Regarder les 5 premières minutes de la vidéo de l'introduction.
L'algorithme naïf et l'algorithme de Horspool en vidéo : Recherche textuelle
Illustration de l'algorithme
Auteur : Gilles Lassus
Algorithme de recherche naïve
Compléter ci-dessous :
.128013 0ldy1,4-]ké/weibmc_:35aPr+ 7=9o[f.gt28;6sSh)(pîunxv 050d0o0K0x0p0c0P0B0s0c0x0P0P0D010K0p0U010406050P0W0r0r0x0z0e040Q0F0c0W0@0F0X050m0~1012140|0U04051k1d1n0m1k0|0d0p0Z0,0.0:0=0R0p0J0R0c1B0R0K0`050%0q0c0o1w0/0;011A1C1E1C0K1K1M1I0K0z1l0K0R0,170P0U0x0X0=0L011O1y010H0)0o0X0x0r0o1I1+1-1=1Q1^1M1{1}0`0a0B0y0z0F0U0F0P0p1a0X0B0#1)0z0z0o0s2i1d200X1l0m1%2v1!1$1#1J0d220=1E0X1`2f1I1t1v0-1P2F0p2H0X0F2L1I0U2o1l2t2v2Z0}1,2j2N1?2S0z110c0`0B0f2s2%0{2$212)1Q2+2-2/0L2=1-2@2t2E012|0x2.040B0v302u0|332`0=36380B0h3c322%343i2/0w3m3e3o3g350F2,372/0O3t2^2(1x2{3y2}390C3D3f3G3h3I3A390M3M3v3O3x3z3j0E3U2_3W3q040f0b3#3F2O3X3J0f2;1e2?3u3$3.3(0f2 3?313^3-2*3Q380f3b3~3d3E3p430`0f3l473n3_423Y4c3s4f404a4j3)3C4f1o2X1d2L2y0d1$2D3w0s2T1~1l4w1m4u2#4s4C0#2Y3V3.0k0`0#0H3m0B493w0X0H0`2o0s0R0o0z4$0o0t1{1u0o3m4W3W0_040T4:3N3`0`0K0o0Y4}4_4O1?4?0g4U4;4{040r0F0@4T4s4`530`0S0u3,340n2/0B5o514h1Q0P0d0`02030v0E0N5w5y5A5x5z5k3w5t5n5o2o0X0Z0F0p1N0.0B1E0P4}2k0o0+2Q1t0s5X0B0T0l0Z1`0K0W0o0c1M1}0X0K0B0Z0p0#0S5W0+0F0s0s0W2n1`5#0+0#5G3W5I395o5W5S0x0,0R0x0V2H0B5a5c2k1-0+5R4$6h6j4}4 0o0I673.696b0B5B5z6D5D5C3t6B572*0`5Z0p64565f1Q0F0`0D6Q521Q4?0G0j6I6b6K2{6M6W5r0=6T046V4f4V6R0=0r0p0`3+4m6J6?014Q040n1A1M6+416)040p75346.020c0K0N6:2Z6=6X3h0q0`255q760=4?4^5e7k354|4~507u6,014?0S7a3w6.0i7F3%7m047o7A7q7C0`7t2#6~0X0`6l0p5d7T7v7D5j6|6B6%7U0`0k7J3.6.7h2?7j7B6^6`6$7)7?7P70721_7.6L047-6;6(6-5v7e0N812{7L7N7!7B7s7p3p7W5b7Y8i3w7D8b6-5m041-0d8q7w046u7z8f7P6Z8n3%6*7O7b0`0A8E58848B344?6#856~7:7;317|8j598l7Z2?867Q040G8L828N8$6~8Q7%2Z067{7{8%7V838w6.0A8V2u8X3w7^3)7`7)8%708m8S7v8`8-8W8%8U8w0X8d1`8+6Y7R9l3h8k5c9o8(5i958@918F780X5!5X9s6.6x8H4X0`0x0U0U1`8v9G4=9n9O58799R5g047E7(8^7+788|8J8 398%933=8=8?7*7v702o5,0z1c9a7B8`6N6P4m1d4L0o2v2Wa14v1u4x2y2B2w0x1La40m4w0|ae0$0(0*04.
Version booléenne de l'algorithme de recherche naïve
Re-écrire l'algorithme précédent en s'arrêtant dès qu'une occurrence de motif est trouvée dans texte.
La fonction renverra uniquement un booléen.
.128013 0ldTy1,4-]ké/weibmc_:35aPrq+ 7F=9o[f.gt28;6sSh)(pîunxv 050d0p0N0y0q0c0S0D0t0c0y0S0S0G010N0q0X010406050S0Z0s0s0y0A0f040T0I0c0Z0`0I0!050n111315170 0X04051n1g1q0n1n0 0d0q0$0/0;0?0^0U0q0M0U0c1E0U0N0}050*0r0c0p1z0=0@011D1F1H1F0N1N1P1L0N0A1o0N0U0/1a0S0X0y0!0^0O011R1B010K0,0p0!0y0s0p1L1.1:1^1T1{1P1~200}0a0D0z0A0I0X0I0S0q1d0!0D0(1,0A0A0p0t2l1g230!1o0n1*2y1%1)1(1M0d250^1H0!1}2i1L1w1y0:1S2I0q2K0!0I2O1L0X2r1o2w2y2$101/2m2Q1_2V0A140c0}0D0g2v2*0~2)242,1T2.2:2=0O2^1:2`2w2H012 0y2;040D0w332x0 362}0^393b0D0i3f352*373l2=0x3p3h3r3j380I2/3a2=0R3w2{2+1A2~3B303c0E3G3i3J3k3L3D3c0P3P3y3R3A3C3m0H3X2|3Z3t040g0b3(3I2R3!3M0g2@1h2_3x3)3;3+0g323_343{3:2-3T3b0g3e413g3H3s460}0g3o4a3q3|453#4f3v4i434d4m3,3F4i1r2!1g2O2B0d1)2G3z0t2W211o4z1p4x2(4v4F0(2#3Y3;0l0}0(0K3p0D4c3z0!0K0}2r0t0U0p0A4)0p0u1~1x4.0r0I1a3p4Z3Z0|040W4_3Q3}0}0N0p0#534 4R1_4|0h4X4`51040s0I0`4W4v50590}0V0v3/370o2=0D5u574k1T0S0d0}02030w0H0Q5C5E5G5D5F5q3z5z5t5u2r0!0$0I0q1Q0Z2m4?1a0m1}0D2T1w0B0Z1:0N0D0;0D2Z0m0S1}0t1Q0I0Z0D2V2m0(5M3Z5O3c5u5.0y0/0U0y0Y2K0D5g5i2n1:0.5/4)696b53550p0L603;62640D5H5F6v5J5I3w6t5d2-522f0Z0$0p5c5l1T0I0}0G6J581T0l0t0}0F3a5?6A646C2~0}0q6P5x0^6M046O4i4Y6K0^0s0q0}3.4p6B6:014T040o1D1P6(446#046%6.6!6*5B0c0N0Q6-2$6/6Q3k0r0}285w730^4|4~5k7h385254567r6)014|0V72376+0j7C4!7j047l7x7n7z0}7q2(6{0!0}6d0q5j7Q7s7A7G3Z0I5s041:0d7!3;7$0}2V0N7+6D041%5`6H7m374|5p6_6t6Z7R0}0l7;6L6N846;6?046^2$067 807s6}6 1|877t0483776{6+027b0Q8k0!7I7K7X7y7p7`4!7T5h7V8B4{5n8k7-7(0!7*8o7s7S7?7v6I7L7{0}0J8G5e767f78016+0C8u828Y5m040k8J6N7e2_7g7y8Q7U7W2_8$4|8X8U8C8m8,1T4|0k7}8c8e8e8$8Q8n8#8p868O8^8+9h7M8(8k6=4f6Y9a6{6}8F9k3s9j9e7s6+0G8=348@7M8v7k1}937o7O9J8l8`9M7A973`997 9b6E7^8T9y7y9A8k6S0}0e0A0Z9Y9S999V758:6,8*9:9v3z9m9^3Z9o3,3w8d8f7y6}2r0N0Z0A1f9{5e7@6G9,421g4O0p2y2Zah4y1x4A2B2E2z0y1Oak0n4z0 au0)0+0-04.
Temps de recherches
⌛ Avant de commencer
Vous devez travailler sur Basthon
Télécharger dans le même dossier :
Dans Basthon ouvrir temps_naif.ipynb, puis dans temps_naif.ipynb ouvrir pg798.txt (cliquer sur OK).
III Le principe de l'algorithme Boyer Moore Horspool
En bio-informatique
Les algorithmes de recherche textuelle sont aussi notamment utilisés en bio-informatique. C’est dans ce domaine que l’on va prendre les exemples du TP qui suivra.
- Comme son nom l'indique, la bio-informatique est issue de la rencontre de l'informatique et de la biologie : la récolte des données en biologie a connu une très forte augmentation ces 30 dernières années. Pour analyser cette grande quantité de données de manière efficace, les scientifiques ont de plus en plus recourt au traitement automatique de l'information, c'est-à-dire à l'informatique.
- Analyse de l'ADN : Comme vous le savez déjà, l'information génétique présente dans nos cellules est portée par les molécules d'ADN. Les molécules d'ADN sont, entre autres, composées de bases azotées ayant pour noms : Adénine (représenté par un A), Thymine (représenté par un T), Guanine (représenté par un G) et Cytosine (représenté par un C).
Auteur du schéma : Victoria Denys/CEA sur https://www.cea.fr/comprendre/Pages/sante-sciences-du-vivant/l-ADN-dechiffrer-pour-mieux-comprendre-le-vivant.aspx?Type=Chapitre&numero=1
Algorithme de recherche naïve en partant à l'envers
Auteur : Gilles Lassus
Re-écrire l'algorithme de recherche naïve, mais en démarrant de la fin du motif et non du début. Certes, c'est pour l'instant
très artificiel, mais cela va nous aider 😊.
Compléter ci-dessous :
.128013 0ldy1,4-]k/weibmc_:35aPr+ 7=9o[f.gt28;6sSh)(punxv 050d0n0J0w0o0c0O0A0r0c0w0O0O0C010J0o0T010406050O0U0q0q0w0y0e040P0E0c0U0=0E0V050l0|0~10120`0T04051i1b1l0l1i0`0d0o0X0*0,0.0:0Q0o0I0Q0c1z0Q0J0^050#0p0c0n1u0-0/011y1A1C1A0J1I1K1G0J0y1j0J0Q0*150O0T0w0V0:0K011M1w010G0%0n0V0w0q0n1G1)1+1:1O1?1K1_1{0^0a0A0x0y0E0T0E0O0o180V0A0Z1%0y0y0n0r2g1b1~0V1j0l1#2t1Y1!1Z1H0d200:1C0V1^2d1G1r1t0+1N2D0o2F0V0E2J1G0T2m1j2r2t2X0{1*2h2L1;2Q0y0 0c0^0A0f2q2#0_2!1 2%1O2)2+2-0K2:1+2=2r2C012`0w2,040A0u2~2s0`312^0:34360A0h3a302#323g2-0v3k3c3m3e330E2*352-0N3r2?2$1v2_3w2{370B3B3d3E3f3G3y370L3K3t3M3v3x3h0D3S2@3U3o040f0b3Z3D2M3V3H0f2/1c2;1m2V1b2J2w0d1!2B3u0r2R1|1j3_1k3@2Z3;2 053 0Z2W3T3,0k0^0Z0G3k0A3C3n0G0^1_0o0G0s1^0X0n0y0O3k4l3u0@040S4y3L3,0V0^0J0n0W4J4E4d1;4B0g4j4z3#0^0q0E0=4i472s4T3,4B0R0t3r0A4,4k4F2(0^2O1r0r0n4x4!374$1;0E0^0C4S4/1O4B0F0j4+4-4|2_4;514O1O4~04504`4.5d3f0p0^234N3!4%0^4D4`593f4V4X4q5p3+4P0^0R5c5q4}0^0i5F5B1O0q0o0^3:2X064-5j5G1O4f040m1y1K5K3n5b5i5v015f020c0J0M5h2X5U5L5l5n1^5A324B5t2Z525w044J4L0n5{4A5D5$3u5f5J5)60015N5P663U4B4*4`5S5T586e4H040k693U5f5;2;5?326g043)6m6o6p5k015X5Z1@6u4G0^6t6d6H5,5.0M6M2(5m045o5u6e5}6i6N044W4Y6%5C045E6Q5V0:0E0m0^1+0d6V5a6)5y4Z5 6H546,2_6X6Z706;016$6!6H6r6*5z7b784(6{6=5I7j6f5O3%7m6b7m6r6P775@790^566:7w6w6x2 6z3u6r634M7g7w727K5%040o7q7l7A7O7u3=6#7y6l5R6F6F5*7t7R5g7s6O7)0z7m6B5Q2;6n7$6e5X7f5=7%7,7T6a4 7D2s7F3#755`7N674C73617e6 7W715D7Z7=7#6o7|7P0V4?4^8a5+0^0H8q6r0w0T0T1^6`876j5s8u5(7{6e7r7~845_1a8B5r898N4:6}6+8Q53688J3,5f7.8X1;7:8q7i6E7#8l7Q8#5e4 7+7P7-7/7o7;2 7?834e0^2m0J0U0y8M8G7c4;8n0o4@4_5R1b4a0n2t2U9e3^1s3`2w2z2u0w1J9h0l3_0`9r0!0$0(04.
Le principe
L'idée est d'améliorer le code précédent (celui où l'on parcourt le motif à l'envers) en sautant directement au prochain endroit
potentiellement valide.
Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent
dans le motif):
Si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu.
On se décale donc juste assez pour dépasser X, donc de la longueur du motif cherché.
Si X est dans le motif (sauf à la dernière place du motif!), on va regarder la place de la dernière occurence de X dans le motif.
On se décale afin de faire coïncider le X du motif et le X du texte.
IV. Implémentation de l'algorithme Boyer Moore Horspool
utiliser un prétraitement du motif pour déterminer les décalages
On va d'abord coder une fonction dico_lettres qui renvoie un dictionnaire associant à chaque lettre de mot (paramètre d'entrée)
son dernier rang dans la variable mot. On exclut la dernière lettre, qui poserait un problème lors du décalage (on décalerait de 0...)
Dans l'exemple suivant :
Etape 0 :
Le dictionnaire créé sera donc : dico = {"s": 0, "t": 1, "r": 2, "i": 3, "n": 4}
Etape 1 :
i prend la valeur 5 c'est à dire len(motif) - 1"d" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire de len(motif)
Etape 2 :
i prend la valeur 5 + 6 c'est à dire de i + decalagedico["n"] = 4, on va faire un décalage de 5 - 4, c'est à dire de len(motif) - 1 - dico["n"]
Etape 3 :
i prend la valeur 11 + 1 c'est à dire de i + decalage- On a concordance pour la lettre "g", on vérifie la concordance des lettres en partant vers la gauche,
donc pour les indices i - k, k augmentant de 1 à chaque nouvelle comparaison. On observe qu'il n'y a plus
concordance lorsque i - k = 8 .
"p" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire len(motif) à partir de l'indice
où l'on se trouve.
i prendra la valeur 8 + 6 = 14, c'est à dire que i prend la valeur i - k + len(motif)
Etape 4 :
i prend la valeur 14dico["s"] = 0, on va faire un décalage de 5 - 0 = 5, c'est à dire len(motif) - 1 - dico["s"]
A vous de jouer : Implémenter l'algorithme Boyer Moore Horspool
Compléter ci-dessous :
.128013 yB1-{]/wi_}P+r 79HfIg;2àh)O(pnv0ld,4kéebmc:35a=o[.8t6sSèuxM 050I0N0!0U0j0H0$0p0Q0H0U0$0$0V010!0j0D010406050$0)0P0P0U0o0b040%0W0H0)0 0W0E050h16181a1c140D04051s1l1v0h1s140I0j0F0@0_0{0}0z0j0v0z0H1J0z0!12050/0O0H0N1E0`0|011I1K1M1K0!1S1U1Q0!0o1t0!0z0@1f0$0D0U0E0}0x011W1G010t0;0N0E0U0P0N1Q1?1^1}1Y201U2325120a0p0m0o0W0D0W0$0j1i0E0p0-1;0o0o0N0Q2q1l280E1t0h1/2D1,1.1-1R0I2a0}1M0E222n1Q1B1D0^1X2N0j2P0E0W2T1Q0D2w1t2B2D2+151@2r2V1~2!0o190H120p0d2A2/132.292;1Y2?2^2`0x2}1^2 2B2M01340U2_040p0S382C143b320}3e3g0p0K3k3a2/3c3q2`0T3u3m3w3o3d0W2@3f2`0#3B302:1F333G353h0q3L3n3O3p3Q3I3h0Z3U3D3W3F3H3r0r3$313(3y040d0G3-3N2W3)3R0d2|1m2~3C3.3_3:0d373~39403^2=3Y3g0d3j463l3M3x4b120d3t4f3v414a3*4k3A4n484i4r3;3K4u4h3E433T4A3V424j3;3#4F3%4H4x0d3,4L4p3P4x0x3?4R494T3R0x3}2+4v4C4I0x454%4B3/4*4e4-4G4q4!4m4=4M4@3Z0x4t4`4S3X4U4z504Y524!4E554w4!4K2-1y2)1l2T2G0I1.2L3E0Q2#261t5i1u5g5e2-5o0-2*4{1Y0L120-0t3u0p4.420t5D0j5o0k1U1(2w0$3u5I1~11040C5T4?33120P0W0!5Z5A0}5W0A0R3B0p5;5H5!3p5D5G5U1Y0W120V5`5@015W0f0l5:5=5{0}5C040t3G605+3d120j6e51010W0i6h1k4n5?6f0E0O120o1^0v0N5*6k5W5Y4n683d6u042d6A5662126D2-610E5$5(6K3c5-6U3E5}040e6X3(0P0j4k6$3_5-5/4u5=6:6r6k6R040I6+5V120X6`5#045%5)6E615W6}736s6h6~5,120g0g6j6L6Z5 6q6F6@6i6/67616a2w0!0)0o6p2+6=6L6@6_4u4(3(6a5E7f3x5K040c0+0s7a6M5X7N6@0!0N0*7S7N5W0J7G4C6S0 5F776B125.665;7k5L5o7Z3(7h7;427/0W5O0.1,0N5S7(6L6C7Q7#0j7%6P6f6W7n7-6Q6o1B0Q7~7@1~7?7j746|7e8a7x3x798k6f8j7w7k6H6J806V6N83705(857W7*8h5|126#8s6k6(6*8M6L0Q0d12030p0j0p0$0N0o0!0p0y0p1@0o5o7t0j0o0p7S7U1V0U0F2x2s7~8Y0U1h0$0Y0p0B2r8*8$0I0)0p0O0W1h2s9771850Y3B066:6F6a0i1I1U8I5^047m8v616Z020H0!0w7i9t6s8x228G7P8z7!048;7V9H3(899B6k6Z8L9P6L8O3;9F6.4%6;7o78040L9p6l5~9)9V4W9Z9!8p3E9l9n6z8Q8q9%9)9v9x0w9)6t128y877)9Ga47y84862~6F9O2~9;7=6n041^7A9T9`9eaa39ac6|7Q9D7vab8la6av9$an9F0A9|8K9,6)9W9_6YaEaI3/129(9M6,7caD040V9Aae7.9J7T9La78A0476a#9I9saW9uaKal9IaOa)9N7c9Yae9i9:9j8c9{aL3_8ua,9$a;b29Q120naF8P9/9!9k6hao2Caf7^a~a/7=5~aV39bh2=at9F6Oay6?a9aBa^bo8b6f8S8U912r0U8:2k0)0F0M0p1U0paA8oa{aX2Y8e8gaP8i129gbW6 0U0D0D22akbu818Bb!9qa+bo6F9Ra0brb.7Obtapa}bPa=aQ04aCa bX04b8c31Y9V4$b+a$c2bba{bp6 0-0Q3f0U6yaSbnbg6Fc97,cfbScna08rbkb0b7cw6^2xckcm6qcg0}bC048V920@0z8!0QcO0p0)bF1h2wbO8E0t8%2s2k2p9^cea|6f6a0N0=c(cb3E5Wby3lcf9#6k6a8Fc79q9Kc/b|88arb_7laS9Sb5a8bjc:a?048ncy8iah2YcB8e0W9Xcsc^bAbvcCcj0_cFdf8JaTb@a29Eb_82d4bwdB8Hc}9*6!b9aHdv0}b?dH7z5MdldFa%8Cc 9Fa(dbbib:cpa-dJdPaN9F7ddndocudHb1b;6Q6H190*bs8Cd#3hb=a.d89`b4bzd~c5djcDdtd02Caq047Yd)9raSc6dM01crdTcdaecH01cJ8V0u0H0p2P0p0t8}8$1@0?2w8^0E8.0p220p1a0o0j0(2wd-bc7p12c-8ZdmbQd.a}cicEe9d}d%coe#9Cdzaud1a5b{eab}cYaBeOcta}d|eod;d$9$e_e4d7d=b3ege6dscle!5;06a`dp6L7q0.7te+e|dqbT5MbV4-0h5x0N2D2(fp5h1C5j2G2J2E0U1Tfs0h5i14fC0.0:0=04.
V. Crédits
Gilles LASSUS, Jean-Louis THIROT, Marine MERA et Mireille COILHAC
# Tests(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)