Recherche textuelle

illus

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 :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 TD find_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

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 :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 Correction du TD find_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

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

gif naif

Animation de Nicolas Revéret

Recherche naïve

Algorithme de recherche naïve

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bxp_.P3(a;+g=/m4rse97Sf,dî 612:é5nuh050O0I0e0y0d0o0H0Q0g0o0y0H0H0C010e0d0s010406050H0Y0E0E0y0G0n040L0k0o0Y0@0k0X050D0~1012140|0s04051k1d1n0D1k0|0O0d0i0,0.0:0=0.0X0B0Y0y0B0I0l0s0n0e0Z1b0Q0Z0d0B0Z0o1P0Z0e0`050%0q0o0I1w0/0;011O1Q1S1Q0e1Y1!1W0e0G1l1K0,170H0s0y0X0=0T011$1y010M0)0I0X0y0E0I1W1{1}221(251!282a0`0a0Q0v0G0k0s0k0H0d1a0X0Q0#1_0G0G0I0g2v1d2d0X1l0D1K2I1=1@1?1X0O2f1z0d0X272s1W1t1v0-1%2S2U0X0k2Y1W0s2B1l2G2I2/0}1|2w2!232(0G110o1W0y1N2B0M0=030t0t0g2)0I1S2%0k0l0p0l0S0`0Q0S1d0y2:2?0{2=2e2^1(2`2|2~300I32013436383a2V3d0l20040Q0T3k3m1}3o2G2R013t0y2}1l2 0Z313335370#3D2(3F0w3h0w3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0F3h0F3-1e3/3p2@1x3s0k2{3T3v3X3x3Z3B3$3 3(3e0W3h0W452/3:2?3Q3@4f3{3A3#394l3c3e0R3h0R4r473;4a3?4c3u3V3w3y4z3~3b3F0K3h0K4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0j3h0j4Z2H4#492#4(4d3^3`4h3|4j4B4:0l0J3h0J4^3O4u3=4}4O3_4Q4i4A3%4D3f0p0`0S0p5a4`4v4)4 5h525j4C3F0S3g045B5r485t4~4x514S4/403f3H0S3K0D3l3.4!5G5d4w4+4y4.545N0S3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550S4F5D4H6b2;1q2-1d2Y2L0O1@2Q5d4A2X1u1l2,0I2.3n5~1l4A6G2e0d0O0=352G5A3v6N6P655z3e3g0Q2j0I6V6j5%1W5}6e1(0f0`0#0M6I5/4|0b3h6=6,3?0M0`2B0g0Z0I0G700I0t281u0I6`5c4%0_040x7a4$610`0e0I0r7k7g4{237d0N6I0Q6?2_0`0E0k0@6;6c2H7v1(7d0m0U6I0|7C6L2w6U016Q2?3F3H5g7O5#663e206!296$7P6W557T6+7b6@3h0Q7/7o3Q0H0O0`02030w0J0z7_7{7}7`7|7J7;7V0t6R3e5)7U6O7%6(4m0l3*7!2a6%5^8e897+7h237?7.7/2B0X0i0k0d1#0.0Q1S0H7k2x0I0+2T1t0g8F0Q0x0V0i270e0Y391!2a0X0e0Q0i6N0I0m8E0+0k0g0g0Y2A278J0+0#837L5G85870l5`8a8j5M8e428h7$7W6X8_6*5T6{018q3I7/8E8A2 700y0P2U0Q7y7A2x1}0+8z9f9h1#7k7m0I0u8;2;3P8@7R4n6T8b92554o908|5$8e683-97999b0Q7~7|9S807 9x6H9z9E869B0l6m8{8c8k5l4F9I9*8}9,959a7:970X0`8H0d8.7t7E0=0k0`0C9~977d0h0c9X3N8?9!8^4W4P858d5l4W9.9F5Nae3L9Q9 3R9`a47,23a104a37L7u970E0d0`5q7L7K9y4u9A1}3F4=af9!ahaM216#9J7X0laNao9baq6.040b1O1!at8o3sasazaqaw020o0e0zay2/aAau3s0q0`2i7;5d7d7f8=9^7j7l7nb4a{0=7Ga*7p1(aw0lbd4va}04a b9a+bb0`b3aIboar049k0d7Bbsbebp047Ha97D9Z6V8^57aOaU9357ak7(5NbJaY9Q9@babu0fbi5dawa^3na`btaCaEbE7M0QaK0X5A5nbK9/9K5l5paS7#bL6kb;bSbTa!0`a%26bY5:0`bXa.97a:a=0zc561bkbmbz3Qb2b0c6bv7zbxcl4|bcc9bV0k6^041}0Oce7w049tb8cib10`0hcqcB0dcJbf0`0AcM3?c7cQ017da8ctbtb!b#3Nb%bAbubwby9YbVa6cT9_04c8cF7c0`0c7IaG84ac9$5B9Db|5%6ZaTb?aVc~2I3lbTd9c$4vcScXc%aw0Ac!2Hdb5db)5Db+abbHc}7T2 ag9+5A7Zd3al8e5Q9=dadk4%a#cpdedcc:cAcNaxdi3Iaq0Xcg27cTckbnc%c/c)dU0`bDc`dWb-c|aL6Y89dtaPdvd,b`8id4935(dCdDaZb5049{9}d(bZ0`9we1cm0y0s0s27cze5crbqc.a-c=edbCdobG7%8^0S8`d.d0dA8 dybPesd`d9dQegb$a/cOdOdE4|dm3jd%cib.67c d@6k9HeuaQ6Y9M5,aHc+6Md*b/6Y9(eqeO5%9-eRd:3f9(5,ap97a#2B8Q0G1cdI5X9`0X8I8Fdo0D6K1o6s0D6u1d0e6wf72O2J0y1Z6F6t6C7K0#0%0)0H04.

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.

Évaluations restantes : 5/5

.128013]ik[v8o-)yqxb.+g=âmT4rs97f,d :F5hwtcl0p_P3(a;R/àeîS612énuA050C0X0J0S0c0L0x0D0K0L0S0x0x0r010J0c0N010406050x0)0t0t0S0w0k040Z0h0L0)0~0h0(0D020S0t0N0T0D0U0X180w0l0)0X0x050V1517191b130N04051G1z1J0V1G130C0c0f0?0^0`0|0^0(0q0)0S0q0X0i0N0k0J0H1i0D0H0c0q0H0L1/0H0J11050.0n0L0X1S0_0{011.1:1=1:0J1{1}1_0J0w1H1*0?1e0x0N0S0(0|0$011 1U010A0:0X0(1m0X1_2h2j2o212r1}2u0t2w040a0D0P0w0h0N0h0x0c1h1j0,2f0w0w0X0K2R1z2y0(1H0V1*2%2b2d2c1`0C2A1V0c0(2t2O1_1P1R0@202;2?0(0h2`1_0N2W1H2#2%37142i1j2|2p300w180L1_0S1-2W0A0|030O0O0K310X1=2 0h0i0#3y110D0#1z0S383b123a2z3d213f3h3j3l0X3n013p3r3t3v2@3y0i2m040D0$3E3G2j3I2#2:013N0S3i1H3k0H3m3o3q3s0,3X303Z0Q3B0Q3)2!3H133-3L0|3:3=053@3_3T3{3W2=3Y3z0v3B0v441A463J3c1T3M0h3g3;3P3^3R3`3V3}4j3 3z0G3B0G4p37473b3.4b4z4f3U3|3u4F3x3z0!3B0!4L4r484u4a4w3O3?3Q3S4T4i3w3Z0z3B0z4$3+4N3K4)3/4+4y4-4A4/4h4E4=3z0g3B0g4`2$4|4t2}4 4x4c4e4B4g4D4V570i0y3B0y5c3,4O495h4,4d4.4C4U3~4X3y0M110#0M5u5e4P505j5B5m5D4W3Z0#0#5I3D0V3F454{4s5N5i4R5l4:564k3y3#0#3(5Z3*5d5%5x4Q524S555o5.0#4104615L5_4~5{5A535C4;604m634o5?5#5^4(5g685k545n5E5U4I634K6h4q3+1K351z2`2*0C2d2/5x4U2_1Q1H340X363H6i1H4U6N2z0c0C0|3q2#5U3P6U6W6p5T3z5W0D2E0X6$5S5p5W2%5!6k2p0d110,0A6P665g0I3B6}6@3M0A112W0K0H0X0w780X0O2u1Q7d0n0h1e725w4~10040R7l4}6l110J0X0m7v7r5f2p7o0B6P0D6~3e110t0h0~6|6w2$7G217o0j0E6P137N6S1j6#016X3b3Z3#5A7Z5~6q3z2m6+2v6.6c4G3!1_6h730|703$0D7~7z3.0x0C1102030Q0y0T85878986887U807*0O6Y3z627)6V7!6%5p417/2F7;5-7?8l7_7m5g823B7~0D2W0(0f0h0c1~0)1j7i1e0%2t0D2=1P1v2j0J0D0^0D340%0x2t0K1~0h0)6+1,0,8f7W5%8h8j0i6e8m8u5 7?4m8s6-8o6/5.8^8y7s2p8B7}7~8Y780S0Y2?0D7J7L0D0C2j0=9a0H9c9e7v7x0X0o8/393-8=7$4H6!8n7+6(0i4I8~8`7,9E7^6?8z9683981k8d8c8b8a8e7W7V9v4O9x2j3Z4Z4-8h917?4Z9G907=5F9%3)8D7F7`3/7u2L0)0f0X7E7P0|0h110r9 9^0d0K110F3;8$9u6O9w9B8i9y0i4@9(ag9*5F4@9-9C5pak9=8Da09_040ca59M21a204a47W9@aB0|0t0c115K9W8gag8?59al9H9D59aq8p5.aSau7 a6110I1.1}aA953M11azaGawaD020L0J0TaF37aHa-4a0n112D805x7o7q8:9^0(7u7w7yb7aI017Ra,7AaC110ibh4Pb004b2bda~bf11b69Ybsb9049g0c7Mbwbi0|bga;9^0h7|2j0Cbm5xbJ11300JbN679`8*9}b37n117TaObr7YaQai5raT9.8v5F5raXan3Zb+a#9?a}bEax0dbT5gaDa{3Hb`3.aKaMad6xaf6$8?5J9AaU6:5Hb;9/5U5H6=9P9?aw6_04a)2sb~7H04b}bHbea?a^0Tct3MbobqbD3.b5bY7tbz7KbBcJ7B110jcCa1bK0(bMcxbxba9rcO7Q110ec#4aa/cS01aD0pc,bycwcGb4110bc,c0c13+c35`7IcMbCaebe7oc(b%4P11c=d3bs7o0bb#4MaPcaai5Vcdb-8{5Fdkchb.5U6;b^b_avb8d9c`a3c:dycXb{c.c,c563c77Oc98ocb7(3k9)ci6)7.6,ce607(5?dva$becpcNdDd8cvdzaEc|2$c~67cE2tc)bt7pd?bybAd2c8d4cQdf4rd79!0(5U8ldPamdR3y8rdUdm9I619KcmdZawby2bbW9~d(bOdAeo4~a7110u0w1wdJ7X8Rb)9#6)8^e7dV7?0#8}ecar6degdZd/cKa:a|a=eqeSdxayd+c/er5gdH5Ydge2eBe46)6s8_ed9D0#9FeKaYeHe-dYdwd#760-0)0w0(dB04el9|ene(390V6R6y6M6A6J1z0J6Dff2-2(0S1|fc0V6B1Fez5x2W0t0O0A0S0d7d0H621r1t1v1x0De06x1M3I1G0*1g2W0D0x1e1g0c1,1v0c0DfS1=8$fX9efQ0w0~1~8V0c0K0 8P9i1~8Y0A1i2YfT1j0q0w0s8(0D0S8+056R2W0Je 1jevexf93t3$0W8X3k259e5;9tfJ1O1Q3.1W1Y1!1$1(1*1,231;1?1^2dfl1}3.gv251@282G1`2-fggn4W0x6I2{4~5E326K6zf8c?675O5*6ob=0$3A3$5Y5!aOb8gY5|5+eL3 g$3#3%65g,5)g.g!cig$620D436vdgg_5z6n6bdrg$6e0D6gg*h3be6m5Q5,dn3!9J3$6uhd4%hfg-695}e@3xg$9%0D4#h2hpbxhrh65Rg}aj4^g^hqg`hsg/huhkaS0D5bhA5$h451hMg|h85q5shJhChLhEhi6qg$cc63aNhohUhKh5hhg:hv3y6;5Vh$b{hg6ahFhZ5;5I5=h:6jh=hWh)h^hkef63h1i65vh%h?i0h*5Th,6eeI5ufb2%6BfffhgK6G3tgOgTfcgV6OfadL7#9#h,dlibiIdqhjiIclco6`3Rd?7|7Fd75`750477797b797e0/9}0O8N0Ld?cIiWbUf3bbf6dbb{7Cf2d{i.d ey8;e*hkdOeAeGh_dT7:e/4=g=egawiUavi:8A9O9U9S88jji iFahiH0ie6j4j93Yg~2ne?g#jrjc9^979?8F8H8Jf#0Di,8P7YcV0c8U0(8W8Y8!8$0(f~8*8,2Si@5$e)dijqeEjtiK8@jxj8j+939LbsjD8D9m9o1~d{9i9kge0?9n9d1~9q7vgjf7i^j*jpe4g$e-eFjug;9JiMh+hl44jC9O9?jjko9Rjn9Zj1hwiJhOkukhim0i9;e`d!cYeXe!2pc0dGaL04aNk6d}6TkthHb,j+apjyhGatkCeP6^a(a*j!d.ejc+kGbj04a@a_d-3$ejd;f1jgcPd^k^a.i=c!k{bFcQd+blk+a b1d=k d@bvk7c cL7Li}047SkrkPj%ka0ia!kdj+aWkVhZa!kYcneWdac}eTaEkJc6b$cGe3hkb@lokwh!kyjah!cleOiQcqk$f2lxk(bI84cAc:k?lflakOh~d0lel8bGeVcycUcWl-kEk3k%frbZ04d6gWeQeYlTlfc_l4c-a3k:kZk|i|l+c%d_dCl|k_delib(lkiccke.j+cclLjv5GeNeOe{kElUk;lWlAm2c;l~m2e$mgk86Yh,dtlIjzdplriNh`mrdvlQd%l;l(d*m2c{lZl6k@mdc$k`m#c*ldmSlbl_lhlDk7lFh,j3dQi2j78tkeh_i3lOmskDb{cpg4g6c,et04g8l@9Xm:kQidmllJefmokfndlumtmUeRc2lzm5k)kFmT3.dFmCkKe%e1lEncj)m@mNeIj-m`mmj:9PlQn3f0n5a804aa0;n96}ga0,2%6Lisfe2(fh2(fjgGnZ0f3Ifo0-0/0;04.

