Recherche textuelle

illus

Source : Gilles Lassus

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

Auteurs : Marine Méra - Modification par François Hallé, Jean-Louis Thirot et Mireille Coilhac

À vous de jouer 1 : trouver une lettre dans un mot

Écrire une fonction trouve_lettre qui prend en paramètres un caractère cet une chaîne de caractères texte et qui renvoie la **première** occurrence decdanstexte`.

La fonction devra renvoyer None si c est absent de texte.

Contraintes

On n'utilisera pas ni la fonction index, ni la fonction find.

Exemples

>>> trouve_lettre('j', 'bonjour')
3
>>> trouve_lettre('j', 'alphabet')
None

Évaluations restantes : 5/5

.128013So4l57s_xN6:w/phPn[1gk2cC=iè)-tfàear39,8(d v]é;umbyq050Q0I0F0J0B0e0h0R0y0e0J0h0h0A010F0B0p010406050h0W0X0X0J0K0Z040b0c0e0W0^0c0s050o0 1113150}0p04051l1e1o0o1l0}0Q0B0S0-0/0;0?0/0s0v0W0J0v0I0E0p0Z0F0q1c0R0q0B0v0q0e1Q0q0F0{050(0Y0e0I1x0:0=011P1R1T1R0F1Z1#1X0F0K1m1L0-180h0p0J0s0?0x011%1z010G0*0I0s0J0X0I1X1|1~231)261#292b0{0a0R0r0K0c0p0c0h0B1b0s0R0$1`0K0K0I0y2w1e2e0s1m0o1L2J1?1^1@1Y0Q2g1A0B0s282t1X1u1w0.1(2T2V0s0c2Z1X0p2C1m2H2J2:0~1}2x2#242)0K120e1X0J1O2C0G0?030i0i0y2*0I1T2(0c0E0u3e0{0u1e0J2;2@0|2?2f2_1)2{2}2 310I33013537393b2W3e0E21040x3j3l1~3n2H2S013s0J2~1m300q323436380$3C2)3E0L0{0L3J2G3m0}3N3q0?3Q3S053U3W3y3Y3B2U3D3f0d0{0d3+1f3-3o2^1y3r0c2|3R3u3V3w3X3A3!3}3$3f0f0{0f432:3.2@3O3=4d3_3z3Z3a4j3d3f0l0{0l4p453/483;4a3t3T3v3x4x3|3c3E0g0{0g4G3L4r3p4J3P4L4c4N4e4P3{4i4S3f0O0{0O4X2I4Z472$4$4b3?3^4f3`4h4z4.0E0M0{0M4?2J2-0I2J2Z2M0Q1^2R3:014y2Y1v1m5a2/3m3,3L054y5p2f0B0Q0?362H3E0u3u5x5z513#4B3g0R2k0I5G4y5I5C1X0o3k463O0w0{0$0G5r2I5V5i0n0{0R5#5v4_2`0G0{1?0c0W0S0I0i1#1/2C5,5%4#0`040P5~4I4`0s0{0y644s5i610N5,5+652`5;0I0j0F0I6a4!4`610D0m5,0}445s3N5F015A2@3E3G3@0R6z4,523~3F225M5O4R6K6E5T5-3O5)040R6X5+6w5$6h1)0h0Q0{020!0W0c0F0V6+6-6/6;6.0V2C0s0S0c0B1$0e02030L0M0V2U1u0y1$2z0/0R5a0X0B0C2C0R0c0y0y0W2B28782y1$0y2y1~0,6m6l6n6!3n7z5V6H0i5B3f3(4N7D5P4A3%6M2a5N6A5H7L7G5S5U6$0?6(5*6Y5?0R6`6|6~0R0k1c1$1}0K1`6{282w0R2u2)0s6@6?6,6^7{0V6u6o2x7D7F0E407I5y7Q7K53405L7O6O4-6K873J6v2=6y896B1~3E4m888g6J4k0E4m8e2b8u5Q4l7U6W6Y5 4`5X040G4a6f8H6i040B8N7W010c6V2U8S6b4#0s0Y0{0K1~1G823O61637B8T8#0{2j8+6c0{8.8m8Z666j7x8@600{0D6s818/4s846C4C5E8o7R534D8z7P6I8C0E4D2J3k6Y9o6g8|248J0B5!7z9q6p8P7w6m906q0{0t9C8P8R969y1)610T8Y9K0?0c0{0A0A9O5.3r689G9L0{6t7z8l5q8n5G854U8t8a6P8w4U9g8B7S0E9-3J9p9|9x9W0?8J2C0F7m1d9w8O9X8Q958{5w9c854:9.9i9^4:9?9/8h8waf9{8G8T0y5D04037@0B7i2x0I0h0F0R7o4a6 0H0R0m0-71730VaAaC6,aL741N7`7274301}7v2q5@0U0R1#0-130J2E7g7y4q8+988q3f55ag9d6K55akah53a@ap6Xa7a08%0%a49V5W0y0{7+2Vb75ias0{av0z0%6ma%1Q2V5LaRaNaB7c0:5L0U780;0)5}9%5~0o5u1p2.1e5d1e0F5fbI2P2K0J1!5bbG5m6v0$0(0*0h04.

Plus difficile

Le problème est plus difficile quand il faut chercher non plus un seul caractère mais un mot dans le texte.

on ne parlera pas de 'mot' mais de motif, ce qui est plus général.
quand on trouve le motif cherché à un endroit du texte, on dira qu'il s'agit d'une occurrence du motif dans le texte : cela désignera l'indice i tel que texte[i:i+1] == motif

Rappel : la notation chaine[i:j] désigne la tranche de la chaîne comprise entre i inclus et j exclu. On parle de slicing.

image bo

Exécuter le code ci-dessous

La fonction find de Python

Python dispose d'une méthode find attachée aux objets chaînes de caractère qui permet justement de trouver un motif dans la chaîne

Pour corser un peu l'affaire, on peut prendre un texte très long. Typiquement, on peut chercher un mot ou une phrase dans tout le texte d’un roman.

Le site http://www.gutenberg.org/browse/languages/fr propose les grands classiques de la littérature qui sont tombés dans le domaine public. On peut par exemple y trouver le texte intégral du roman Le rouge et le noir de Stendhal dans l’encodage UTF-8 : http://www.gutenberg.org/ebooks/798.txt.utf-8

À vous de jouer 2

Nous allons ouvrir ce fichier texte avec Python et charger l'intégralité du fichier texte dans une variable nommée stendhal. Exécuter ci-dessous

On peut chercher ensuite si le motif "Julien trembla" apparaît quelque part dans le roman.

La méthode find renvoie un entier correspondant à l'indice de la première occurrence du motif dans le texte.
La méthode find renvoie -1 si le motif cherché n'apparaît pas dans le texte. Par exemple stendhal.find('Joséphine') renvoie −1 car le prénom Joséphine n’apparaît jamais dans le roman.

Exécuter ci-dessous

À vous de jouer 3

Une variante de la méthode find a deux arguments. Le deuxième est un entier égal à l'indice de départ de la recherche.

Question 1

En utilisant ce deuxième argument, trouvez s'il y a une occurrence suivante du motif : 'Julien trembla'

Solution

print(stendhal.find('Julien trembla', 162927))

Question 2

Trouver les deux premières occurrences du mot : 'Julien' dans le roman

Solution

occur_1 = stendhal.find('Julien')
occur_2 = stendhal.find('Julien', occur_1 + 1)
print("1ere occurence : ", occur_1)
print("2eme occurence : ", occur_2)

À vous de jouer 4

Question 1

La fonction nb_occurrences prend en paramètres deux chaines de caractères texte et motif.
Elle renvoie le nombre de fois où motif apparaît dans texte.
Compléter ci-dessous.

Évaluations restantes : 5/5

