Aller au contenu

Boyer Moore

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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kg[: r);S/(.lo4y,6b=ac1x5+ud3t28_Pw7evp-fh09mn]is050C0L0E0v0W0n0X0f0w0n0v0X0X0u010E0W0N010406050X0B0T0T0v0g0q040j0o0n0B0=0o0U050k0|0~10120`0N04051i1b1l0k1i0`0C0W0M0*0,0.0:0,0U0c0B0v0c0L0O0N0q0E0Q190f0Q0W0c0Q0n1N0Q0E0^050#0t0n0L1u0-0/011M1O1Q1O0E1W1Y1U0E0g1j1I0*150X0N0v0U0:0F011!1w010P0%0L0U0v0T0L1U1_1{201$231Y26280^0a0f0I0g0o0N0o0X0W180U0f0Z1@0g0g0L0w2t1b2b0U1j0k1I2G1:1=1;1V0C2d1x0W0U252q1U1r1t0+1#2Q2S0U0o2W1U0N2z1j2E2G2-0{1`2u2Y212$0g0 0n1U0v1L2z0P0:030H0H0w2%0L1Q2#0o0O0R0O0x0^0f0x1b0v2.2;0_2:2c2?1$2^2`2|2~0L3001323436382T3b0O1~040f0F3i3k1{3m2E2P013r0v2{1j2}0Q2 3133350Z3B2$3D0D3f0D3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0p3f0p3+1c3-3n2=1v3q0o2_3R3t3V3v3X3z3!3}3$3c0z3f0z432-3.2;3O3=4d3_3y3Z374j3a3c0s3f0s4p453/483;4a3s3T3u3w4x3|393D0K3f0K4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0G3f0G4X2F4Z472Z4$4b3?3^4f3`4h4z4.0O0S3f0S4?3M4s3:4{4M3@4O4g4y3#4B3d0R0^0x0R584^4t4%4}5f505h4A3D0x3e045z581m2+1b2W2J0C1=2O5b4y2V1s1j2*0L2,3l3,3L054y5T2c0W0C0:332E5y3t5#5%515i5*0f2h0L5-5w535A3+4I4`0b0^0Z0P5V2F0f464t0P0^260W0P0H250M0L0g0X625Z4_210@040l6i655b0U0^0E0L0y6u6p5|6l0^0r6i646z3q0^0T0o0=61445W6F0:6m0h0e6i0`6M2F655,015(2;3D3F5e6Y4,523~3E1 5=5@4R6,6%0k3j0f6_6E5a4#6s042R1r0w0L6h6V3G6q4#0o0^0u6D774`6m0d0V6T6y4s6)0H5)3c3(4N7l5^6,3(5;275?6Z5.5x7o1U6@3G6`7d2@0^0W7c6O0179047b756{4!4`0U0t0^2g7j7S6A6n7Y6k6G046I6K7$3O6Q7K6|4`7N0O7/7Z1$0T0W5m7i756X5$7y7n0O407q806*5/3 6.7w6:4-6,843J6`7R7%0:5~040J1M1Y7@8j3P7I8q3O7N020n0E0i7P2-8i4t7V047X7~7L6m6o8I7:7H046u6w0L7,5b7.7Q7G1$7=8u5b7`7|8M7^6P0^6S756U2/3N7l824m858c6+4k0O4m7v288^888{7C6^8h7F7L6~0b8!787a994`8$045o8-7,8;6#4C5+867z534D8}7x877A0O4D2G93948D5b8l8n249c8O988W7L8w8y0i9F3q8F8H8/8N1$8K8T6}6H6J6a9V7e0^0h9N0:0o0J0^1{0C9(8s7)9Y6L9R8)017f9!2@9P259{9T0^8L9@8r6~7*9Z8(8r8V8C8X9)0^7?9I9S0:9e3hag9^8Zala40^9Ha37-0^7hao8v7a8B3l9A9W8P6v6xa8at040d9 3;8taw5banab96aqaK9_au8,4q9i9n824U8@7y7s8`4U9r8 9ua#8g9z94ac9:araAa=7Naz3LaB7TaSaN9a040A9/aj7}as9j1{3D4:a$9t534:a+a%6;8`bba/9za=8la7aQaha?9/a`a{63a=7U7W9~aG8Ua1aTa59=aT6QaW45aGb80U3D55bc9o6,55bgbdbS927Ea:95br6~700W7274asaO0^0mbE9,0N0N259.bB4#9Ub^a~6 btae9/by8GbAb+b_bDb{8Oa69?5U8J9$b~b2b47{5BbHcd9hbLaZ9k5k9ma,5_5lbUbR8`5nbXbZbxaMbqam9bb0b|7JcF217Nb3cI7_chakaXcm5-825zcqbh8dcw3ecua(5jcU9xbYa}218l2z0E0B0g1acMaL6 0U7173b65U0k5Y5E5S5G5P1b0E5Jd32M2H0v1Xd00k5H6U0Z0#0%0X04.

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

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