Temps de recherches

⌛ Avant de commencer

Vous devez travailler sur Basthon

Télécharger dans le même dossier :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 TD temps_naif.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

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).

adn

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

gif naif inverse

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 :

Évaluations restantes : 5/5

.128013w]itkc[v8o-)Oyl0bxp_.P3(a;+g=/m4rse97Sf,d 612:5nuh050P0J0e0z0d0p0I0Q0g0p0z0I0I0D010e0d0t010406050I0X0F0F0z0H0o040M0k0p0X0?0k0W050E0}0 11130{0t04051j1c1m0E1j0{0P0d0i0+0-0/0;0-0W0C0X0z0C0J0l0t0o0e0Y1a0Q0Y0d0C0Y0p1O0Y0e0_050$0r0p0J1v0.0:011N1P1R1P0e1X1Z1V0e0H1k1J0+160I0t0z0W0;0T011#1x010N0(0J0W0z0F0J1V1`1|211%241Z27290_0a0Q0w0H0k0t0k0I0d190W0Q0!1^0H0H0J0g2u1c2c0W1k0E1J2H1;1?1=1W0P2e1y0d0W262r1V1s1u0,1$2R2T0W0k2X1V0t2A1k2F2H2.0|1{2v2Z222%0H100p1V0z1M2A0N0;030u0u0g2(0J1R2$0k0l0x0l0S0_0Q0S1c0z2/2=0`2;2d2@1%2_2{2}2 0J3101333537392U3c0l1 040Q0T3j3l1|3n2F2Q013s0z2|1k2~0Y303234360!3C2%3E0x3g0x3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0G3g0G3,1d3.3o2?1w3r0k2`3S3u3W3w3Y3A3#3~3%3d0V3g0V442.3/2=3P3?4e3`3z3!384k3b3d0R3g0R4q463:493=4b3t3U3v3x4y3}3a3E0L3g0L4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3d0j3g0j4Y2G4!482!4%4c3@3_4g3{4i4A4/0l0K3g0K4@3N4t3;4|4N3^4P4h4z3$4C3e0q0_0S0q594_4u4(4~5g515i4B3E0S3f045A591n2,1c2X2K0P1?2P5c4z2W1t1k2+0J2-3m3-3M054z5U2d0d0P0;342F5z3u5$5(525j5+0Q2i0J5.5x545B3,4J4{0f0_0!0N5W2G473P0b3g635!4`2^0N0_270d0N0u260i0J0H0I69655c0^040y6o5}2^0_0e0J0s6y6u5b4$6r0O690Q6p4$0W0_0F0k0?62455X6v1%6r0m0U690{6R643O5-015)2=3E3G5f6%4-533 3F205?5^4S6;6,0E3k0Q6~6I6T3=0_2S1s0g0J6n6!3H6J4{0k0_0D6H7b226r0h0c6Y6C5#5%6(0u5*3d3)4O6.5/5y7t6?285@7q5_6;7u3K6 706D4{6L040d7g71017d047f797J4#4{0F0d0_5p796Z2:6$7p6)1|3E417v7+7x54415=7B6^4.6;7/7H6 7h1%5 040b1N1Z7P7K6w7N877X227S020p0e0A7U2.7W6b3r0r0_2h7n8m0;6r6t798072046y6A0J8r3P6V8b8s7R0_0l8G4u8o048q8w7Q8u8D5c7M6N6P8T6E0_6W7m8Q4t7w7s0l4n7:7`6:4l8+7A298.5:4m1V6|3H7I7 7Q7M0f8L5c7S8j3m8l8M8p268Y4{8S8%8c3r6M6O6g9b7i8!9k1%7S8K9e8H7Z5n6H975N5B030Q0n2v1{0H0e2w1!0-0Q242v0#0Q1L0N0%9F1s7Z0W0X6l0Q917%8D8)6*4D5,7;7E8:4E7^8?7D6_9+8`6}8}6~8x01828425926K0_9Y8k9_8e0C8h953M9w4$9t047$a27Q0k67041|0P9~7L6x6z6B9r8E0_0h9n8y7O7Va30_0Bal89a15V8R0_7laxaf7ea72Ga9am048W9jaq6qasau3Qa0aV6r0c6X9Zaq9#7-3d4V8-9/7{8:4V9-7C6/8^0la+7~9@7I9_90aB9o7ea 8yaDa8ay049qae881%ab3ia$7)8(7;8*4;a,a?7y0l4;a;8@bmbja`8}9_82aRb99fb3b28I7TaL7aaJb7aVbcaY0_a#4r9!bh9$559(bq5456bpa-8/5k562H9?a{8~baav0W7577aV7S0vaV7M0z0t0t26akaS8Z6sb;73bK040m8$bf7o5.8*5obSbXa@c8bWbl5`5mb#8|9@a}b aIb)bCbEaN89awby8H7SaAcmbz01bJbeaEbgc6bQ5Ac9ce6;cGcd7=cJ5{8{a|7Q822A0e0X0H1bcx8H7M740d7678bN8w0E5Z5F5T5H5Q1c0e5Kc;2N2I0z1Yc.0E5I6Z0!0$0(0I04.

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.

Visualisation Boyer Moore Horspool par Nicolas Revéret

Boyer Moore Horspool

Faire plusieurs essais en modifiant le texte à parcourir et le motif à chercher.

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.

Dans l'exemple suivant :

étape 0

Le dictionnaire créé sera donc : dico = {"s": 0, "t": 1, "r": 2, "i": 3, "n": 4, "g": 5}

Comprendre les variables utilisées

Nous utilisons les mêmes variables i et k que dans l'algorithme de recherche naïve en partant à l'envers vu précédemment.

Au début, pour la recherche du motif "attg" dans le texte "atttcgattgc" nous avons la situation suivante :

variables

La recherche démarrera donc avec i = 0 et k = len(motif) - 1

La variable i sert à se déplacer vers la droite sur texte en partant du début de texte.
La variable k sert à se déplacer vers la gauche sur motif en partant de la fin de motif.

Lorsque l'on a positionné le motif sous le texte, i correspond donc à l'indice de la première lettre de texte sous laquelle se trouve la première lettre de motif

À vous de jouer

Dans la situation suivante :

variables

1. Donner le dictionnaire dico de prétraitement du motif

Solution

dico = {"g": 4, "a": 5, "t": 3}

Ne pas oublier que pour chaque caractère on donne le rang de la dernière occurence.

2. Dans le déroulement de l'algorithme, on est positionné sur les cases rouges. Donner i et k

Solution

i = 1 et k = 3

3. Compléter en utilisant les noms de variables i et k :

texte[...] = "c"
motif[...] = "t"

Solution

texte[i + k] = "c"
motif[k] = "t"

4. Quelle est la plus grande valeur que peut prendre i en fonction de len(texte) et len(motif) ?

Solution

len(texte) - len(motif)

Par exemple dans l'exemple ci-dessous la plus grande valeut possible de i vaut 9.
En effet : len(texte) - len(motif) = 13 - 4 = 9

variables

Comprendre les décalages à réaliser

1. Décalage pour un alignement simple

situation 4-1

Le dictionnaire de prétraitement du motif est le suivant : dico = {"c": 5, "g": 2, "a": 4}

Il faut aligner les deux caractères "g", et pour cela faire un décalage pour i de 4 - 2

On obtiendra donc :

situation 4-2

Par quel calcul trouve-t-on qu'il faut faire un décalage de 2 ? L'exprimer avec les noms de variables uilisés.

Astuce

Il faudra utiliser :

k qui donne l'indice de la première lettre de motif qui est différente en parcourant à l'envers (ici en rouge pour "a")
dico[...] qui donne l'indice de la lettre de motif qu'il faudra aligner (ici en jaune le "g" le plus à droite).

Solution

k - dico[text[i + k]] = 4 - 2 = 2

2. Autre situation de décalage

situation 5-1

Le dictionnaire de prétraitement du motif est le suivant : dico = {"a": 0, "t": 2, "g": 3}

En utilisant la formule trouvée à la question 1. déterminer le décalage à effectuer pour aligner les "t". Qu'en pensez-vous ?

Solution

i = 1 et k = 0
text[i + k] = "t"
dico["t"] = 2
k - dico[text[i + k]] = 0 - 2 = -2

On observe que le décalage obtenu serait négatif, et donc il faudrait revenir en arrière. Ce n'est évidemment pas correct.

Pour que le déplacement du motif se fasse vers la droite, il faut aligner une lettre du texte avec une du motif située à sa gauche, et non à sa droite comme c'était le cas dans cet exemple.

Dans ce cas-là, on appliquera tout simplement un décalage de 1 vers la droite. C'est le plus petit décalage que l'on puisse faire.

3. Cas où on ne peut pas réaliser d'alignement

situation 3-1

Le dictionnaire de prétraitement du motif est le suivant : dico = {"g": 4, "a": 5, "t": 3}

"c"n'est pas dans motif. On peut donc directement faire un assez grand saut : il suffit de positionner motif tout de suite après le caractère "c" du texte, donc ici à i = 5. Cela correspond à un décalage de 4, c'est à dire de k + 1

On obtiendra :

situation 3-2

Le principe de l'algorithme de Boyer Moore Horspool

Il faut avoir réalisé le dictionnaire de prétraitement du motif
On fait varier i de 0 jusqu'à la dernière valeur possible.
Pour chaque i, on observe les correspondances entre les lettres du texte et celles du motif, en partant de la fin.
Si toutes les lettres correspondent, on a trouvé un indice qui répondait au problème. On incrémente i de 1 pour faire une nouvelle recherche.
Sinon, on repère l'indice k de la lettre ne correspondant pas, et on réalise un décalage approprié pour i

À vous de jouer : Implémenter l'algorithme Boyer Moore Horspool

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013]ik[v8oB-)yqxb.+g=Dm}T4rsM97f,{d :5hwtcOl0p_PL3(a;j/eHèS612énu050G0#0M0X0c0P0z0H0N0P0X0z0z0s010M0c0R010406050z0.0u0u0X0y0l040(0h0P0.120h0-050!191b1d1f170R04051v1o1y0!1v170G0c0f0`0|0~100|0-0r0.0X0r0#0j0R0l0M0K1m0H0K0c0r0K0P1!0K0M15050=0o0P0#1H0}0 011Z1#1%1#0M1-1/1+0M0y1w1V0`1i0z0R0X0-100+011;1J010D0@0#0-0X0u0#1+26282d1?2g1/2j2l150a0H0T0y0h0R0h0z0c1l0-0H0:240y0y0#0N2G1o2o0-1w0!1V2T2022211,0G2q1K0c0-2i2D1+1E1G0{1=2%2)0-0h2-1+0R2M1w2R2T2}18272H2/2e2?0y1c0P1+0X1Y2M0D10030S0S0N2@0#1%2=0h0j0)0j0*150H0*1o0X2~3116302p331?3537393b0#3d013f3h3j3l2*3o0j2b040H0+3v3x283z2R2$013E0X381w3a0K3c3e3g3i0:3O2?3Q0V3s0V3W2Q3y173!3C103%3)053+3-3K3/3N2(3P3p0x3s0x3{1p3}3A321I3D0h363(3G3,3I3.3M3;4a3?3p0J3s0J4g2}3~313#424q463L3:3k4w3n3p0)3s0)4C4i3 4l414n3F3*3H3J4K493m3Q0C3s0C4T3Y4E3B4W3$4Y4p4!4r4$484v4)3p0g3s0g4.2S4:4k2:4?4o43454s474u4M4~0j0B3s0B533Z4F40584Z444#4t4L3=4O3q0Q150*0Q5l554G4@5a5s5d5u4N3Q0*3r045M5C4j5E594I5c4%4}4b3q3S0*3V0!3w3|4/5R5o4H4_4J4|5f5Y0*3^5O3`5%3X545+4=5-5r4`5t4(5=4d5O4f5`5)5|4V575 5b4{5e5v5L4z5O4B684h5*6b345F5U6f5J5g0*4Q5O4S6m4D5}6c6r5.5V5:6h3p0*4+5O4-6A4U5n5~6E605/6g5K6J505O526O6o6Q6D5T6F6t634x3q5i5O5k6#6a6%6q6)6T6G6V5g0+5y046~5Q6p4m6_6e625X6-0+5N7a726@745q765I6,5w0+3S7l7d4;6(7g5H5W5;795@0+5_5(6n6?7p6^7r617i787k650+677z6B734X757s6H6W3R6j0+6l7M6P7C7f4^6`6+7H3Q0+6x7+5l1z2{1o2-2W0G222#5o4L2,1F1w2`0#2|3y691w4L812p0c0G103g2R5L3G888a6|5=2c2u0#8g6u8i2T5(7O010d150:0D836C2e0L3s8x8r0-0D8u0c3i0S1/1|2M0z8C7e1014040W8O7!41150u0h0M8U562e8R0k0I83177A862H8f018b317*8e898;8h798j2k8l8`8n8|8p3T0H958y3D8u830H97100h150s9a9c018R0F0v8+8#0H8:8=283@8^8m7j9t0H8k9v7)3p5@3W95968r8t040D4n9h8D150c9M8P010h8A042(9Q8V3$0o150y281Q9o5o8R8T8-9i0-9!042t9)4=9+9?6c8X8Z9_8%150k8)9n9-3!9q0S8c4c9u909wa89y8~9A7u5w659E9Fak9.99a39R8R0e9}98048Y8!ao9Yaqas8W9VaA9j150b0b9X8$1?9e049g8-9b9NaC8-8,2 a48_9r0-3Q6j5ra5915w4zad2laf6I0ja!5`al9H9#0;0.0y1naOam040Ga2aU4Fa5a73oa97S5g4Qa*8 b65Y6x3WaT82aV8gb36La#aW8{5w4+b9a,7Tbk68a=a}3IaD9U9baxaJ418F040i0A0$aD9^bB4G150M0#0nbObJ150EaIbMau8Z0c8wbL9*9 8*aS9ob28?4 b5bn3Q50bqaa9B0j6Yaj9G9R0-8G3ibV5oaLaN2}aPb|b~0h8J0;200#8Nb#9@159,b09Yb}bX12b!cibCaE040ka bgb1bmb36/blbr5g5ib=bb6-cya:9Fa|2(1E0Nccc04=c2cO57aqaHaOc59Y0N5N030H0U3a1%0zbO2Icc9p0-cLc,0X0.0n0m0.3k0_0z1:200h0.0f2i0M0H1/0HavbZ0`0K0#0y0N0K0,ct3Y5Rb+9s6J6 czb?ag5L5ycDb/dk1+cHb{cj9OcR2ecQa{8r0u0c155Bb)bLdiaY6J5NdmcE5w5M8}a+dna-dR93a;9R9I0L1Z1/dzat9PdC9RaL020P0M0Yc33ycWcp9/159=cecScgaDckbObQ0#bScrd(9d150je69Zd`2ie4chcudxclbZe4a1dIco9pcwb,5Zb.a%5L2bdret6J3Sb`akd@bW0deadBc49.9:d{enb$8Sd 9{cmekeFe8eadE5z9a0Hbfdgbh8`b35?esab3q3^ewe*e(dXeBdwcpd!d$e3d+eheEe`cpd-0rd:d=3YeC5oeV04dHeH8r9T1528a~e}bWe1bRd|9~04arfjd)eS040qeacke|eLcf04cUf9d,9ff22Sf45~ePejfn8Q15fmfv9`04fuegcp8R0bb(fzcXcZ0H0w28d2c@02030V0B0Y0@0H0l0H3a3i2Lcc2Cc.28cMdf2Sdhepdj3qai3aa$e.4de-b@0*aidve;cIaQfPf39ieGd?a|gefDggeTfff5dF5Of{8.eobieq0*a!g2bmex3qa)9zdU7Tgxdu3wgbfE579IfHfVd^15gk3TgmaMfCgTfagnfM2ef63ufIcqfUd?eZf|e#aX5LbdgzcA5=b8gEdPg:gI94gKe=bWcK8HcNg(aL0peO040X0R0R2ifeg!1?bKheaBd*hhcqcsemfQgue$gwbkg=gF6vbpg_ds3qbtgJg~g 5,dygocP9ffshFgP3#aLfrhG57g$9ag,gtdK5Lb_htg`6XdSbahy0*b_gadY9Y9Ic_e_hk8Rg*5*dJf~dL6.e)g7cChxgB0*cGhBhC9igNcngiaQfhh/hoeMfLibfFaRhLc115hOihifgS9ifSeF9U9WhP34c7e4h=5|h@gvf 6~h{do3piCg6iE3Rdlh*hCgL2ei5eXgjfpe9itatcL0he4ide!c604i9iYh7hji7fAfqhJfOe4aGfp02f00YeUgqf8i+ay15ix949icY15c!0t0,0N3(1P1:2C2EeQhni!87h^7*dNhYhy7ah#g?79dNiLiMgci#i*gfgYaMi.jvgljxiki|gQi/iUe704iTilfNiWi(g(e0bPfih:fKi)fpjDjwi#in8rfSfy4iizhqiBezjkgB7ljnhu5Yj/e:jshD4=h-0^iajffRi~iQ8rj204c!0O2H2)0H2M0f0cd10H270_2if/2L0c0%2M0E0H1X0-f%f)0Y0X0ff_1:c@1:2Jg%6Bj)g/iF9Dj-e*7xj:hZ3R9Djrj^cJfpgWiNfojH9Siji_eWjeg-cviAh_7KiDa-k)iHk+g9i2g~i415h.iwk19Rk3k52H0D0?d20.2H0r9$c.0H0zc;0Mkn1Xc{ke0|cM0H0Z0.c)1:h90y0%0_0|d3ca2M2IbZ0D0,2M0-jSj(enhViFgyhpkL7WkKjla/k:jskQkVghjYehjAgXi,jXjBjZjWkYgrk!hUjhiFg;lFjlg^aej;79bdgak=042M0Ma^a`jLiu9Vc.h2cdkC2 0!857/807;7}1o0M7@m92Z2U0X1.m60!7=8,0:0=0@0z04.

Algorithme de Boyer-Moore-Horspool

def dico_lettres(mot):
    d = {}
    for i in range(len(mot)):
        d[mot[i]] = i
    return d

def BMH(texte, motif):
    dico = dico_lettres(motif)
    indices = []
    i = 0
    while i <= len(texte) - len(motif):
        k = len(motif) - 1
        while k >= 0 and texte[i + k] == motif[k]:  #(1)
            k = k - 1
        if k == -1:  #(2)
            indices.append(i)
            i = i + 1  #(3)
        else:
            if texte[i + k] in dico:  #(4)
                if  k - dico[texte[i + k]] > 0 :  #(5)
                    i = i + k - dico[texte[i + k]] 
                else:  #(6)
                    i = i + 1
            else:  
                i = i + k + 1  #(7)
    return indices

On remonte le motif à l'envers, tant qu'il y a correspondance et qu'on n'est pas arrivés au début du motif
Si on est arrivés à la valeur k = -1, c'est qu'on a parcouru tout le mot : on l'a donc trouvé.
On a trouvé le motif, mais attention, il ne faut pas trop se décaler sinon on pourrait rater d'autres occurences du motif (pensez à la recherche du motif «mama» dans le mot «mamamamama»). On se décale donc de 1.
On s'est arrêté avant la fin, sur une lettre présente dans le mot : il va falloir faire un décalage intelligent.
On décale juste de ce qu'il faut pour mettre en correspondance les lettres, en faisant attention à ne pas décaler d'un nombre négatif.
Si le décalage avait été négatif ou nul, on se décale juste de 1 vers la droite, on ne peut pas faire mieux.
La lettre n'est pas dans le motif : on se positionne juste après elle.

V. Crédits⚓︎

Gilles LASSUS, Nicolas REVERET, Jean-Louis THIROT, Marine MERA et Mireille COILHAC

Recherche textuelle

I. La méthode find de Python⚓︎

II. Recherche textuelle naïve⚓︎

III Le principe de l'algorithme Boyer Moore Horspool⚓︎

IV. Implémentation de l'algorithme Boyer Moore Horspool⚓︎

V. Crédits⚓︎

I. La méthode `find` de Python⚓︎