.128013TSo4l57s_x60:.w/+phPnùI1gk2c=iè)-tfîearà39,8(d vé;u!mbyq050U0L0I0M0E0f0i0V0C0f0M0i0i0D010I0E0s010406050i0Z0#0#0M0N0%040c0d0f0Z0|0d0v050q13151719110s04051p1i1s0q1p110U0E0W0;0?0^0`0?0v0z0Z0M0z0L0H0s0%0I0t1g0V0t0E0z0t0f1U0t0I0 050,0$0f0L1B0@0_011T1V1X1V0I1%1)1#0I0N1q1P0;1c0i0s0M0v0`0B011+1D010J0.0L0v0M0#0L1#2022271-2a1)2d2f0 0a0V0u0N0d0s0d0i0E1f0v0V0*1~0N0N0L0C2A1i2i0v1q0q1P2N1`1|1{1$0U2k1E0E0v2c2x1#1y1A0=1,2X2Z0v0d2%1#0s2G1q2L2N2@12212B2)282-0N160f1#0M1S2G0J0`030j0j0C2.0L1X2,0d0H0e0H0y0 0V0y1i0M2^2{102`2j2}1-2 3133350L3701393b3d3f2!3i0H25040V0B3p3r223t2L2W013y0M321q340t36383a3c0*3I2-3K0P3m0P3Q2K3s113U3w0`3X3Z053#3%3E3)3H2Y3J3j0e3m0e3=1j3@3u2|1C3x0d303Y3A3$3C3(3G3+443-3j0g3m0g4a2@3^2{3V3|4k403F3*3e4q3h3j0l3m0l4w4c3_4f3{4h3z3!3B3D4E433g3K0h3m0h4N3S4y3v4Q3W4S4j4U4l4W424p4Z3j0S3m0S4(2M4*4e2*4-4i3}3 4m414o4G4^0H0Q3m0Q4}3T4z3`524T3~4V4n4F3,4I3k0m0 0y0m5f4 4A4.545m575o4H3K0y3l045G5f1t2=1i2%2Q0U1|2V5i4F2$1z1q2;0L2?3s3?3S054F5!2j0E0U0`3a2L5F3A5,5.585p5;0V2o0L5@5D5a5H3=4P510A0 0*0J5$2M4d3V0p3m695*502~0J0 0v0$0j0d0C0C0Z2F2c0C0L0i6f6b5i0~040T6x632~0 0I0L0k6H6D5h4,6A0R6f0V6y4,0v0 0#0d0|684b5%6E1-6A0G0n6f116!6a3U5?015/2{3K3M5l6:4?59453L265|5~4Y6}6^0q3q6S516d3N0V7b6L4+510i0U0 020(0Z6X0Y7j7l0I7n7k7m2G0v0W0d0E1*1)5{0d0#0$2G2C1*0J7x0:0d0w0V6W6Y0V0M0s210N0M0K0I2C220:6H6J1*7o7m7(7q7*0Y6Q6,2_6/5-6;0j5:3j3/4U6`5^5E7_6 2e5}7?5 6}7`3Q7/5#7;5@7^3i5=7=6{5_46802f714@6}472N3q7b7c6$3{6k6m6o6q7u6u6Q77280d0 0D8B8t010#0E0 5v6-3N8C1-0C5H030V0x0v2z0E3Y0E0i0M2A2C0Z7B7D7F0U02030P0Q0Y8x6r6t6v6+7d2B7|8c4t7{8f7}5a4t5{818l6|4r0H903Q8r6R8I6U042Y1y6u6n6p6r8z0L8H6M518E048G8O9f9s288K8M9r7e288S0 8U9j0E6u0V0O0V7T0|0N8)7k3e0V1R3C0J2H0I0Z7z342G0C0t0L0N9)7H9j8{8O6b8~6?4J8e988h0H4K968k83729a4K8p7a8s9z3x0 2G130f0,0I9D6h1-9u9w2@9y9Ea8047#6K9;8I9u0o8|4A0 2a0v0Uav6z0 6Cara78u047O0E6Zak8Q0`6Oafaw9iaz9K0L9m8y9paB6N0 0G9:7:4z9?224!9_a08m9a4#9~828g7~0H4#a49eaN0165040p1T1)aQ5i9haa0Zac8%b44,9u0!aj3salag0`9u0HaZ519B5Ibm286A6*9xa}9G048U0b227X7k8/8;0Y0.0V6I8#6H0V0Z2Z7Q1e7F8@aY8O886#a)928c4`919`a^4`a=b#5abZ9d9e8ra}9h6laW8^0v8Abuas8Fbb51b:8w9nbSaMb`040rb|9A8LbpbTava*0v3K5cb!a.995q5cb(ch9{cfb,b-bhaR9J9lbRc1bga}aic6anb7b9aeb_aG019uc5cFam0`bo3ocKbi01bw8U1R0i1*0U0X0s0?9L7R0N0F0:0fbD8=bR8_0V1`0d0Z0W0X9qcaaF5+bX9@5ra-a@605scld06}5u1#75a5b-b/a96vb8adcAbjb{cPaRapc^a(cLcH0 auc`cQ9hayaAds3V6AaEdndt6V6XaKdg01aPdjb50 ctaVcv8_bq6%a#dGcS7Bc=3e7A9(9*9,9*a%89bW8bc}5Gc 93d53ld3d.9ad,a{b.8Ia 2G9!0N1hdJ6T8vb=cw4)6x0q5)5L5Z5N5W1i0I5Qed2T2O0M1(ea0q5O6,0*0,0.0i04.

Question 2

Reprendre la fonction de la question précédente avec une fonction récursive.

Évaluations restantes : 5/5

.128013So4l5s_x60:.w/+phPn1gk2c=i)-tfear3,(d vumby050L0F0D0G0A0e0g0M0y0e0G0g0g0z010D0A0q010406050g0O0P0P0G0H0R040b0c0e0O0,0c0t050o0?0^0`0|0;0q04051c151f0o1c0;0L0A0N0!0$0(0*0$0t0v0O0G0v0F0C0q0R0D0r130M0r0A0v0r0e1H0r0D0/050V0Q0e0F1o0%0)011G1I1K1I0D1Q1S1O0D0H1d1C0!0 0g0q0G0t0*0x011U1q010E0X0F0t0G0P0F1O1:1=1`1W1}1S20220/0a0M0s0H0c0q0c0g0A120t0M0T1.0H0H0F0y2n15250t1d0o1C2A1*1,1+1P0L271r0A0t1 2k1O1l1n0#1V2K2M0t0c2Q1O0q2t1d2y2A2%0=1;2o2S1{2W0H0_0e1O0G1F2t0E0*030h0h0y2X0F1K2V0c0C0f0C0u0/0u150G2(2+0:2*262-1W2/2;2?2^0F2`012|2~30322N350C1^040x3b3d1=3f2y2J013k0G2=1d2@0r2_2{2}2 0T3u2W3w0I0/0I3B2x3e0;3F3i0*3I3K053M3O3q3Q3t2L3v360d0/0d3Z163#3g2,1p3j0c2:3J3m3N3o3P3s3S3=3U360f0/0f3{2%3$2+3G3*453.3r3R314b34360j0/0j4h3e1g2#152Q2D0L1,2I3(014q2P1m1d2!0F2$4z3|3D054q4Q260A0L0*2}2y3w383L0M4Y4!494r334%1_2b0F4,4q3T4t371O0o3c3~3G0w0/0T0E3!4T3%400*0n0/0M552z4 4I0t0E0/0t0Q0h0c0y0y0O2s1 0y0F0g0h2t0y5d4W3 2T010.040K5z5f583H0/0D0F0i5M5H575C5E0J5z5c5R2.0/0P0c0,544S5e5X1W5T5V5I5C0t0/0A5Q4k4I0c0/0z5?3h5J0P0A0/0k5|5B1{5E0B0l5z0;5(5A4*4Z014#2+3w3y3,6d4@3;4/361^0M4=6m4a6o3x4|3c0M6z5W5@5J5:040A5m5o5q5s0F5-5*0*5_045{6b6B5}5/5L5N5P6b5.1{6P0m634l0/1}0t0L6(4I5E5G6Z6N5K045!5$6.5J5,6=6C6V6F6{5S0/0B696(4+6f0h4$363W4)783:6u3?0C3W6r214?794^4s3V6x046A6T641W516F5%2%7v6)6F6H5p2t0t5t6M6 6#5`6R7B6!1W6P0C721{5 397K6U650/686b6a2)3F7f7a6h3@3m7+7p6v3^7l226t4.7i3^2A6y7u6A7Q0*7y2t0D5q146S81017W04627%776e6g1=3w4e7e8g4-4_8j4;7m7_8o4d7s7u897y310g6L886?5E7$4i8f4,7b0C4v8l8s7q4u8q7^7o6n7i8L3B7 806?830U867Y7w0*8b3a8C7L7R0/0p8%7D5k7F5q7H5t5v5x7U5+0/6;7)8-3)6W5O8B917Z8~045U8,98936^5#0A7A4z8D0/9b7P6?6E6G5n7G6K8;5^8/9u5~60048+978(5D74766Z0o4V4A4P4C4M150D4F9O2G2B0G1R9L0o4D6a0T0V0X0g04.

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

