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

.1280136ewn-f(9[1= :7dcokliy5sP3r/h,b]tquSèxam2Ng)é84_vpCà050p0c0G0M0u0t0x0m0q0t0M0x0x0l010G0u0X010406050x0I0N0N0M0A0v040J0r0t0I0@0r0e050B0~1012140|0X04051k1d1n0B1k0|0p0u0W0,0.0:0=0.0e0Q0I0M0Q0c0f0X0v0G0C1b0m0C0u0Q0C0t1P0C0G0`050%0E0t0c1w0/0;011O1Q1S1Q0G1Y1!1W0G0A1l1K0,170x0X0M0e0=0O011$1y010g0)0c0e0M0N0c1W1{1}221(251!282a0`0a0m0y0A0r0X0r0x0u1a0e0m0#1_0A0A0c0q2v1d2d0e1l0B1K2I1=1@1?1X0p2f1z0u0e272s1W1t1v0-1%2S2U0e0r2Y1W0X2B1l2G2I2/0}1|2w2!232(0A110t1W0M1N2B0g0=030V0V0q2)0c1S2%0r0f0k3d0`0k1d0M2:2?0{2=2e2^1(2`2|2~300c32013436383a2V3d0f20040O3i3k1}3m2G2R013r0M2}1l2 0C313335370#3B2(3D0z0`0z3I2F3l0|3M3p0=3P3R053T3V3x3X3A2T3C3e0U0`0U3*1e3,3n2@1x3q0r2{3Q3t3U3v3W3z3Z3|3#3e0w0`0w422/3-2?3N3;4c3^3y3Y394i3c3e0b0`0b4o443.473:493s3S3u3w4w3{3b3D0o0`0o4F3K4q3o4I3O4K4b4M4d4O3`4h4R3e0T0`0T4W2H4Y462#4#4a3=3@4e3_4g4y4-0f0i0`0i4=2I2,0c2I2Y2L0p1@2Q3/014x2X1u1l592.3l3+3K054x5o2e0u0p0=352G3D0k3t5w5y503!4A3f0m2j0c5F4x5H5B1W0B3j453N0s0`0#0g5q2H5U5h0d0`0m5!5u4^2_0g0`1=0r0I0W0c0V1!1.2B5+5$4!0_040h5}4H4_0e0`0q634r5h600D5+5*642_5:0c0L0G0c694Z4_600R0n5+0|435r3M5E015z2?3D3F3?0m6y4+513}3E215L5N4Q6J6D5S5,3N5(040m6W5*6v5#6g1(0x0p0`016*2B0e0W0r0u1#0t002T1t0q1#2y0.0m590N0u0K2B0m0r0q0q0I2A276_2x1#0q2x1}0+6l6k6m6Z3m7k5U6G0V5A3e3%4M7o5O4z3$6L295M6z5G7w7r5R5T6#0=6%5)6X5=0m6,6.6:0m0P1b1#1|0A1_6-272v0m2t2(666*6t6n2w7o7q0f3 7t5x7B7v523 5K7z6N4,6J7:3I6u2;6x7=6A1}3D4l7;7|6I4j0f4l7`2a8a5P4k7F6V6X5~4_5W040g496e8n6h040u8t7H010r6U2T8y6a4!0e0E0`0A1}1F7+3N60627m8z8H0`2i8N6b0`8Q828F656i7i8W5 0`0R6r7*8R4r7-6B4B5D847C524C8f7A6H8i0f4C2I3j6X946f8#238p0u5Z7k966o8v7h6l8)6p0`0j9i8v8x8/9e1(600F8E9q0=0r0`0l0l9u5-3q679m9r0`6s7k815p835F7.4T897?6O8c4T8|8h7D0f9P3I959#9d9C0=8p2B0G771c9c8u9D8w8.8!5v8^7.4/9Q8~9X4/9V9R7}8c9{9!8m8z0q5C04037#0u732w0c0x0G0m79496;0Z0m0n0,00agai0H0I001M0e002 1|7g2p5?0S0m1!0,120M2D717j4p8N8;863e549|8_6J54a09}52aTa56W9:9)8J0$9-9B5V0q0`7S2Ua-5ha80`ab0Y0$6laG1P2U5Karah6}0/5K0S6_0:0(5|9J5}0B5t1o2-1d5c1d0G5ebk2O2J0M1Z5abi5l6u0#0%0)0x04.

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