utiliser un prétraitement du motif pour déterminer les décalages

On va d'abord coder une fonction dico_lettres qui renvoie un dictionnaire associant à chaque lettre de mot (paramètre d'entrée) son dernier rang dans la variable mot. On exclut la dernière lettre, qui poserait un problème lors du décalage (on décalerait de 0...)

Dans l'exemple suivant :

Etape 0 :

étape 0

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

Etape 1 :

  • i prend la valeur 5 c'est à dire len(motif) - 1
  • "d" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire de len(motif)

étape 1

Etape 2 :

  • i prend la valeur 5 + 6 c'est à dire de i + decalage
  • dico["n"] = 4, on va faire un décalage de 5 - 4, c'est à dire de len(motif) - 1 - dico["n"]

étape 2

Etape 3 :

  • i prend la valeur 11 + 1 c'est à dire de i + decalage
  • On a concordance pour la lettre "g", on vérifie la concordance des lettres en partant vers la gauche,
    donc pour les indices i - k, k augmentant de 1 à chaque nouvelle comparaison. On observe qu'il n'y a plus concordance lorsque i - k = 8 .
  • "p" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire len(motif) à partir de l'indice où l'on se trouve.
    i prendra la valeur 8 + 6 = 14, c'est à dire que i prend la valeur i - k + len(motif)

étape 3

Etape 4 :

  • i prend la valeur 14
  • dico["s"] = 0, on va faire un décalage de 5 - 0 = 5, c'est à dire len(motif) - 1 - dico["s"]

étape 4

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