.128013So4l57s_x60:.w/+phPn[1gk2c=i)-tfîear39,8(d v]é;umby050Q0I0F0J0C0e0h0R0A0e0J0h0h0B010F0C0r010406050h0W0X0X0J0K0Z040b0c0e0W0@0c0u050p0~1012140|0r04051k1d1n0p1k0|0Q0C0S0,0.0:0=0.0u0x0W0J0x0I0E0r0Z0F0s1b0R0s0C0x0s0e1P0s0F0`050%0Y0e0I1w0/0;011O1Q1S1Q0F1Y1!1W0F0K1l1K0,170h0r0J0u0=0z011$1y010G0)0I0u0J0X0I1W1{1}221(251!282a0`0a0R0t0K0c0r0c0h0C1a0u0R0#1_0K0K0I0A2v1d2d0u1l0p1K2I1=1@1?1X0Q2f1z0C0u272s1W1t1v0-1%2S2U0u0c2Y1W0r2B1l2G2I2/0}1|2w2!232(0K110e1W0J1N2B0G0=030i0i0A2)0I1S2%0c0E0k0E0w0`0R0w1d0J2:2?0{2=2e2^1(2`2|2~300I32013436383a2V3d0E20040R0z3k3m1}3o2G2R013t0J2}1l2 0s313335370#3D2(3F0L3h0L3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0d3h0d3-1e3/3p2@1x3s0c2{3T3v3X3x3Z3B3$3 3(3e0f3h0f452/3:2?3Q3@4f3{3A3#394l3c3e0k3h0k4r473;4a3?4c3u3V3w3y4z3~3b3F0g3h0g4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0O3h0O4Z2H4#492#4(4d3^3`4h3|4j4B4:0E0M3h0M4^3O4u3=4}4O3_4Q4i4A3%4D3f0l0`0w0l5a4`4v4)4 5h525j4C3F0w3g045B5r485t4~4x514S4/403f3H0w3K0p3l3.4!5G5d4w4+4y4.545N0w3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550w4F5D4H6b2;1q2-1d2Y2L0Q1@2Q5d4A2X1u1l2,0I2.3n5~1l4A6G2e0C0Q0=352G5A3v6N6P655z3e3g0R2j0I6V6j5%1W5}6e1(0y0`0#0G6I5/4|0o3h6=6,3?0G0`2B0A0s0I0K700I0i281u0I6`5c4%0_040P7a4$610`0F0I0j7k7g4{237d0N6I0R6?2_0`0X0c0@6;6c2H7v1(7d0D0m6I0|7C6L2w6U016Q2?3F3H5g7O5#663e206!296$7P6W557T6+7b6@3h0R7/7o3Q0h0Q0`02030L0M0V7_7{7}7`7|7J7;7V0i6R3e5)7U6O7%6(4m0E3*7!2a6%5^8e897+7h237?7.7/2B0u0S0c0C1#0.0R1S0h7k2x0I0+2T1t0A8F0R0P0U0S270F0W391!2a0u0F0R0S6N0I0D8E0+0c0A0A0W2A278J0+0#837L5G85870E5`8a8j5M8e428h7$7W6X8_6*5T6{018q3I7/8E8A2 700J0H2U0R7y7A2x1}0+8z9f9h1#7k7m0I0n8;2;3P8@7R4n6T8b92554o908|5$8e683-97999b0R7~7|9S807 9x6H9z9E869B3d9D9J7X9%9I8c8k5l6m3L9Q7E3?0`8H0C8.7t9?010c0`0B9|977d0v0T9X3N8?9!8^4W4P858d5l4W9,9F5Nac9;9b9}0u9^a27,239 04a17L7u970X0C0`5q7L7K9y4u9A1}3F4=ad9!afaK216#9)93aLam7:976.040o1O1!ar8o3saqax9}au020e0F0Vaw2/ayas3s0Y0`2i7;5d7d7f8=97ap049t7nb1a^0=7Ga%7p1(au0Ebb4va`04a|b7a(b90`b0aGbm3R7x7z0C7Bbqbcbn047Ha77D9Z6V8^57aMaS5557ai7(5NbHaV9Qa@brb30ybg5daua=3nbSby01aAaCbC7M0RaI0u5A5nbI9-8}5l5paQ7#bJ5%b:bQ9=aX0`a!26bW5:0`bVa+97a-a/0Vc461bibkbx3Qa a}c5049kbvck4|bac8b89~6^041}0Qcd7wb47lb6cha~0`0vcpcA0CcIbd0`0qcL9@04c7cE7c0`a6csbrbYbZ3Nb#4vbt7AcP01a4c*bUc*7d0T7IaE84aa9$5B9(b=9Kb@6ZaRc|9*c`2I3lbRd6c$5Xc6czcM040qc!2Hd84%b(5Db*a9bFc_7T2 ae9.5A7Zd0aj8e5Q959ad69}aYcocXb$c.dF3QcZdb3?cf27c/boc-c(dEcTcq0`bBc?bl7Nc^aJ6Y89dqaNdsd%b_8id1935(dzd7bRao9^0u8I8Fc*au9wdZc%cw0r0r27cye0cF7edR04cKe7cUbAdlbE7%8^0w8`d)b{dx8 dvbNeod=d7d^ebdL9~cNdf3I9}dj3jdYchb-67c{dwb@9HeqaO6Y9M5,aF9YaHd#b.6Y9:emd/6k4FbMeO3f9:5,b ctaY2B8Q0K1cdId9ebd`9`d|eF6H0p6K1o6s0p6u1d0F6wf42O2J0J1Z6F6t6C7K0#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