.128013î6ewn-f(9ù1T= :7dcokliy5.sP3r/h,btquS!èxam2Ig0)é84_+vpà050r0d0I0P0w0v0A0o0s0v0P0A0A0n010I0w0$010406050A0K0Q0Q0P0D0x040L0t0v0K0{0t0f050E12141618100$04051o1h1r0E1o100r0w0#0:0=0@0_0=0f0T0K0P0T0d0g0$0x0I0F1f0o0F0w0T0F0v1T0F0I0~050+0H0v0d1A0?0^011S1U1W1U0I1$1(1!0I0D1p1O0:1b0A0$0P0f0_0R011*1C010h0-0d0f0P0Q0d1!1 21261,291(2c2e0~0a0o0B0D0t0$0t0A0w1e0f0o0)1}0D0D0d0s2z1h2h0f1p0E1O2M1_1{1`1#0r2j1D0w0f2b2w1!1x1z0;1+2W2Y0f0t2$1!0$2F1p2K2M2?11202A2(272,0D150v1!0P1R2F0h0_030Z0Z0s2-0d1W2+0t0g0Y0g0l0~0o0l1h0P2@2`0 2_2i2|1,2~3032340d3601383a3c3e2Z3h0g24040o0R3o3q213s2K2V013x0P311p330F3537393b0)3H2,3J0C3l0C3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0Y3l0Y3;1i3?3t2{1B3w0t2 3X3z3#3B3%3F3*433,3i0y3l0y492?3@2`3U3{4j3 3E3)3d4p3g3i0c3l0c4v4b3^4e3`4g3y3Z3A3C4D423f3J0q3l0q4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0X3l0X4%2L4)4d2)4,4h3|3~4l404n4F4@0g0j3l0j4|3S4y3_514S3}4U4m4E3+4H3j0U0~0l0U5e4~4z4-535l565n4G3J0l3k045F5e1s2;1h2$2P0r1{2U5h4E2#1y1p2:0d2=3r3=3R054E5Z2i0w0r0_392K5E3z5+5-575o5:0o2n0d5?5C595G3;4O500u0~0)0h5#2L4c3U0e3l685)4 2}0h0~0f0H0Z0t0s0s0K2E2b0s0d0A6e6a5h0}040i6w622}0~0I0d0O6G6C5g4+6z0G6e0o6x4+0f0~0Q0t0{674a5$6D1,6z0V0p6e106Z693T5=015.2`3J3L5k6/4=58443K255{5}4X6|6@0E3p6R506c3M0o7a6K4*500A0r0~017i2F0f0#0t0w1)1(5`0t0Q0H2F2B1)0h7n0/0t0k0o6V6X0o0P0$200D0P0b0I2B210/6G6I1)7i016P6+2^6.5,6:0Z5/3i3.4T6_5@5D7(6~2d5|7#5~6|7)3P7X5!7Z5?7%3h5;7!6`5^457/2e704?6|462M3p7a7b6#3`6j6l6n6p7k6t6P76270t0~0n8n8f010Q0w0~5u6,3M8o1,0s5G030o0S0f2y0w3X0w0A0P2z2B0K7r7t7v0r008j6q6s6u6*7c2A7+7~4s7*817,594s5`7:876{4q0g8+3P8d6Q8u6T042X1x6t6m6o6q8l0d8t6L508q048s8A8}9a278w8y997d278E0~8G910w6t0o0%0o7J0{0D8R0J0K3d0o1Q3B0h2G0I9C0o0=0o2F0s0F0d0D9P7x918$8A6a8)6=4I808?830g4J8;867=718^4J8b798e9h3w0~2F120v0+0I9l6g1,9c9e2?9g9m9^047R6J9X8u9c0z8%4z0~290f0raf6y0~6Bab9@8g047E0w6Ya48C0_6N9 ag90aj9s0d948k97al6M0~0V9W7Y4y9Z214Z9$9-888^4!9+7;827-0g4!9;8|ax0164040e1S1(aA5h8 9`0K9|8Pa;4+9c0Ma33ra5a00_9c0gaJ509j5Hb6276z6)9fa*9o048G0m217N9B000-0o6H8N6G0o0K2Y7G1d7v8YaI8A7`6!aP8-7~4_8,9%a#4_aYbJ59bH8{8|8da*8 6kaG8Z0f8mbeac8ra{50bU8i95bAawb#040!b%9i8xb9bBafaQ0f3J5bbIaU8@5p5bbMb 9(b}bQbRb1aB9r93bzb,b0a*a2b;a7a@a_9~b!aq019cb:cna60_b83ncsb201bg8G1Q0A1)0r0W0$0=9t7H0D0N0/0v8Xb+8!0o1_0t0K0#0W98b^ap5*bF9!5qaTa!5 5rc3c*6|5t1!749=bRbT9_6ua^9}cib3b$cxaBa9cYaOctcp0~aec!cy8 aiakd93U6zaod4da6U6Wauc}01azd0a=0~cbaFcd8!ba6$aLdncA7rcV3d7q9O9Q9S9QaN7{bE7}c%5Fc)8.c/3kc-dR8^dPa(bS8ua,2F9J0D1gdq6S8hbWce4(6w0E5(5K5Y5M5V1h0I5Pd`2S2N0P1%d@0E5N6+0)0+0-0A04.

Question 2

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

Évaluations restantes : 5/5

.1280136ewn-f(1= :dcokliy5.sP3r/h,btuSxam2g0)4_+vp050m0c0D0H0r0q0v0k0n0q0H0v0v0j010D0r0R010406050v0E0I0I0H0y0s040F0o0q0E0,0o0e050z0?0^0`0|0;0R04051c151f0z1c0;0m0r0Q0!0$0(0*0$0e0K0E0H0K0c0f0R0s0D0A130k0A0r0K0A0q1H0A0D0/050V0C0q0c1o0%0)011G1I1K1I0D1Q1S1O0D0y1d1C0!0 0v0R0H0e0*0J011U1q010g0X0c0e0H0I0c1O1:1=1`1W1}1S20220/0a0k0w0y0o0R0o0v0r120e0k0T1.0y0y0c0n2n15250e1d0z1C2A1*1,1+1P0m271r0r0e1 2k1O1l1n0#1V2K2M0e0o2Q1O0R2t1d2y2A2%0=1;2o2S1{2W0y0_0q1O0H1F2t0g0*030O0O0n2X0c1K2V0o0f0t0f0i0/0i150H2(2+0:2*262-1W2/2;2?2^0c2`012|2~30322N350f1^040J3b3d1=3f2y2J013k0H2=1d2@0A2_2{2}2 0T3u2W3w0x0/0x3B2x3e0;3F3i0*3I3K053M3O3q3Q3t2L3v360N0/0N3Z163#3g2,1p3j0o2:3J3m3N3o3P3s3S3=3U360t0/0t3{2%3$2+3G3*453.3r3R314b34360b0/0b4h3e1g2#152Q2D0m1,2I3(014q2P1m1d2!0c2$4z3|3D054q4Q260r0m0*2}2y3w383L0k4Y4!494r334%1_2b0c4,4q3T4t371O0z3c3~3G0p0/0T0g3!4T3%400*0d0/0k552z4 4I0e0g0/0e0C0O0o0n0n0E2s1 0n0c0v0O2t0n5d4W3 2T010.040h5z5f583H0/0D0c0G5M5H575C5E0B5z5c5R2.0/0I0o0,544S5e5X1W5T5V5I5C0e0/0r5Q4k4I0o0/0j5?3h5J0I0r0/0L5|5B1{5E0M0l5z0;5(5A4*4Z014#2+3w3y3,6d4@3;4/361^0k4=6m4a6o3x4|3c0k6z5W5@5J5:040r5m5o5q5s0c5-5*0*5_045{6b6B5}5/5L5N5P6b5.1{6P0u634l0/1}0e0m6(4I5E5G6Z6N5K045!5$6.5J5,6=6C6V6F6{5S0/0M696(4+6f0O4$363W4)783:6u3?0f3W6r214?794^4s3V6x046A6T641W516F5%2%7v6)6F6H5p2t0e5t6M6 6#5`6R7B6!1W6P0f721{5 397K6U650/686b6a2)3F7f7a6h3@3m7+7p6v3^7l226t4.7i3^2A6y7u6A7Q0*7y2t0D5q146S81017W04627%776e6g1=3w4e7e8g4-4_8j4;7m7_8o4d7s7u897y310v6L886?5E7$4i8f4,7b0f4v8l8s7q4u8q7^7o6n7i8L3B7 806?830U867Y7w0*8b3a8C7L7R0/0P8%7D5k7F5q7H5t5v5x7U5+0/6;7)8-3)6W5O8B917Z8~045U8,98936^5#0r7A4z8D0/9b7P6?6E6G5n7G6K8;5^8/9u5~60048+978(5D74766Z0z4V4A4P4C4M150D4F9O2G2B0H1R9L0z4D6a0T0V0X0v04.

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