Compléter ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013g[ r);/(Blo4,6Ib=ax+5utM}P7e{-h0mnk:Sé.èy1cd32à8_wvpfHO9]is050S0C0x0s0*0k0+0d0R0k0s0+0+0r010x0*0!010406050+0w0H0H0s0e0P040L0l0k0w0 0l0I050h16181a1c140!04051s1l1v0h1s140S0*0Z0@0_0{0}0_0I0b0w0s0b0C0E0!0P0x0F1j0d0F0*0b0F0k1X0F0x12050/0q0k0C1E0`0|011W1Y1!1Y0x1*1,1(0x0e1t1S0@1f0+0!0s0I0}0U011.1G010#0;0C0I0s0H0C1(23252a1:2d1,2g2i120a0d0A0e0l0!0l0+0*1i0I0d0-210e0e0C0R2D1l2l0I1t0h1S2Q1}1 1~1)0S2n1H0*0I2f2A1(1B1D0^1/2!2$0I0l2*1(0!2J1t2O2Q2`15242E2,2b2:0e190k1(0s1V2J0#0}030X0X0R2;0C1!2/0l0E0Q3l120d0Q1l0s2{2~132}2m301:323436380C3a013c3e3g3i2%3l0E28040d0U3r3t253v2O2Z013A0s351t370F393b3d3f0-3K2:3M0T3o0T3S2N3u143W3y0}3Z3#053%3)3G3+3J2#3L3m0m3o0m3@1m3_3w2 1F3z0l333!3C3(3E3*3I3-463/3m0v3o0v4c2`3`2~3X3~4m423H3,3h4s3k3m0o3o0o4y4e3{4h3}4j3B3$3D3F4G453j3M0B3o0B4P3U4A3x4S3Y4U4l4W4n4Y444r4#3m0W3o0W4*2P4,4g2-4/4k3 414o434q4I4`0E0(3o0(4 3V4B3|544V404X4p4H3.4K3l0G120Q0G5h514C4:565o595q4J3M0Q0Q5v3q0h3s3^4+4f5A554E584Z4_473l3O0Q3R5M3T505Q5k4D4=4F4^5b5X0Q3;045;5y5)4.5+5n4?5p4!5:495?4b5$5O5(4R535{574@5a5r5H4v5?4x644d5P67315B5T6b5F5c0Q4M5?4O6i4z5_686n5,5U5.6d3m0Q4%5?4)6w4Q5j5`6A5|5-6c5G6F4|5?4~6K6k6M6z5S6B6p5 4t3l5e5?5g6X666Z6m6#6P6C6R5c0U5u046`5^6l4i6=6a5~5W6)0U5J6|5L5N6j6/4-6!5m725E6(5s0U3O7k6~6:707f5D5V5/755=0U3?6.5i7d6;7q5}7h747j610U637a6x6 4T717r6D6S3N6f0U6h7K6L7A7p4;6?6%7F3M0U6t7)7n7Y7N7C6Q6q5X0U6H7?7,527B7!7g7s6E3N6U0U6W7W3U1w2^1l2*2T0S1 2Y5k4H2)1C1t2@0C2_3u651t4H8l2m0*0S0}3d2O5H3C8s8u6^5:292r0C8A7;6)773@7M010J120-0#8n0d6y310#8O0*3f0X1,1_2J0+8n8T1:11040i8(8L0I120H0l0x8.7o0}8+0f0K8n147b8q2E8z018v2~7(8y8t948B758D2h8F9a8H7j1(5$0d9l8S8/8O8R8)0}0l120r9q8L8+0D0z8~8^8r9995253:988G7i9H0d8E9J7%3m5=3S9m9n8_8M120#4j9w9V8:040*9!7-010l0Y122#9)7`3z0q120e251N9C9;8`128-909r3Y9?042q9{3X8+9 2|9o048=8@a09x120fa65k9t040Eaj4.0H0*5vao538{8}908 aa4B939F0I3M615naB9b5s499M9e9O7taJ9j3s9T9Ta19$0Sat2b8+0caX3z8;8?a#9}04a!af9#9.a)018+0)0)9:3Xal9v909U9*9$9(axa6aH8w4u9I9g9Kb5aL2iaN7 6f9S9ma18N042J0x0w0e1ka|aU9pb1a-9D8Ab40E6taG9EaI3M4Mba9f7Q5cby5$ay8m3Wb3963m6Hbzbc7R4%bEbS5cbQ648Lbi8Pa^5*8V040j0y0$a:a8a:9$0x0C0tb=b.120nb%5`a%0 8Qbt9|a;ahaw6xc10dbN9G4{b6bG5X4|bVb79P0E6Ubf9lbq041B3fb|53a`cr318W8Y8!1}0C8%c75kb/cCb}ac8?0*c0az9*8{9Bc7c9aD3m6+bRchaO3M5ecgcd6)cT9kbgab2#cpcAcu1:ctbpaga+a@bscL92bAbw5wccbB6F5ucZc~5taQ3Pc(a.9%c-9s9ud9a212a5cFau9~b:b~cJb_04aic:9Valandp9*aqasdtc20R7703c80d0+0C0e0x0d0V0d240e3fbm0*0e0db=b@1-0s0Z2K2FcAdD0s1h0+0N0d0%2EdLdH0S0w0d0q0l1h2Fd/adcJ0NcOc^c8c`bO3l8J37aH9h5H5Jd1e56F8JbJb2d ca5Yc}e9ege8b8eg2QaRd69*bi0Y1W1,dca dcal020k0x0ga{2`a}c20Ia3dfd}cDdidgcv04dSb^eN8*ahex12dseEa1dv5?dmc54ecPeecR3l9Re3bAei5;9dbbcV7 e;end5aSeF4C120JeV04eD3ue}5ke!5xc@bLaAe*5HaFe.bW60e=bFd20QaFc%e|bh12es2eeve f1ezeBeveI2fdma9faa~dkcKfDc2cNdxa_9-0425aWfK5*fFdma,eK5`fzbofVdh8,djcHb dmdoeY8Ldrdce!5Lf+dqeWft04f0eSa*c?f;9*a`f33Uf5cGeQ0CfTf$b0f}c2f-fQcGf_fZaY120)e%g1bK85bMfc6Fbeffe@7R0Q4vekcigud4e|foabgef4a1c/g9e~f^f10uf.are#f9gmfbbve06sehelgUgwcW6FbIeogB9Vbidlgc68fug+2bf fydefAf`c3f#g@9$d_fGgQcMc48Rcm8Ldz12dBd*0d371}d=0Z0M0d1,0dg|d|fHd~gSef6GgVgxbU9Ngs6rbYg$gAh2d7c*8Xc,g@ald{g`120s0!0!2ffPgfeTg_hM3}a/g.c.f?hS3}fXfBf$hhg@fJgHak12gLhV01f/f)hig~c_hle+0Qckgrc!5sh@fifg8Ickfnhwg2g,co2K3!1Mg5h+gGgE8Lh-gP2P5QcQ5HcTh_fkcYhrh`ijgzi2hxfEd8iadbh+ewiw04h*h%cG0-0Ri79`a|i32bh404h62 0FdF0RiQ0d0w2Ed#czhgcI0#dI2F2x2Ci9c6d}ii3m6`hogZ3Nd0iod2i/e`hwfp043hdEe$h/iggnh=7(e2hkhs7=e7i@ei76irisi|g*iDi4g4g6hFivjig/hUjoa$gJh#ghexfM9/iycw0lj0if91j7aC7(3OcUipi.28gY7 7kjeisepeG8Oi60_iIjrdaf2g;a4g?hPg^fCh:gIh!j(h$icf=amgMdwjY9+jqj:iucpjBjua+f$jkj fUhjfRjnj{gaj`g1cngDj+eL04a?j1jEi-3Ne-jFi^3;jN7R7wjQjRiKjsg8k8a_ixj^eH8;0s0thYjmkxkbf,ka2PkvhQjteEkNj_iBf@iFiHi*k54.8+b{jzk7kJj;iCkyf6gNf:kYf!f*f4kRiMdB0p0k9M1-0#iXdK0`0d2JdW0IdP0d2fh82I0*0O2Jkiihgo3NfeknjcaKjbel7IktgAi|i~kXkekZ12gj5(e)j4i.gqlilmgvllci7UlojfabkVjWlskMgFkAk+fWg=fYk/gghOlVjsj-lYa*k;5Ply9abw7)i:jObDlFi;l,i`kujSgIkIlOkKj!k$l`3PlPj=k$kdl{k)kUjVi8h1glj2gRl*e07?l-krhqaMj875hu3vl)jGi.h^lClGcfl:jOi0hvi|bkbmlUk(iuhz0RhBi+8m0h8p868k888h1l0x8bmR2W2R0s1+mO0h898 0-0/0;0+04.

V. Crédits⚓︎

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