.128013So4l7s_60:w+pPnA[1ci)-e3,(v];uâyqTRx./hgk2=Fàtfîra98d ém5b050#0x0U0Y0u0e0g0$0t0e0Y0g0g0R010U0u0n010406050g0E0(0(0Y0X0G040b0c0e0E0~0c0p0$020Y0(0n0D0$0J0x180X0H0E0x0g050M1517191b130n04051G1z1J0M1G130#0u0B0?0^0`0|0^0p0O0E0Y0O0x0w0n0G0U0N1i0$0N0u0O0N0e1/0N0U11050.0*0e0x1S0_0{011.1:1=1:0U1{1}1_0U0X1H1*0?1e0g0n0Y0p0|0Q011 1U010V0:0x0p1m0x1_2h2j2o212r1}2u0(2w040a0$0o0X0c0n0c0g0u1h1j0,2f0X0X0x0t2R1z2y0p1H0M1*2%2b2d2c1`0#2A1V0u0p2t2O1_1P1R0@202;2?0p0c2`1_0n2W1H2#2%37142i1j2|2p300X180e1_0Y1-2W0V0|030h0h0t310x1=2 0c0w0f0w0s110$0s1z0Y383b123a2z3d213f3h3j3l0x3n013p3r3t3v2@3y0w2m040$0Q3F3H2j3J2#2:013O0Y3i1H3k0N3m3o3q3s0,3Y303!0y3C0y3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0d3C0d451A473K3c1T3N0c3g3=3Q3_3S3{3W3~4k403z0)3C0)4q37483b3/4c4A4g3V3}3u4G3x3z0i3C0i4M4s494v4b4x3P3@3R3T4U4j3w3!0f3C0f4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0!3C0!4{2$4}4u2}504y4d4f4C4h4E4W580w0Z3C0Z5d3-4P4a5i4-4e4/4D4V3 4Y3A0j110s0j5v5f4Q515k5C5n5E4X3!0s3B045W5M4t5O5j4S5m4;574l3A3$0s3)0M3G464|5#5y4R534T565p5,0s425Y445;3+5e5^4 5`5B545D4=5 4n5Y4p645?664)5h695l555o5F5V4J5Y4L6i4r3,1K351z2`2*0#2d2/5y4V2_1Q1H340x363I6j1H4V6O2z0u0#0|3q2#5V3Q6V6X6q5U3z3B0$2E0x6%5T5q5X456l2p0P110,0V6Q675h0l3C6}6@3N0V112W0t0N0x0X780x0h2u1Q7d0*0c1e725x4 10040A7l4~6m110U0x0K7v7r5g2p7o0z6Q0$6~3e110(0c0~6|6x2$7G217o0v0k6Q137N6T1j6$016Y3b3!3$5B7Z5}6r3z2m6,2v6/6d4H3#1_6i730|703%0$7~7z3/0g0#1102030y0Z0D85878986887U807*0h6Z3z617)6W7!6(5q427/2F7;5+7?8l7_7m5h823C7~0$2W0p0B0c0u1~0E1j7i1e0%2t0$2=1P1v2j0U0$0^0$340%0g2t0t1~0c0E6,1,0,8f7W5#8h8j0w6f8m8u5~7?4n8s6.8o6:5,8^8y7s2p8B7}7~8Y780Y0W2?0$7J7L0$0#2j0=9a0N9c9e7v7x0x0L8/393.8=7$4I6#8n7+6)0w4J8~8`7,9E7^5=7`01978D1k8d8c8b8a8e7W7V9v4P9x2j3!4!4.8h917?4!9G907=5G9%3*9P7P4b7u2L0E0B0x7E9@010c110R9~9M0P0t110S3=8$9u6P9w9B8i9y3y9A9H9D4^9-9C5q4^2%3G9?9M0p110ua48z2pa104a37W7F9M0(0u115L9W8gaf8?5a9(af9*5G5aan8p5,aP9=8D9 6_040l1.1}ay953Nawa+7A21aB020e0U0DaD37aFaz3N0*112D805y7o7q8:au7u7w7yb6a}0|7Ra/3/aB0wbf5_a 04b1bba,bd11b59Ybp3:7I7K0u7Mbta:bq040vbj4 0c7|2j0#bF5hbH11300UbL7H042b8*9|b27n117TaLbo7YaNah5saQak5q5saVaS3!b*aZ9P7 b7040PbRa;a2b|0|aHaJac6yae6%8?5Kaj9.8v5Gc8b/9/5V5Iar98b@a#11a(2sb bvb`cpa=a@0Dcp0pblbnbA3/b4bX7t049gbycD7B11bEaE9 bN04bJcwb89rcI7Q110rcU9^04axcM9MaB0mcRcrb$cB110Ccsa2a`3Ia|buavcFbxbzadbc017ocXc,5_11b{d2bY040Cb!4NaMc6ah5Wc9ao5 6+6-b,di9Kcjb@a!b_d5a{cNb~c$c~c_dsc?du04c)dwbuc15Yc37Oc58oc77(3k9)cf6*7.dkca8{cc7(64dpb^c~a$cHdEbBcqdz3,c@d)aB0Rc=d,9 cxb02tcYc brd`c_cGc|c4c~7Rda4sc,9!0p5V8ldOaRdQ3A8rdTdh7?60dndZckb_bU9{9}d(bgdvdta5a7040I0X1wdI7X8Rb(9#6*8^ebdlei8}egaWeKekdZd?a.er5yd/c*c#euc~c(cpdG3Eb#cAe76sdgeNcc9FeMb:6*6tb?d-3/a$2W0U0E0X0pc*eobWe(6P0M6S6z6N6B6K1z0U6Efb2-2(0Y1|f80M6C1FeC5y2W0(0h0V0Y0P7d0N611r1t1v1x0$e46y1M3J1G0q1g2W0$0g1e1g0u1,1v0u0$fO1=8$fT9efM0X0~1~8V0u0t0 8P9i1~8Y0V1i2YfP1j0O0X0F8(0$0Y8+056Se{e}1jeyeAf53t3%0T8X3k259e5/9tfF1O1Q3/1W1Y1!1$1(1*1,231;1?1^2dfh1}3/gq251@282G1`2-fcgi4X0g6J2{4 5F326L6A39d66m5P5(6pb:0!3A3Ce%5=aLaugT5{5)eh3xgX3$3(5!g%5%g)gVcfgX610$63g#dbg;5A6o6ccb0wgX6f0$6hg}4(dxg(6a5|e-h49J3%6vh95@g 52hdg*hfgX9%0$4$6wg~hbg=hog@h3gXaq0$4`hvhac^hch15Sg^h45bg:hxh05R5*dVhgb*0$5uhGhlhQhnhKhT6rgXc85YaKhk6kh#5Q6bhLhB3A5X5ZhZh/hIhyh%g+hg5/5J5:h.5wh}hRh=h(5Uh*6160hPi7h$hSi0h*6f0sh8652%6M2%6CfbfdgF6H3tgJgOf8gQ39f6dK7#9#h*e,gWgYceh@6=94d)a$6{d`7|7FgR3e750477797b797e0/9|0h8N0ed`cCiVa-bTb9eqcAb3117DeT68bw7Li-cKfD66e6eEe8g-iIhMdS7:dUh)7@ci9 iTa!i/0|979U9S88jleB8;j4hgeaeDeJg,0wefjaijjxdn9 9O8D8F8H8JfX0$i+8P7Y0p8T1Z0p8W8Y8!8$0pf`8*8,2Si?e5e)jrh5j7h@eLjzhq8@jC9MjE993k9b9d1~d 9i9kg90?9nj_0$9q7vgedbj3ddiGhh8_jbib9JiLhUgXe?iO8183cjjlkn9RjpiEagk99;eIkc4?hr2ne:hM9;dYdqdxeSeYbueVi{5hdGaKk6j%k8j5aib+kw3ZhCkzj-iJaqe@cla%a)j#d=b_eXdAc%84cud;2$e^bkd^e jid{7pd}cSbai@d7cLkHd.11bikK3ecyd_k`i.l0cEd i bDj13Jk7dL7$gXaYkvjAaUkAh@aYkDdpeRc+l3esaCe#aI04kNj$c}6Uj(5rj*kglKkfjcb=lvemd#cmk(c*d+k=dBa?a^cwl9k_ldcJk|k`d~c{lgl2k-eZbIjOf0i=lgd1l)i:k,k*eZ11dDlzd3lylHd)7oc/l7b}aCk;3%lxlflbcWk}m5e1bum8li9Xm6jullk9h+kbjAcdlslMmulRellxlXmek.lBmacZmEk?bGm1lC5Jkq9ZlJdfkTmwdjkYhMmTe@atlTc!e0lYdrc:mcl$k^lgbsmqm4mgl|bC7SmQlIkQi1dNmrmwj98tkU40h*dXaselkEbue`0-g1cpa611g3k)j2kPmskRejmUj.ejlOkdnnm!n9d)c_l~m)m0mHm3i|c!m+m2l;dFlDe%kOmqe*iklLjcimkXn2mw93n7d!na76nce~neewa90;niljgQf61M6Afkfa2(fd2(ffgBir6K7V0,0.0:0g04.

Temps de recherches par différentes méthodes

Compléter ci-dessous la fonction naive_find qui code la fonction find de Python de façon naïve

Évaluations restantes : 5/5