.128013î6ewn-f(9[1= :7dcokliy5.sP3r/h,b]tuSxam2;g0)é84_+vp050q0d0I0M0v0u0z0n0r0u0M0z0z0m010I0v0Z010406050z0J0N0N0M0C0w040K0s0u0J0@0s0f050D0~1012140|0Z04051k1d1n0D1k0|0q0v0Y0,0.0:0=0.0f0Q0J0M0Q0d0g0Z0w0I0E1b0n0E0v0Q0E0u1P0E0I0`050%0G0u0d1w0/0;011O1Q1S1Q0I1Y1!1W0I0C1l1K0,170z0Z0M0f0=0O011$1y010h0)0d0f0M0N0d1W1{1}221(251!282a0`0a0n0A0C0s0Z0s0z0v1a0f0n0#1_0C0C0d0r2v1d2d0f1l0D1K2I1=1@1?1X0q2f1z0v0f272s1W1t1v0-1%2S2U0f0s2Y1W0Z2B1l2G2I2/0}1|2w2!232(0C110u1W0M1N2B0h0=030W0W0r2)0d1S2%0s0g0c0g0l0`0n0l1d0M2:2?0{2=2e2^1(2`2|2~300d32013436383a2V3d0g20040n0O3k3m1}3o2G2R013t0M2}1l2 0E313335370#3D2(3F0B3h0B3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0V3h0V3-1e3/3p2@1x3s0s2{3T3v3X3x3Z3B3$3 3(3e0x3h0x452/3:2?3Q3@4f3{3A3#394l3c3e0c3h0c4r473;4a3?4c3u3V3w3y4z3~3b3F0p3h0p4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0U3h0U4Z2H4#492#4(4d3^3`4h3|4j4B4:0g0j3h0j4^3O4u3=4}4O3_4Q4i4A3%4D3f0R0`0l0R5a4`4v4)4 5h525j4C3F0l3g045B5r485t4~4x514S4/403f3H0l3K0D3l3.4!5G5d4w4+4y4.545N0l3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550l4F5D4H6b2;1q2-1d2Y2L0q1@2Q5d4A2X1u1l2,0d2.3n5~1l4A6G2e0v0q0=352G5A3v6N6P655z3e3g0n2j0d6V6j5%1W5}6e1(0t0`0#0h6I5/4|0e3h6=6,3?0h0`2B0r0E0d0C700d0W281u0d6`5c4%0_040i7a4$610`0I0d0L7k7g4{237d0F6I0n6?2_0`0N0s0@6;6c2H7v1(7d0S0o6I0|7C6L2w6U016Q2?3F3H5g7O5#663e206!296$7P6W557T6+7b6@3h0n7/7o3Q0z0q0`007_7J7;7V0W6R3e5)7U6O7%6(4m0g3*7!2a6%5^86817+7h237?7.7/2B0f0Y0s0v1#0.0n1S0z7k2x0d0+2T1t0r8x0n0i0T0Y270I0J391!2a0f0I0n0Y6N0d0S8w0+0s0r0r0J2A278B0+0#7{7L5G7}7 0g5`828b5M8642897$7W6X8.6*5T6{018i3I7/8w8s2 700M0b2U0n7y7A2x1}0+8r97991#7k7m0d0y8)2;3P8,7R4n6T838`554o8^8;5$86683-8 91930n7_009p6H9r9w7~9t3d9v9B7X9S9A848c5l6m3L9I7E3?0`8z0v8$7t9(010s0`0m9.8 7d0k0H9M3N8+9P8-4W4P7}855l4W9X9x5Na19$939/0f9*9@7,239;049?7L7u8 0N0v0`5q7L7K9q4u9s1}3F4=a29Pa4az216#9U8{aAab7:8 6.040e1O1!ag8g3safam9/aj020u0I0Pal2/anah3s0G0`2i7;5d7d7f8*8 ae049l7na?a*0=7GaS7p1(aj0gb04va,04a.a|aTa~0`a=avbb3R7x7z0v7Bbfb1bc047H9|7D9O6V8-57aBaH5557a77(5NbwaK9Ia)bga^0tb55daja%3nbHbn01aparbr7M0nax0f5A5nbx9Y8=5l5paF7#by5%b#bF9%aM0`aP26bL5:0`bKaW8 aYa!0Pb_61b7b9bm3Qa;a/b`049cbkc94|a b}a}9:6^041}0qc27wa_7la{c6a:0`0kcecp0vcxb20`0XcA9)04b|ct7c0`9{chbgbNbO3NbQ4vbi7AcE019_cVbJcV7d0H7Iat7|9 9R5B9Tb%9Cb)6ZaGc.9Vc,2I3lbGc{cR5Xb{cocB040XcP2Hc}4%bT5DbV9~buc+7T2 a39Z5A7Zc=a8865Q8}92c{9/aNcdcMbRcZdu3QcOd03?c427c!bdcYcTdtcIcf0`bqc(ba7Nc*ay6Y81dfaCdhdSb+8ac?8{5(doc|bGad9*0f8A8xcVaj9odOcScl0Z0Z27cnd=cu7edG04czd|cJbpdabt7%8-0l8/dUb-dm8@dkbCedd%c|d*e0dA9:cCd43I9/d83jdNc6bY67c-dlb)9zefaD6Y9E5,au9NawdQbZ6Y9#ebd!6k4FbBeD3f9#5,b;ciaN2B8I0C1cdxc~e0d,9,d.eu6H0D6K1o6s0D6u1d0I6we_2O2J0M1Z6F6t6C7K0#0%0)0z04.

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

.1280136f(9[T7ol5.s3r]âua;2é84_+àAîewn-1F= :dckiyP,/hbRtqSmg0)xvp050M0D0X0s0P0j0m0K0N0j0s0m0m0J010X0P0*010406050m0r0!0!0s0o0Q040Z0i0j0r0~0i0F0K020s0!0*0t0K0W0D180o0Y0r0D0m050T1517191b130*04051G1z1J0T1G130M0P0)0?0^0`0|0^0F0#0r0s0#0D0G0*0Q0X0U1i0K0U0P0#0U0j1/0U0X11050.0V0j0D1S0_0{011.1:1=1:0X1{1}1_0X0o1H1*0?1e0m0*0s0F0|0u011 1U010c0:0D0F1m0D1_2h2j2o212r1}2u0!2w040a0K0R0o0i0*0i0m0P1h1j0,2f0o0o0D0N2R1z2y0F1H0T1*2%2b2d2c1`0M2A1V0P0F2t2O1_1P1R0@202;2?0F0i2`1_0*2W1H2#2%37142i1j2|2p300o180j1_0s1-2W0c0|030y0y0N310D1=2 0i0G0h0G0H110K0H1z0s383b123a2z3d213f3h3j3l0D3n013p3r3t3v2@3y0G2m040K0u3F3H2j3J2#2:013O0s3i1H3k0U3m3o3q3s0,3Y303!0n3C0n3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0x3C0x451A473K3c1T3N0i3g3=3Q3_3S3{3W3~4k403z0k3C0k4q37483b3/4c4A4g3V3}3u4G3x3z0b3C0b4M4s494v4b4x3P3@3R3T4U4j3w3!0h3C0h4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0w3C0w4{2$4}4u2}504y4d4f4C4h4E4W580G0e3C0e5d3-4P4a5i4-4e4/4D4V3 4Y3A0$110H0$5v5f4Q515k5C5n5E4X3!0H3B045W5M4t5O5j4S5m4;574l3A3$0H3)0T3G464|5#5y4R534T565p5,0H425Y445;3+5e5^4 5`5B545D4=5 4n5Y4p645?664)5h695l555o5F5V4J5Y4L6i4r3,1K351z2`2*0M2d2/5y4V2_1Q1H340D363I6j1H4V6O2z0P0M0|3q2#5V3Q6V6X6q5U3z3B0K2E0D6%5T5q5X456l2p0O110,0c6Q675h0E3C6}6@3N0c112W0N0U0D0o780D0y2u1Q7d0V0i1e725x4 10040d7l4~6m110X0D0(7v7r5g2p7o0S6Q0K6~3e110!0i0~6|6x2$7G217o0%0L6Q137N6T1j6$016Y3b3!3$5B7Z5}6r3z2m6,2v6/6d4H3#1_6i730|703%0K7~7z3/0m0M1100857U807*0y6Z3z617)6W7!6(5q427/2F7;5+7?8d7_7m5h823C7~0K2W0F0)0i0P1~0r1j7i1e0v2t0K2=1P1v2j0X0K0^0K340v0m2t0N1~0i0r6,1,0,877W5#898b0G6f8e8m5~7?4n8k6.8g6:5,8-8q7s2p8t7}7~8Q780s0C2?0K7J7L0K0M2j0=920U94967v7x0D0l8%393.8*7$4I6#8f7+6)0G4J8?8/7,9w7^5=7`018 8v0K85009m6P9o9t8a9q0G4!4.898_7?4!9y8^7=5G9S3*9H7P4b7u2L0r0)0D7E9)010i110J9:9E0O0N110I3=8U9L6y9N6%8+4^9T9O9V5G4^9Y9u5qa69%8v9;0F110P9_8r2p9?049^7W7F9E0!0P115L7W7V9n4P9p2j3!5aa79z9v5aac8h5,aGag7 9`110E1.1}am8}3NakaW7A21ap020j0X0tar37atan3N0V112D805y7o7q8(9Eaj049i7ya{a/0|7Ra!3/ap0Gb55_a;04a?b1aXb311a`aBbf3:7I7K0P7Mbja#bg040%b94 0i7|2j0Mbv5hbx11300XbB7Ha~9,9.a@7n117Taz889O8+5saH9Z8n5G5saLa93!bUaP9Ha.bka}0ObHa$9@b.0|avaxa17Oa38g8+5K9saI6;5Ib!9!5V5I2%3Gb)ahaR04aT2sb;bl04b-as9;a%a)0tce0Fbbbdbq3/a_bM7t0498bocu7B11buci9EbD04bzcn7u7wb0cra^110fczaY04alcDb29=110zcIcgcQbs0pceap0Ja,3Ib*brcfcxbp9McV7ocPbec.b,c#017o0pbP4NbRa49Q5Wb~bW8:5Gd5c2bX5V6=64c8c8ai11cha-cjb:cUb+djc(cXceb?5Yb^7X8JbSd47(3k9Uc36*7.6-b 5 7(dfdg9;6_cSc;3,c-4Qdqdoc.c)c+dRaicp2tc|ctc_dTcwbndQb_c?cBd04sd)aD0F5V8ddCa8dE3A8jdHd79A609C90dgaQcVa}2b8YbLdVb6dndl9`9|040g0o1wdw8)dzaE6*8-d{dI7?0H8=e0ad6ee4e6dicSdraqcZcTegcVapcYed5ydu3EbQd?epd^6*6t8.e19v0H9xeyaMeveWdLe7bkdO2W0X0r0o0FcZea9-9/eR390T6S6z6N6B6K1z0X6Ef22-2(0s1|e 0T6C1Fdx5y2W0!0y0c0s0O7d0U611r1t1v1x0Kd;6y1M3J1G0B1g2W0K0m1e1g0P1,1v0P0KfF1=8UfK96fD0o0~1~8N0P0N0 8H9a1~8Q0c1i2YfG1j0#0o0q8W0K0s8Z056Se.e:1jekeme|3t3%0A8P3k25965/9lfw1O1Q3/1W1Y1!1$1(1*1,231;1?1^2df81}3/gh251@282G1`2-f3g94X0m6J2{4 5F326L6Ae{cM685P5(6pb#0w3A3CeQ5=bQa|gK5{5)ez40gO3$3(5!gU5%gWgMc3gO610K63gSd1g(5A6o6cdcgO6f0K6hg;4(e8gV6a5|e%3xgO6t0K6vg 5@g?52h3gXh50GgO9S0K4$6wg=h1g)hfg+g`3y4_g%hpg@5R5*d8hihi5bhwb+h2g^5Sg,5r5thFc`hHhzgYh65H5Jayhb6khxhehIhA6rgOd55YgR655whGhqh!hRhC5/5J5:hWh,hOh.hQhhh%6160hN5$hy6bhJhtew5Jg~h+e~2%6Cf2f4gw6H3tgAgFe gH6Pe}b`7#aEh%d6h:isdbhBisc6fe4 dO6{c|7|7Fd)5_750477797b797e0/9.0y8F0jd%bhc|e9cKe_gI5h7CcZc:iVbtfu66eSd3ir7@bViu7@iwh$i;6?cViFahiH4 8 9Jenip9Pi:d`dyeuhSd 7:eY4?g-e49;9G8v8x8z8BfO0KiT8H7Y0F8L1Z0F8O8Q8S8U0Ff.8Y8!2Si!d=crd@hCesj8jd3Zg{2ne$gN8,jg9Eji913k93951~c:9a9cg00?9fjZ0Ka 9kj3aCeThCeWetjMgZ9Bi^5Uh7jTcVjV9I86e`c=6Uj;hjith}9RjPjci?9$e*dS5_aZeNbwefc,9;duayd1i.b{7$gOafj@i?abjQhKafkfdNaSaUjFdZa|kieJbkcka*dY2$kg68d#e=i i$iWkUbIj-i*cCkKdW11b8kj6mkSi*bik4c`bm7Lk!i,3Jkriqd^gOaOkwk9aKkzhtaOkf9(kIc!k*aoklkHcVkoj/k5i/k{hLi=k9bZl1ixlib(l5cVdOccaVl8cRdkkmcE11a(a*cnk,kX7QkWi#bIi)lFbsk#lyeKbyjse?iZi*c^lIcReIlOkLdslv9*l7lWc$eFc*i(d,lUiXdUl)c}11c le7Yk6hTljjRb}j{jel|lpdMl6lxlbl!eGl$cfm6kPdm04eMk$3/ePl_jLk`h;6=k~l~6+lmi_h(m3e+c.dOcymac{madXlDa=d$lLl?7pl:d+k=mH7Rk@aAk/mlj5lhh=l}hKh=m0jN5-eBe6c9lr760-f^ce9{11f`kGi-jHl{e3mWi6jb8lj^hSm^mvkQcvlYm7k%m9mhkheEmCl#n74 mjk3a2j:lgh;jKdDi6exkck9i7izlqe,m*e/e;m-ei9~0;m;k^e{e}1M6Afbf12(f42(f6gsic6K7V0,0.0:0m04.

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