.128013So4l57Rs_x60:.w/+phPn[1gk2c=iè)-tfàearî39,8(d v]é;umby050T0K0H0L0D0e0i0U0B0e0L0i0i0C010H0D0s010406050i0Z0!0!0L0M0$040b0c0e0Z0`0c0v050q111315170 0s04051n1g1q0q1n0 0T0D0V0/0;0?0^0;0v0y0Z0L0y0K0G0s0$0H0t1e0U0t0D0y0t0e1S0t0H0}050*0#0e0K1z0=0@011R1T1V1T0H1#1%1Z0H0M1o1N0/1a0i0s0L0v0^0A011)1B010I0,0K0v0L0!0K1Z1~20251+281%2b2d0}0a0U0u0M0c0s0c0i0D1d0v0U0(1|0M0M0K0B2y1g2g0v1o0q1N2L1^1`1_1!0T2i1C0D0v2a2v1Z1w1y0:1*2V2X0v0c2#1Z0s2E1o2J2L2=101 2z2%262+0M140e1Z0L1Q2E0I0^030j0j0B2,0K1V2*0c0G0P0G0x0}0U0x1g0L2?2_0~2^2h2{1+2}2 31330K350137393b3d2Y3g0G23040U0A3n3p203r2J2U013w0L301o320t3436383a0(3G2+3I0O3k0O3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0d3k0d3:1h3=3s2`1A3v0c2~3W3y3!3A3$3E3)423+3h0f3k0f482=3?2_3T3`4i3~3D3(3c4o3f3h0l3k0l4u4a3@4d3_4f3x3Y3z3B4C413e3I0g3k0g4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0R3k0R4$2K4(4c2(4+4g3{3}4k3 4m4E4?3g3k0P4{3R4x3^504R3|4T4l4D3*4G3i0m0}0x0m5c4}4y4,525j555l4F3I0x3j045D5t4b5v514A544V4=433i3K0x3N0q3o3;4%5I5f4z4.4B4;575P0x3-5F3/5U3P2K1r2:1g2#2O0T1`2T5f4D2!1x1o2/0K2;3q5W5:4D632h0D0T0^382J5C3y6a6c565m6f0U2m0K6i5A585E3:4N4 0z0}0(0I65684~260p3k6A5Y4*0v0I0}2b1x0K0j280v0T6G6u260|040S6T5e6I0}0H0K0k6%6Z4)4 6W0Q6A0U6H4 0v0}0!0c0`6z493Q6=6V0}0F0n6A0 6}5:3S6h016d2_3I3K5i795%6k3h236m2c6o7a6j5B7j1Z5.6 1+6E3L0U7y6+6C1+0i0T0}02030O0P0Y7G7I7K7H7J747A0U7g0j6e3h5+7f6b7o6q5P3-7l2d6p4W7$7s5V6U7C7E7x7y0h2a0V0c0D1(0Z2z2a0`0K0M2C2E1~1e0T200H0U0J0U0e7L7J2W1w0B1(2B0;0U610!0D0E2E0U0c0B0B0Z2D2a8i2A0Z0U6_6{6;763r8G5I7T7V0G454S7T7#4p8M246n7*5O8R8N6t6!4 7D3k7y2A200.1%0U6%6)1(0c8B3i0U2w8c1(8D0D0I0/0t810B0t0X6m8e0Y0L0s1 0M0L0N891 0.870v8+1(8.6%0o7Q8I787Z7b203I4r8O9q7p584r7(7n7h7q0G9u8Z6,268$7=0U959M7O0Y9n2@9p6i8L4I9v8V5(8R4I9A9X7i0G9V3O8(6;7/3_0}0D6:7u0^0c0}0C9;9-018o0}5s8G759R4x8K7c3h4Z9W7!7+8R4Z9#a98W5na79*8(9=016w040I4f9`8!2|9/aq9H1+0c7w2Wau7B3_0#0}9a1E0K7R5f6W6Y9oar3vaD042laI4*aKaS6?6$6(6*aMav0^6W0FaA3T9@040Ga)5ZaPaRa!aB01aUa=4y6^6`8|aV7004a(8G9,aN9?0}0ra.4*9}5Fa~1+a%73b2a1649S7o8L4^a89C584^adbo5Pbmai9+7z9{6@040zb84 a+9_b2akba9 4v7Ra49s3h0P6g9w8Q5nbPbr9x5PbP2L3obwaj9{am0p1R1%bCasbAb,aw7F0e0H9PbGbya:2abca$0}aLa2a#3Ua{6{b|a@71b/9?7w206Sb^b4c2049kaHa_aJ0}0wc5bz9:cdc1a+b7cqa?bzbBcjaT0}0Wc801bEbF2=b3c1bz8{6|c0a?6WcmcyaWb.cQa 0WbfbKa_bM0v5C5pbnbW8R5r8T7m9$9Dc*bZ9Kb#bxcecwcCbEcCc^cua*b6cCba3ma0bL9w8L5DbQc-6r3jbVbS5C6s5.c=cHa?ama}c}5Z0}cxcGakcEc{b`1fcTbdb~cnc3dlcM3Tbe9Qbia3d5a55Qd8ae9Y5n5Sc+7)dM9%dPc:dh9+akam2E0H8wdvdqbyatd3cYdIbN3i7X328PaadO7%8UdSc.7Xdgb$cedZ0)d$c_0}a-dw0^d1dF6~0q675;625?5 1g0H5_eh2R2M0L1$ee0q5@750(0*0,0i04.

Nous allons mesurer les temps d'exécution de ces deux fonctions pour des recherches dans le même texte que précédemment, "Le rouge et le noir". La fonction naive_find est en code caché.

Comparons le temps d'exécution en fonction de la longueur du motif cherché avec la recherche naïve

Comparons le temps d'exécution en fonction de la longueur du motif cherché avec la recherche find

😭 Et dans le pire des cas ?

Construisons un texte (très long ! un million de caractères - tous identiques - par exemple) et un motif (assez long lui aussi ! Mettons mille caractères - les mêmes plus un caractère différent à la fin) correspondant au pire des cas, et comparons les deux temps de calcul.
Vous verrez c'est assez long...

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