.128013î6ewn-f(9[1= :7dcokliy5.sP3r/h,b]RtuSèxam2;g0)é84_+vpà050q0d0J0O0v0u0z0n0r0u0O0z0z0m010J0v0#010406050z0K0P0P0O0C0w040L0s0u0K0`0s0f050D111315170 0#04051n1g1q0D1n0 0q0v0!0/0;0?0^0;0f0S0K0O0S0d0g0#0w0J0E1e0n0E0v0S0E0u1S0E0J0}050*0G0u0d1z0=0@011R1T1V1T0J1#1%1Z0J0C1o1N0/1a0z0#0O0f0^0Q011)1B010h0,0d0f0O0P0d1Z1~20251+281%2b2d0}0a0n0A0C0s0#0s0z0v1d0f0n0(1|0C0C0d0r2y1g2g0f1o0D1N2L1^1`1_1!0q2i1C0v0f2a2v1Z1w1y0:1*2V2X0f0s2#1Z0#2E1o2J2L2=101 2z2%262+0C140u1Z0O1Q2E0h0^030Y0Y0r2,0d1V2*0s0g0j0g0l0}0n0l1g0O2?2_0~2^2h2{1+2}2 31330d350137393b3d2Y3g0g23040n0Q3n3p203r2J2U013w0O301o320E3436383a0(3G2+3I0B3k0B3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0X3k0X3:1h3=3s2`1A3v0s2~3W3y3!3A3$3E3)423+3h0x3k0x482=3?2_3T3`4i3~3D3(3c4o3f3h0c3k0c4u4a3@4d3_4f3x3Y3z3B4C413e3I0p3k0p4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0W3k0W4$2K4(4c2(4+4g3{3}4k3 4m4E4?3g3k0j4{3R4x3^504R3|4T4l4D3*4G3i0T0}0l0T5c4}4y4,525j555l4F3I0l3j045D5t4b5v514A544V4=433i3K0l3N0D3o3;4%5I5f4z4.4B4;575P0l3-5F3/5U3P2K1r2:1g2#2O0q1`2T5f4D2!1x1o2/0d2;3q5W5:4D632h0v0q0^382J5C3y6a6c565m6f0n2m0d6i5A585E3:4N4 0t0}0(0h65684~260e3k6A5Y4*0f0h0}2b1x0d0Y280f0q6G6u260|040i6T5e6I0}0J0d0N6%6Z4)4 6W0F6A0n6H4 0f0}0P0s0`6z493Q6=6V0}0U0o6A0 6}5:3S6h016d2_3I3K5i795%6k3h236m2c6o7a6j5B7j1Z5.6 1+6E3L0n7y6+6C1+0z0q0}007G747A0n7g0Y6e3h5+7f6b7o6q5P3-7l2d6p4W7U7s5V6U7C7E7x7y0I2a0!0s0v1(0K2z2a0`0d0C2C2E1~1e0q200J0n0$0n0u002W1w0r1(2B0;0n610P0v0M2E0n0s0r0r0K2D2a892A0K0n6_6{6;763r8x5I7L7N0g454S7L7T4p8D246n7Y5O8I8E6t6!4 7D3k7y2A200.1%0n6%6)1(0s8s3i0n2w841(8u0v0h0/0E7_0r0E0V6m000O0#1 0C0O0b811 0.7 0f8Y1(8#6%0y7I8z787R7b203I4r8F9g7p584r7W7n7h7q0g9k8Q6,268T7*0n7G009d2@9f6i8C4I9l8M5(8I4I9q9L7i0g9J3O8V6;7%3_0}0v6:7u0^0s0}0m9#9X018f0}5s8x759F4x8B7c3h4Z9K7S7Z8I4Z9P9}8N5n9{9U8V9$016w040h4f9+8R2|9Zae9x1+0s7w2Wai7B3_0G0}901E0d7J5f6W6Y9eaf3var042law4*ayaG6?6$6(6*aAaj0^6W0Uao3T9(040gaT5ZaDaFaOap01aIa$4y6^6`8:aJ7004aS8x9WaB9%0}0ZaY4*9.5Fa/1+aR73a?9=649G7o8C4^9|9s584^a1bc5Pbaa69V7z9,6@040ta|4 aV9*a?a8a~9:4v7J9^9i3h0j6g9m8H5nbDbf9n5PbD2L3obka79,aa0e1R1%bqagbobWak0}020u0J0RbZaq0}a#9?aPa(0}azb.a%bn8/6|b?3TaRb*01al0}206SbubmaL8$b0aQ0}0kc83Uahc4a^b a`b~bnbpa*ax0}0Hb~bsbt2=a@b/b^a-b`b6cg6Wcbcm6#bYcD6-cob3bya*bA0f5C5pbbbK8I5r8K7m9Q9tcTbN9AbPblcgckcq9)cj0}clcta8aVa{cfb/a~3m9;bz9m8C5DbEcW6r3jbJbG5C6s5.c#cua%aaa.c=b@c,c)040mcs3qd84ya!2acca)b{5Za,6{do71cJ4acLc{9_5Qc~a29M5n5ScU7XdD9RdGcZd79Va8aa2E0J8n1fdca+049!c_dy9HdA5*dCbgcS7V8LdJcX7Pd6bQcgdQ0)dTdfaXcG26c@9E640D675;625?5 1g0J5_e62R2M0O1$e30D5@750(0*0,0z04.

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

.1280136ewn-f(9[1= :7Odcokliy5.sP3r/h,b]tuSxam2;g0)84_+vp050q0c0I0M0v0u0z0m0r0u0M0z0z0l010I0v0Y010406050z0J0N0N0M0C0w040K0s0u0J0?0s0e050D0}0 11130{0Y04051j1c1m0D1j0{0q0v0X0+0-0/0;0-0e0Q0J0M0Q0c0f0Y0w0I0E1a0m0E0v0Q0E0u1O0E0I0_050$0G0u0c1v0.0:011N1P1R1P0I1X1Z1V0I0C1k1J0+160z0Y0M0e0;0O011#1x010g0(0c0e0M0N0c1V1`1|211%241Z27290_0a0m0A0C0s0Y0s0z0v190e0m0!1^0C0C0c0r2u1c2c0e1k0D1J2H1;1?1=1W0q2e1y0v0e262r1V1s1u0,1$2R2T0e0s2X1V0Y2A1k2F2H2.0|1{2v2Z222%0C100u1V0M1M2A0g0;030V0V0r2(0c1R2$0s0f0k0R3c0_0m0k1c0M2/2=0`2;2d2@1%2_2{2}2 0c3101333537392U3c3e1 040m0O3j3l1|3n2F2Q013s0M2|1k2~0E303234360!3C2%3E0f0B3g0B3K2E3m0{3O3q0;3R3T053V3X3y3Z3B2S3D3d0f0U3g0U3-1d3/3o2?1w3r0s2`3S3u3W3w3Y3A3#3 3%410x3g0x462.3:2=3P3@4g3{3z3!384m3b410b3g0b4s483;4b3?4d3t3U3v3x4A3~3a3(0o3g0o4J3M4u3p4M3Q4O4f4Q4h4S3}4l4V410T3g0T4!2G4$4a2!4)4e3^3`4i3|4k4C4;3e0i3g0i4_3N4v3=4~4P3_4R4j4B3$4E3e3d0_3d5b4{4w4*505i535k4D3(0k0k5p3i0D3k3.3M1n2,1c2X2K0q1?2P5e4B2W1t1k2+0c2-3m5H2G054B5Y2d0v0q0;342F5A3u5*5,545l5/0m2i0c5=5y563f2H5G4L4}0t0_0!0g5!5(4|220d3g68494w0g0_270v0g0V260X0c0C0z6e62220^040h6s5d4(0e0_0I0c0L6D6y4%4}6v0F680m6f5e6B040N0s0?67475I6t1%6v0S0n680{6W5#3O5;015-2=3(3G5h6,4/55403F205`5|4U6_0f6;5F3H0m746O6A0_2S1s0r0c6r6)3H764}0s0_0l6M7g6u0_0j0H6%6H2v6?0V5.413*4Q7u5}6 3*5_285{6-5?5z7x1V7274756Y3?787l7P017i047k7e6N7T0N0v0_0R7r7e6f7u7w3e437z5+7H7B4n7.6{7F6}4:6 7/3K7N7Z6z630_0d1N1Z7S822^7R7Y7m1%7V020u0I0P7X2.816I2^0G0_2h7s3P6v6x7*7T6Q6D6F0c8s5e6!888n8e0_0f8F6a3r8p048r8w896Z0_8v2:8x0_6S6U8C4(6!6$7e6(8V4v7,6/4o5:7;6@5@8.7E297{6^7@0f4p6073807O8R7Q040t8K3P7V8k3m8m8L3?8N8P8*8G0;8u8!4}6Q8Y6k9k7n040S9p8H048J8Q9h017#5p6M9b3P0r5C04030m0p2v1{0C0I2w1!0-0m242v0#0m1L0g0%9O1s7#0e0J6p0m958(8s8,1|3(4G7:8_8=3e4G8@7G8;7J9^7L3k907N8d0;64048525966P0_9+8la37U0_020Q8i993M9D5e9A047(8c7T0s6c041|0qa977048z6G9x9c016v0j9t930vay7h0_0WaL8a94aIaF0_7qar92af7Wak2Gamaz9n6V9gaEaGaS6Qac5Z7T6v0H8%4t9-8:7v8-3e4X9=7=6~8{4X9`9?9}0fa~7 a190aea.aP9ua!7f8WaRaW9y7V9wad7!7$045Ea^aD0m9.0e3(4?a 9|5~4?b4b07|8{bzb9a1aea59obkaEbdbO977jbga$aM9vaSaobsa:aX6va@48bubw3(58bA7I5~58bEbB6 b-bJba919y6Q790v7b7da*bS040ya-0_0M0Y0Y26axbu8D8Tc604aKcd8#0_9s9,b*a`7-3E8/b55~5ob=b/6 5o8~b`bc8bboaX98beaJcHaYaObRanbqb!4#a_5=cq5BcsbF8`5m3c5Ccw7?cYcUcAa27Ta52A0I0J0C1bcMazb~c07)2:0D5%5J5X5L5U1c0I5Od12N2I0M1Yc~0D5M6(0!0$0(0z04.

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

.1280136f(9[T7ol5.Ms3rBL]u}xa2;é84_+ewn-1= :dcHkiyP,/hbtqSmg0){vp050M0E0X0w0Q0j0n0K0N0j0w0n0n0J010X0Q0*010406050n0t0!0!0w0p0R040Z0i0j0t0~0i0G050U1517191b130*04051r1k1u0U1r130M0Q0)0?0^0`0|0^0G0#0t0w0#0E0H0*0R0X0V1i0K0V0Q0#0V0j1W0V0X11050.0W0j0E1D0_0{011V1X1Z1X0X1)1+1%0X0p1s1R0?1e0n0*0w0G0|0x011-1F010c0:0E0G0w0!0E1%2224291/2c1+2f2h110a0K0S0p0i0*0i0n0Q1h0G0K0,200p0p0E0N2C1k2k0G1s0U1R2P1|1~1}1(0M2m1G0Q0G2e2z1%1A1C0@1.2Z2#0G0i2)1%0*2I1s2N2P2_14232D2+2a2/0p180j1%0w1U2I0c0|030C0C0N2:0E1Z2.0i0H0I0o3k110K0I1k0w2`2}122|2l2 1/313335370E39013b3d3f3h2$3k3m27040K0x3r3t243v2N2Y013A0w341s360V383a3c3e0,3K2/3M0H0o3o0o3S2M3u133W3y0|3Z3#053%3)3G3+3J2!3L3l0H0B3o0B3^1l3`3w2~1E3z0i323!3C3(3E3*3I3-473/490k3o0k4e2_3{2}3X3 4o433H3,3g4u3j490b3o0b4A4g3|4j3~4l3B3$3D3F4I463i3:0h3o0h4R3U4C3x4U3Y4W4n4Y4p4!454t4%490A3o0A4,2O4.4i2,4;4m40424q444s4K4|3m0e3o0e513V4D3}564X414Z4r4J3.4M3m0I0$115w5j534E4=585q5b5s4L3:0I0I5y3q0U3s3_4-4h5C574G5a4#4{485v3O0I3R5O3T525S5m4F4@4H4`5d5Z3M5y3@5(5Q5*4T555-5p4^5r4$5=0I4b04645A5+4:5~594_5c5t5J4x664z5_4f5R5|305D5V6d5H5e3k4O664Q6k4B695}6p5.5W5:6f490I4)664+6y4S5l6a6C5 5/6e5I6H4~66506M6m6O6B5U6D6r624v5v5g665i6Z5{6#6o6%6R6E6T6t0x5x046|686n4k6@6c615Y6+0H0x5L6~5N5P6l6;4/6$5o745G6*5u783O0x5%7d6z714V735F5X5;770x3=6~5^7r6N7g6?7i7w6F6U3N650x4d6:2P2?0E2P2)2S0M1~2X5m4J2(1B1s7S2^3u5`1s4J7*2l0Q0M0|3c2N5J3C7;7?6`63282q0E7|6s7~2P5P7t010P110,0c7,6A2a0F3o8d870G0c8a0Q3e0C1+1^2I0n8i6=1/10040d8u7G3z110!0i0X8A542a8x0%0L7,137e7/2D7{017@2}3:3O5p8S7K6{7 2g818T7}7z1%5(0K8.0K8e8C040M7,8:870i110J8^8;0|8x0(0u8N8H0K8Z0C7^497B8Y7=8)83773=0K80827l3:9b8-8/8 88110c4l8~8j110Q9v8v0|0i8g042!9z8B3~0W110p241M955m8x8z8P9q0G9J042p9O4:9Q9Y5}8D8F9#8J110%9G8I1/8{040H9-3X0!0Q5y9)8w9+8M8P8O2{3W97993m659c9k767m4b9i8%a87yaa8,3s8/aj8_9A3Y8a9{90110fapan048E8G9S878xasayam0G9xat8x0s0s9?5m9:8}8Pal9Hau9y9 95a38V4w7`9d8!5=4xac2hae6G3m6h3Saj9q89042I0X0t0p1jaO9TaoaTaC7:aZ98aW3m6va79e9l4N8$a(b6a93:b45(a07+a2b0a40H6Jb5a!774)a%8(bo7mbm5_87a:8bat9D8:a~9.3~8l040q0m0OaG119Ra1aD110X0E0vbRbL040TaK6a9%0~8cbD3X8K9~6zb%aV243:6Wbn8*7m4~bra)7L0Hb:9o8.a{8?8n0ibY55aMc3308m8o8q1|0E8tb%9PbMataEav8F0Qb$bOaQ8K94b,bjb20H6-b;9f7m5gb^bbaf3:cvb}aPbEaua_2_cG3Xc5a`8j9V9Xce9ZcgcS9$cjb#bV9,a}cn8Rcsb.6H6}cwb75v5xcAbt5Jc+cFb 2!1A0Nccc69/8|c}aq040faJaOcL7!7a030K0r361Z0nbR2Ecc960Gc`dh0w0t0v0Y0t3g0=0n1,1|0i0t0)2e0X0K1+0Kawcl0?0V0E0p0N0V0zcqc$96c(0G5J7ac,bc6H5Lc:b=dSah3P9p9w9Ed001cNcK9q9^110$dNbh4Db-dR6H8X3697cx5J27dYd~d`d#a.bx110F1V1+d*ciaSd-8`11020j0X0yaNeeaDcQ2ebVbNd?aQcibRbT0EcZd*9:9=cObP04cJescH8xb*4gcr7|bk3laYb_6teOe1c-5?85d$akd6bZ040Pezc eCet11eF3UeZc411eBemaQd/668^0Kbg3U5Sd^5Ja6d|b0e25vab9jcBa*3ka6cFe5ama:e82deb11e$e)cH9:020#ejel3ue.2ae@d;fkcM9D248@fw5,bQbSbUcV9*d2chaFfB4:9:0Dfhe#bVd4e=fl8|fqe-b dEcmeGb(arfJfQfG9|040seJfX870Nd80K0g24dAdp000:0K0R0K363e2Hcc2ydj24c{d=e|bieMct0Ia,f1eQ63a$f6c;6Ha,fbeYfs8=fjfTcMe(gsfCf)gvfMe:d*e@5Nb+dOe~6Hb4gff7b`0I4OeTdV5vbeaigoa/9xf!f/eDgrfr9qaMfW2Ogp9BgAf*0|gCbVf.g(e{2Oe}dQ5JbmgJgk5vbqgjdZ6HbvgSgod%eDc_8nc|g,d+110lf(0w0*0*2efAdOcf8yf(edf#hlc!gEf#gG5vb:g{h0hvb9bshy3kb|h3h4g)aRe%04g%3Pc^hJfOfL55g.aOg=8QdPgbc)6,ePgKeRczg f33kcEhFfcaQa:drexhaeIg8g?ga8)bk6|h!g|78c/h(eUh|eWhGh5h.gVfPevfFhkcTfIhaechOfPe,g(g#g+gyhR9_e^h=11fSg!8`9D9FhQc7c03eg/h@hVhu78dThxh)79hAgg7zdTgni5hNiyc~hKfPhogXaQfNiihJe;iuamhSin2aeAfPc`c2irieiccWiah;i=fHaBi_8=iWikef04hPi*8=ijhMj0i$iXcHi)hpidaIiDg@hXd_3Nd{hWh#5=7piLjm7z8XiPakgU04h:iCc#htg^497Ah}hCjDgOcCjC9nh,i5hHigiSg*iUjPhIjSiZjScij5hUjgh`ct7OjEiJf5adjq7mj%i4i6cHa:a=a@j5jN9xdjh8cdhse|0U7.1v2@1k7V1k0X7Xk62V2Q0w1*7Tk47%8O0,0.0:0n04.

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
.8594î6en{f(1: =Adockli5.js,P3r/hLbtquè}am2g0)é4_Evpà050V040D0K0k0g0o0e0p0F0s0(0k050p0o0n0d040n0s0:0S0r0d0F0F0A0d0w050B0:0=040k0K0w0w0o0p0s0d0k0W0k0p0C0K0G0H1f0|0~100k0w0K0H0g0k0r0#0=0A0e0s0I100x1s0-050w0 0(0N0@0d1B1e0A0k0A0K0e0N131K0A1M170n1V0w1x1f0L0o0+0g0u060y0o0H1S0/0;0?010V0K0p0d0p0K0V0113150?0k0h0s0e0^1 1)0O1g0k0c0P0k0j130Y06050H0r042o0r0s041_161|24141`17221}1U0b0F0k0d0e0k0V0o0w0s0+0(2e2J2I0c0k0a0k0-100+2K2I1J1L1W040c1Y2*1N132u2s052=2x1{0K2A262D0V2F0K2H2J2L2N2P2R0e1)0i2U0k0t2X2Z2L2#1e0e2(1Z1#0t2.1!2+2;2v2t2v2_04010p2|2C182 0K2G2I2K2M2O2Q0,380k0M3b0R3e2!0}3i3k2/040R3o1#3r2?2^2}010d3z163B30320H1C1m0d0L2%333H363K0k0z3Q3g3S3@2)3p1N0z3Y3q0B2=2o0B2q2?0Y0m2a2P2k0.2}2c0o0k0l0k0f2z0j2h1G012{4s0t4u3y4s0R4u3)4s0z0J252C2m2?0E0r1c0q1m1-0?2o0Y421#0y1D0N1f2l0B3l2+0k0T2L211)0=1*1q1f0A0Q0V0Q0F0Q0d1G0p00112I0F1?0v1?0A1)1y0.4%1N1A1C1E1f1c0p1@100)0d461N0k1m0s2J1K1i2S1P0U4`0u4K4a4M4O4Q0F0?.

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
.êenf( dcokli.s,/rhbtuèamg0)éxpà050D04050h0i0g0b040l050p0J0L040f0D0i0l0c0t0b0f0n0u0q0f0k0!0g0B0s0u0t0f0L0)0w0f0d0b0c0a0t0q0+0w0c0n0)0!0Z0C0Z0f0e0,0x0w0q0~0f0E0f0z0A0o0f0b0:0I0K0M0j0P0R0M0U0W0Y0!0$0(0*0f050n0}0i0c0y040L0q0c0l0b0(0h1c0w0h0t0v1e0g0u0f0x0i0t0l0d0P1E0q1G1I1v0%0f0J0x0x0`0h1O0?1:0i0x0D1R0l0n1G0;0+1+0l171g0y0w0u0h0r0b0m0P0G.

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
.e-nf(1= Odcokli.s,/rhtquamg)évpà050E04050k0l0j0a040m0h0g0g0h0b0f050s0K0M040h0q0o0A0c0o0d0o0a0h0w0x0-0v0l0x0v0a0q0h0n0_0h0K0z0E0y0t0y0o0q0l0c0`0e0M0h0j0t0l0o0^0h0F0h0A0y0x0k0u0a0B0h170v0h0t0C0x0q0$0p0h0i0c0h0a0c0t0a0A150v1I0{0y0h0E0l0$0v0o170h0J0L0N0o0W0Y0N0r1Q0x151s1E0y0D0y0c0k0-1Y0Z1#0X1Z0!1b0f1Q0?0t0~1p0t1o0a220x0c0-0C0D1G0v0:0n0|0h1m1M0-0l0k0k0x0t1I1=0a0p0W0H.

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
.en dcolisr/tuamgépC050r040s000a0i0l0c0g0a0c0d0q0e0n0g0n0p0D0r0f0m0j0c0j0q0I0h0i0a0Q0g000U0p0b0a0o0a0b0l050k0u.

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
.enf= dcoli.s,/rtuamg+xp050w04050g0h0f0a040j0e0d0e0G0u0e0b050n0B0D040m0e0g0r0o0e0h0b0e0c0r0j0p0e0i0a0e0l0r0q0)0s0r0v0j0=0i0e0D0*0Z0t0q0a0q0X0A0C0E0N0P15040k0O0y.

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
.enf docli.s,r/hLbtqèuamgéxvpC050B040p000v0h0x0f0m0i0r0o0w0a0d0g0f0w0Q0b0g0R0B0v0m0S0U0!0m0a0$0h0R0e0+0b0i0+0S0#0v0g0r0t0*0d0e0u0d0w0f0r0i0c0d0v0A0a0g0d0-0@0m0_0{0}0T0m0*0k0B0f0b0e0v0b0r0~1r0k1c0R0r0a0z1z0l0d0B0u0i1w0*121s0R190m1w1d0e0y0q0u1t0 1113150j0d0C000a0k1t0Y0d0k0a0b1w0/0%0w0)0v1H1o0d0s1G1E0+0Q1V1%0z0B0h0f0N0?0a0c0c0i0g0_0a0W1t0-1:0y2d0h0v0x1(0j050n0E.

À 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
.enf Qdcoli.s,r/hbtèuamgéxvpà050A040e0t0u0b0f0d0t0b0a0d0i0a0r0r0n0N0f0t0d0r0a0y0Y0d0M0d0g0h0n0T0l0A0h0I0d0A0u0l0d0u0W0g0u0n0u0g0r0s0T0^0R0a0I0W0V0d0v0h0r0j0c0m0d0/0(0/0l0t0i0#050)0f0a040f0j0)050o1p1r0;0h0t0n0d0l0u0z0h0j1D1q1i0v0q0j151g0b0;0a0t0r0d0f0x0{0P1D0P191b1d0d0z0a0n0@0i0u1X0n1I0Y1f1Q0g0p1-1{0H1W0B0^0i0j0w0M1D0g0Q0#0P0R121G0a0g1E1;1q0n0b0j110N0h0g0g1C0T0b281X0H1/0N1a1c0c0k1w0D.

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
.êe-nf( dcoli.s,r/Lbàtquèam;g)éxvpA050G040H0w0c0h0b0k0t0g0O0g0i0b0u0u0b0g0F0y0k0b0w0p0o0g0%0g0z0j0u0l0e0S0D0s0j0p0O0p0y0l0u0S0w0g0Y0E0Y0g0W0,0y0U0j0z0G0y0}0l0n0j0d0g0d000y0)0~100G0k0w0n0S0Z0n0b0d0n0m0g0r1a0_0w0i0-0G0p0l0d0i0l1e0-0n1n0p0p0a160h1j0i0S0x1v0v0w0Z050i0j0O040l0g020B0u0A0,1z0f140Y0C0g0c1_0d0f0/0;0e0C050q1,1.0m280J.

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
.en-fï dcoHliy.Mjs,r/BhâtquèamgGéxvpCà050I040E0s0w0h0a0f0B0z0G0f0g0F0h0B0k0B0D0a0q0f0!0k0h0z0k0F0*0K0f0I0B0s0x0l0s0X0z0X0l0h0{0i0b0b0B0|0S0g0S0I0s0F0x0s170x0a0C0a0b0x0r0f0u0i0m0a0s0c0o0i0i0s0a0c0j1y0q0I1x0k0@0a0z0x0f0l0D0b1y1t0X0S0D1g0b1a0*1F0`0l140*0g0 1i0G1i0n0f0J000)1L0q140@0s0l0b0h0l0^1H0B0H0B1m0%0S0q0z0}0$0f1z0h0v1t2c0S160e0H0a1o0y0z0l0T211{0S0x0i0z0p2u0s1%000z0b0f0q1J1H0!1g120A1z0f0?290d0i0l0q0n050t0M.

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⚓︎