.128013So4l57s_x06:.w/+phPn[1gk2c=i)-tfear39,8(dO v];umby050P0H0F0I0C0e0h0R0A0e0I0h0h0B010F0C0r010406050h0V0W0W0I0J0Y040b0c0e0V0?0c0u050p0}0 11130{0r04051j1c1m0p1j0{0P0C0S0+0-0/0;0-0u0x0V0I0x0H0E0r0Y0F0s1a0R0s0C0x0s0e1O0s0F0_050$0X0e0H1v0.0:011N1P1R1P0F1X1Z1V0F0J1k1J0+160h0r0I0u0;0z011#1x010G0(0H0u0I0W0H1V1`1|211%241Z27290_0a0R0t0J0c0r0c0h0C190u0R0!1^0J0J0H0A2u1c2c0u1k0p1J2H1;1?1=1W0P2e1y0C0u262r1V1s1u0,1$2R2T0u0c2X1V0r2A1k2F2H2.0|1{2v2Z222%0J100e1V0I1M2A0G0;030i0i0A2(0H1R2$0c0E0w0k3c0_0R0w1c0I2/2=0`2;2d2@1%2_2{2}2 0H3101333537392U3c3e1 040R0z3j3l1|3n2F2Q013s0I2|1k2~0s303234360!3C2%3E0E0K3g0K3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0E0d3g0d3-1d3/3o2?1w3r0c2`3S3u3W3w3Y3A3#3 3%410f3g0f462.3:2=3P3@4g3{3z3!384m3b410l3g0l4s483;4b3?4d3t3U3v3x4A3~3a3(0g3g0g4J3M4u3p4M3Q4O4f4Q4h4S3}4l4V410N3g0N4!2G4$4a2!4)4e3^3`4i3|4k4C4;3e0L3g0L4_3N4v3=4~4P3_4R4j4B3$4E3e3d0_3d5b4{4w4*505i535k4D3(0w0w5p3i0p3k3.3M1n2,1c2X2K0P1?2P5e4B2W1t1k2+0H2-3m5H2G054B5Y2d0C0P0;342F5A3u5*5,545l5/0R2i0H5=5y563f2H5G4L4}0y0_0!0G5!5(4|220o3g68494w0G0_270C0G0i260S0H0J0h6e62220^040O6s5d4(0u0_0F0H0j6D6y4%4}6v0M680R6f5e6B040W0c0?67475I6t1%6v0D0m680{6W5#3O5;015-2=3(3G5h6,4/55403F205`5|4U6_0E6;5F3H0R746O6A0_2S1s0A0H6r6)3H764}0c0_0B6M7g6u0_0v0T6%6H2v6?0i5.413*4Q7u5}6 3*5_285{6-5?5z7x1V7274756Y3?787l7P017i047k7e6N7T0W0C0_0k7r7e6f7u7w3e437z5+7H7B4n7.6{7F6}4:6 7/3K7N7Z6z630_0o1N1Z7S822^7R7Y7m1%7V020e0F0U7X2.816I2^0X0_2h7s3P6v6x7*7T6Q6D6F0H8s5e6!888n8e0_0E8F6a3r8p048r8w896Z0_8v2:8x0_6S6U8C4(6!6$7e6(8V4v7,6/4o5:7;6@5@8.7E297{6^7@0E4p6073807O8R7Q040y8K3P7V8k3m8m8L3?8N8P8*8G0;8u8!4}6Q8Y6k9k7n040D9p8H048J8Q9h017#5p6M9b3P0A5C04030R0Q2v1{0J0F2w1!0-0R242v0#0R1L0G0%9O1s7#0u0V6p0R958(8s8,1|3(4G7:8_8=3e4G8@7G8;7J9^7L3k907N8d0;64048525966P0_9+8la37U0_020x8i993M9D5e9A047(8c7T0c6c041|0Pa977048z6G9x9c016v0v9t930Cay7h0_0qaL8a94aIaF0_7qar92af7Wak2Gamaz9n6V9gaEaGaS6Qac5Z7T6v0T8%4t9-8:7v8-3e4X9=7=6~8{4X9`9?9}0Ea~7 a190aea.aP9ua!7f8WaRaW9y7V9wad7!7$045Ea^aD0R9.0u3(4?a 9|5~4?b4b07|8{bzb9a1aea59obkaEbdbO977jbga$aM9vaSaobsa:aX6va@48bubw3(58bA7I5~58bEbB6 b-bJba919y6Q790C7b7da*bS040na-0_0I0r0r26axbu8D8Tc604aKcd8#0_9s9,b*a`7-3E8/b55~5ob=b/6 5o8~b`bc8bboaX98beaJcHaYaObRanbqb!4#a_5=cq5BcsbF8`5m3c5Ccw7?cYcUcAa27Ta52A0F0V0J1bcMazb~c07)2:0p5%5J5X5L5U1c0F5Od12N2I0I1Yc~0p5M6(0!0$0(0h04.

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 sauf la dernière 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}

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": 1, "t": 3}

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

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 valeur possible de i vaut 9.
En effet : len(texte) - len(motif) = 13 - 4 = 9

variables

5. Compléter pour le "a" en vert du texte : texte[i + ... ] = "a" dans la situation suivante :

variables

Donner la réponse en fonction de len(motif)

Solution

texte[i + len(motif) - 1 ] = "a"

Comprendre les décalages à réaliser

1. Décalage pour réaliser un alignement

decalage 1

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

Il faut aligner les deux caractères "c", et pour cela faire un décalage pour i de 5 - 3

On obtiendra donc :

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

Aide

5 - dico["c"]

Ecrire 5 en fonction de len(motif)
Remplacer "c"par dico[text[...]]

Solution

(len(motif) - 1) - dico[text[i + (n - 1)]] = 5 - 3 = 2

2. Comprendre le dictionnaire de prétraitement

Quel aurait été le problème si le dictionnaire de prétraitement avait contenu la dernière occurence du dernier caractère du motif?

Solution

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

En utilisant la formule précédante on aurait obtenu un décalage de 5 - 5 = 0 !

👉 On comprend donc pourquoi on exclut le dernier caractère su motif du dictionnaire.

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

saut 1

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

"a"n'est pas dans dico. On peut donc directement faire un grand saut de longueur len(motif) . Cela correspond à un décalage de 6 . i prendra la valeur 1 + 6 = 7

On obtiendra :

saut 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 se replace au caractère du texte superposé au dernier caractère du motif. Suivant le cas :
- soit on réalise un décalage approprié pour aligner les caractères
- soit on effectue un saut de la taille du motif.

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

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013So4l7s_60:Mw+pHPn[1ci)-e3,(v];uyqTBxL./hgk2=tfra{9}8d ém5b050#0y0T0W0v0e0g0$0u0e0W0g0g0S010T0v0o010406050g0F0(0(0W0V0G040b0c0e0F0~0c0r050N1517191b130o04051r1k1u0N1r130#0v0C0?0^0`0|0^0r0P0F0W0P0y0x0o0G0T0O1i0$0O0v0P0O0e1W0O0T11050.0*0e0y1D0_0{011V1X1Z1X0T1)1+1%0T0V1s1R0?1e0g0o0W0r0|0R011-1F010U0:0y0r0W0(0y1%2224291/2c1+2f2h110a0$0q0V0c0o0c0g0v1h0r0$0,200V0V0y0u2C1k2k0r1s0N1R2P1|1~1}1(0#2m1G0v0r2e2z1%1A1C0@1.2Z2#0r0c2)1%0o2I1s2N2P2_14232D2+2a2/0V180e1%0W1U2I0U0|030h0h0u2:0y1Z2.0c0x0t0z3k110$0t1k0W2`2}122|2l2 1/313335370y39013b3d3f3h2$3k3m27040$0R3r3t243v2N2Y013A0W341s360O383a3c3e0,3K2/3M0x0z3o0z3S2M3u133W3y0|3Z3#053%3)3G3+3J2!3L3l0x0d3o0d3^1l3`3w2~1E3z0c323!3C3(3E3*3I3-473/490)3o0)4e2_3{2}3X3 4o433H3,3g4u3j490i3o0i4A4g3|4j3~4l3B3$3D3F4I463i3:0f3o0f4R3U4C3x4U3Y4W4n4Y4p4!454t4%490!3o0!4,2O4.4i2,4;4m40424q444s4K4|3m0Y3o0Y513V4D3}564X414Z4r4J3.4M3m0t0j115w5j534E4=585q5b5s4L3:0t0t5y3q0N3s3_4-4h5C574G5a4#4{485v3O0t3R5O3T525S5m4F4@4H4`5d5Z3M5y3@5(5Q5*4T555-5p4^5r4$5=0t4b04645A5+4:5~594_5c5t5J4x664z5_4f5R5|305D5V6d5H5e3k4O664Q6k4B695}6p5.5W5:6f490t4)664+6y4S5l6a6C5 5/6e5I6H4~66506M6m6O6B5U6D6r624v5v5g665i6Z5{6#6o6%6R6E6T6t0R5x046|686n4k6@6c615Y6+0x0R5L6~5N5P6l6;4/6$5o745G6*5u783O0R5%7d6z714V735F5X5;770R3=6~5^7r6N7g6?7i7w6F6U3N650R4d6:2P2?0y2P2)2S0#1~2X5m4J2(1B1s7S2^3u5`1s4J7*2l0v0#0|3c2N5J3C7;7?6`63282q0y7|6s7~2P5P7t010Q110,0U7,6A2a0m3o8d870r0U8a0v3e0h1+1^2I0g8i6=1/10040B8u7G3z110(0c0T8A542a8x0w0k7,137e7/2D7{017@2}3:3O5p8S7K6{7 2g818T7}7z1%5(0$8.0$8e8C040#7,8:870c110S8^8;0|8x0X0Z8N8H0$8Z0h7^497B8Y7=8)83773=0$80827l3:9b8-8/8 88110U4l8~8j110v9v8v0|0c8g042!9z8B3~0*110V241M955m8x8z8P9q0r9J042p9O4:9Q9Y5}8D8F9#8J110w9G8I1/8{040x9-3X0(0v5y9)8w9+8M8P8O2{3W97993m659c9k767m4b9i8%a87yaa8,3s8/aj8_9A3Y8a9{90110sapan048E8G9S878xasayam0r9xat8x0D0D9?5m9:8}8Pal9Hau9y9 95a38V4w7`9d8!5=4xac2hae6G3m6h3Saj9q89042I0T0F0V1jaO9TaoaTaC7:aZ98aW3m6va79e9l4N8$a(b6a93:b45(a07+a2b0a40x6Jb5a!774)a%8(bo7mbm5_87a:8bat9D8:a~9.3~8l040J0l0paG119Ra1aD110T0y0KbRbL040AaK6a9%0~8cbD3X8K9~6zb%aV243:6Wbn8*7m4~bra)7L0xb:9o8.a{8?8n0cbY55aMc3308m8o8q1|0y8tb%9PbMataEav8F0vb$bOaQ8K94b,bjb20x6-b;9f7m5gb^bbaf3:cvb}aPbEaua_2_cG3Xc5a`8j9V9Xce9ZcgcS9$cjb#bV9,a}cn8Rcsb.6H6}cwb75v5xcAbt5Jc+cFb 2!1A0uccc69/8|c}aq040saJaOcL7!7a030$0L361Z0gbR2Ecc960rc`dh0W0F0K0H0F3g0=0g1,1|0c0F0C2e0T0$1+0$awcl0?0O0y0V0u0O0%cqc$96c(0r5J7ac,bc6H5Lc:b=dSah3P9p9w9Ed001cNcK9q9^110jdNbh4Db-dR6H8X3697cx5J27dYd~d`d#a.bx110m1V1+d*ciaSd-8`11020e0T0EaNeeaDcQ2ebVbNd?aQcibRbT0ycZd*9:9=cObP04cJescH8xb*4gcr7|bk3laYb_6teOe1c-5?85d$akd6bZ040Qezc eCet11eF3UeZc411eBemaQd/668^0$bg3U5Sd^5Ja6d|b0e25vab9jcBa*3ka6cFe5ama:e82deb11e$e)cH9:020Pejel3ue.2ae@d;fkcM9D248@fw5,bQbSbUcV9*d2chaFfB4:9:0nfhe#bVd4e=fl8|fqe-b dEcmeGb(arfJfQfG9|040DeJfX870ud80$0I24dAdp02030z0Y0E0:0$0G0$363e2Hcc2ydj24c{d=e|bieMct0ta,f1eQ63a$f6c;6Ha,fbeYfs8=fjfTcMe(gwfCf)gzfMe:d*e@5Nb+dOe~6Hb4gjf7b`0t4OeTdV5vbeaigsa/9xf!f/eDgvfr9qaMfW2Ogt9BgEf*0|gGbVf.g,e{2Oe}dQ5JbmgNgo5vbqgndZ6HbvgWgsd%eDc_8nc|g:d+110Mf(0W0o0o2efAdOcf8yf(edf#hpc!gIf#gK5vb:g h4hzb9bshC3kb|h7h8g-aRe%04g+3Pc^hNfOfL55g=aOg_8QdPgfc)6,ePgOeRczh3f33kcEhJfcaQa:drexheeIgcg`ge8)bk6|h(h078c/h,eUi0eWhKh9h=gZfPevfFhocTfIheechSfPe,g,g)g/gChV9_e^h_11fSg(8`9D9FhUc7c03eg?h{hZhy78dThBh-79hEgk7zdTgri9hRiCc~hOfPhsg#aQfNimhNe;iyamhWir2aeAfPc`c2iviiigcWieh^i_fHaBi}8=i!ioef04hTi.8=inhQj4i*i#cHi-htihaIiHg{h#d_3Nd{h!h)5=7piPjq7z8XiTakgY04h@iGc#hxg|497Ai1hGjHgScCjG9nh:i9hLikiWg.iYjThMjWi%jWcij9hYjkh~ct7OjIiNf5adju7mj+i8iacHa:a=a@j9jR9xdjhccdhwe|0N7.1v2@1k7V1k0T7Xka2V2Q0W1*7Tk87%8O0,0.0:0g04.

Algorithme de Boyer-Moore-Horspool

def BMH(texte, motif):
dico = dico_lettres(motif)
n = len(motif)
indices = []  # La liste des indices auxquels se trouvent le motif cherché
i = 0
while i <= len(texte) - n:   #(1)
    k = n - 1  
    while k >= 0 and texte[i + k] == motif[k]: # Tant qu'il y a correspondance
        k = k - 1
    if k == -1:   #(2)
        indices.append(i)
        i = i + 1   #(3)
    else:   #(4)
        if texte[i + n - 1] in dico:   #(5)
            i = i + n - 1 - dico[texte[i + n - 1]]
        else:   #(6)
            i = i + n
return indices

On remonte le motif à l'envers, tant qu'il y a correspondance et qu'on n'est pas arrivé au début du motif
Si on est arrivé à 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 la lettre de texte positionnée au dessus de la dernière de motif, avec la dernière occurence de cette lettre dans motif.
On fait un saut de la logueur du motif.

V. QCM⚓︎

L'algorithme de Boyer-Moore

Dans tout ce QCM on considère la fonction BMH qui prend en paramètres deux chaînes de caractères texte et motif, et qui renvoie la liste des indices où se trouve motif dans texte. La taille de motif est n

dico_lettres est la fonction qui fait le prétraitement du motif cherché.

Que renvoie dico_lettres("pacecap") ?
- {"p": 0, "a": 1, "c": 2, "e": 3, "c": 4, "a": 5, "p": 6}
- {"p": 0, "a": 1, "c": 2, "e": 3}
- {"p": 0, "a": 5, "c": 4, "e": 3}
- {"p": 6, "a": 5, "c": 2, "e": 3}
Remarque
.8594o4l5s_L06.:/phPnA1gk2cj=iè)àftîear{3},(d véumbqE050n040h0H0P0D0b0q0w0E0z0(0P050w0b0O0G040O0z0:0g0d0G0E0E0I0G0f050m0:0=040P0H0f0f0b0w0z0G0P0C0P0w0o0H0V0S1f0|0~100P0f0H0S0D0P0d0#0=0I0q0z0A100M1s0-050f0 0(0t0@0G1B1e0I0P0I0H0q0t131K0I1M170O1V0f1x1f0T0b0+0D0k060p0b0S1S0/0;0?010n0H0w0G0w0H0n0113150?0P0N0z0q0^1 1)0i1g0P0j0B0P0l130Y06050S0d042o0d0z041_161|24141`17221}1U0F0E0P0G0q0P0n0b0f0z0+0(2e2J2I0j0P0a0P0-100+2K2I1J1L1W040j1Y2*1N132u2s052=2x1{0H2A262D0n2F0H2H2J2L2N2P2R0q1)0s2U0P0e2X2Z2L2#1e0q2(1Z1#0e2.1!2+2;2v2t2v2_04010w2|2C182 0H2G2I2K2M2O2Q0,380P0v3b0c3e2!0}3i3k2/040c3o1#3r2?2^2}010G3z163B30320S1C1m0G0T2%333H363K0P0K3Q3g3S3@2)3p1N0K3Y3q0m2=2o0m2q2?0Y0r2a2P2k0.2}2c0b0P0y0P0J2z0l2h1G012{4s0e4u3y4s0c4u3)4s0K0L252C2m2?0U0d1c0u1m1-0?2o0Y421#0p1D0t1f2l0m3l2+0P0W2L211)0=1*1q1f0I0R0n0R0E0R0G1G0w00112I0E1?0x1?0I1)1y0.4%1N1A1C1E1f1c0w1@100)0G461N0P1m0z2J1K1i2S1P0Q4`0k4K4a4M4O4Q0E0?.

Au début de la fonction BMH, avec quelles valeurs i et k sont-ils initialisés ?
- i = 1 et k = 0
- i = 0 et k = 0
- i = 0 et k = len(motif) - 1
- i = len(motif) - 1 et k = 0
Remarque
.olsx0.ê/phngkciè)àtfear,(d éumb050i04050n0a0z0u040o050h0J0L040A0i0a0o0k0s0u0A0c0C0w0A0b0!0z0B0E0C0s0A0L0)0v0A0t0u0k0g0s0w0+0v0k0c0)0!0Z0d0Z0A0y0,0D0v0w0~0A0r0A0e0q0x0A0u0:0I0K0M0m0P0R0M0U0W0Y0!0$0(0*0A050c0}0a0k0l040L0w0k0o0u0(0n1c0v0n0s0p1e0z0C0A0D0a0s0o0t0P1E0w1G1I1v0%0A0J0D0D0`0n1O0?1:0a0D0i1R0o0c1G0;0+1+0o171g0l0v0C0n0j0u0f0P0G.

Dans la boucle interne while k >= 0 and texte[i + k] == motif[k], que se passe-t-il si on sort de cette boucle avec k == -1 ?
- On a trouvé une non-correspondance : on effectue un décalage.
- Toutes les lettres ont correspondu : on ajoute i à la liste des résultats, puis on incrémente i de 1.
- On place le motif juste après le caractère différent.
- On arrête complètement la recherche.
Remarque
.ols./phn1gkc=i)-ftàear,(dO véumq050f04050l0a0y0t040k0A0m0m0A0p0i050e0K0M040A0c0n0j0h0n0q0n0t0A0F0D0-0r0a0D0r0t0c0A0b0_0A0K0E0f0u0v0u0n0c0a0h0`0x0M0A0y0v0a0n0^0A0s0A0j0u0D0l0g0t0o0A170r0A0v0C0D0c0$0d0A0z0h0A0t0h0v0t0j150r1I0{0u0A0f0a0$0r0n170A0J0L0N0n0W0Y0N0w1Q0D151s1E0u0B0u0h0l0-1Y0Z1#0X1Z0!1b0i1Q0?0v0~1p0v1o0t220D0h0-0C0B1G0r0:0b0|0A1m1M0-0a0l0l0D0v1I1=0t0d0W0H.

Dans le bloc else (non-correspondance), lorsque texte[i + n - 1] est présent dans dico quelle est la nouvelle valeur de i ?
- i = i + n - 1 - dico[texte[i + n - 1]]
- i = i + 1
- i = i + k + 1
- i = i + len(motif)
Remarque
.ols/pngcCiteard éum050e040i000l0c0k0p0b0l0p0o0q0h0m0b0m0g0D0e0a0r0n0p0n0q0I0j0c0l0Q0b000U0g0f0l0s0l0f0k050d0u.

Dans le bloc else (non-correspondance), lorsque le caractère texte[i + n - 1] n'est pas dans dico, quelle est la nouvelle valeur de i et pourquoi ?
- i = i + k
- i = i + n
- i = i + n - 1
- i = i + dico[motif[-1]]
Remarque
.olsx./+pngc=iftear,d um050h04050k0a0t0p040m0u0l0u0G0g0u0i050f0B0D040s0u0k0q0r0u0a0i0u0n0q0m0o0u0b0p0u0c0q0v0)0w0q0d0m0=0b0u0D0*0Z0j0v0p0v0X0A0C0E0N0P15040e0O0y.

Dans quel sens l'algorithme de Boyer-Moore-Horspool compare-t-il les caractères du motif avec ceux du texte ?
- De gauche à droite, comme l'algorithme naïf.
- De droite à gauche au sein de la fenêtre courante.
- En commençant par le milieu du motif.
- Dans un ordre aléatoire déterminé par le dictionnaire de prétraitement.
Remarque
.olsxL./phngcCiètfera,d véumbq050h040e000t0b0k0a0s0n0p0i0A0r0w0l0a0A0Q0j0l0R0h0t0s0S0U0!0s0r0$0b0R0v0+0j0n0+0S0#0t0l0p0o0*0w0v0z0w0A0a0p0n0q0w0t0x0r0l0w0-0@0s0_0{0}0T0s0*0c0h0a0j0v0t0j0p0~1r0c1c0R0p0r0d1z0u0w0h0z0n1w0*121s0R190s1w1d0v0y0B0z1t0 1113150f0w0m000r0c1t0Y0w0c0r0j1w0/0%0A0)0t1H1o0w0C1G1E0+0Q1V1%0d0h0b0a0N0?0r0q0q0n0l0_0r0W1t0-1:0y2d0b0t0k1(0f050g0E.

À quoi sert le dictionnaire de prétraitement dico construit à partir du motif ?
- À stocker toutes les positions du motif dans le texte.
- À compter le nombre d'occurrences de chaque lettre dans le texte.
- À connaître, pour chaque lettre du motif sauf la dernière, son dernier rang, afin de calculer le décalage à effectuer en cas de non-correspondance.
- À trier les caractères du motif par ordre alphabétique.
Remarque
.oQlsx./phngcièàtfear,d véumb050h040b0z0s0j0v0w0z0j0r0w0c0r0p0p0t0N0v0z0w0p0r0e0Y0w0M0w0l0a0t0T0d0h0a0I0w0h0s0d0w0s0W0l0s0t0s0l0p0n0T0^0R0r0I0W0V0w0A0a0p0m0q0u0w0/0(0/0d0z0c0#050)0v0r040v0m0)050g1p1r0;0a0z0t0w0d0s0x0a0m1D1q1i0A0B0m151g0j0;0r0z0p0w0v0y0{0P1D0P191b1d0w0x0r0t0@0c0s1X0t1I0Y1f1Q0l0i1-1{0H1W0o0^0c0m0k0M1D0l0Q0#0P0R121G0r0l1E1;1q0t0j0m110N0a0l0l1C0T0j281X0H1/0N1a1c0q0f1w0D.

Quelle est la valeur maximale que peut prendre i (l'indice de début de fenêtre) pendant la recherche du motif dans le texte ?
- len(texte) - 1
- len(texte)
- len(texte) - len(motif)
- len(texte) + len(motif)
Remarque
.olsxL.ê/pnAgciè)-àtfear,(d vé;umbq050i040k0E0q0z0u0b0r0A0O0A0m0u0s0s0u0A0B0v0b0u0E0w0x0A0%0A0F0a0s0n0t0S0C0G0a0w0O0w0v0n0s0S0E0A0Y0d0Y0A0W0,0v0U0a0F0i0v0}0n0c0a0j0A0j000v0)0~100i0b0E0c0S0Z0c0u0j0c0f0A0e1a0_0E0m0-0i0w0n0j0m0n1e0-0c1n0w0w0g160z1j0m0S0o1v0H0E0Z050m0a0O040n0A020l0s0D0,1z0y140Y0p0A0q1_0j0y0/0;0t0p050h1,1.0f280J.

Parmi les affirmations suivantes sur l'algorithme de Boyer-Moore-Horspool, laquelle est correcte ?
- L'algorithme ne peut trouver qu'une seule occurrence du motif dans le texte.
- L'algorithme repart toujours du début du texte après chaque comparaison.
- L'algorithme peut sauter plusieurs caractères du texte sans les examiner, ce qui le rend potentiellement plus rapide que l'algorithme naïf.
- L'algorithme nécessite que le motif soit trié par ordre alphabétique pour fonctionner.
Remarque
.oBlïsx.M/pHhngcCjGièàt-fera,d véuâmyq050j040r0z0H0o0y0D0A0G0f0D0C0F0o0A0c0A0n0y0e0D0!0c0o0G0c0F0*0u0D0j0A0z0v0s0z0X0G0X0s0o0{0a0m0m0A0|0S0C0S0j0z0F0v0z170v0y0I0y0m0v0B0D0b0a0J0y0z0w0h0a0a0z0y0w0k1y0e0j1x0c0@0y0G0v0D0s0n0m1y1t0X0S0n1g0m1a0*1F0`0s140*0C0 1i0f1i0g0D0p000)1L0e140@0z0s0m0o0s0^1H0A0E0A1m0%0S0e0G0}0$0D1z0o0l1t2c0S160d0E0y1o0K0G0s0T211{0S0v0a0G0q2u0z1%000G0m0D0e1J1H0!1g120t1z0D0?290x0a0s0e0g050i0M.

VI. 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. QCM⚓︎

VI. Crédits⚓︎

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