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

.128013l(9 _4:;=vm26-uS8w.s3/]+fr7gebh[pPic05a,onkyd1x)t050T0D0X0N0J0b0u0e0K0b0N0u0u0j010X0J0H010406050u0p0l0l0N0A0S040q0P0b0p0=0P0Q050w0|0~10120`0H04051i1b1l0w1i0`0T0J0k0*0,0.0:0,0Q0C0p0N0C0D0o0H0S0X0F190e0F0J0C0F0b1N0F0X0^050#0E0b0D1u0-0/011M1O1Q1O0X1W1Y1U0X0A1j1I0*150u0H0N0Q0:0m011!1w010z0%0D0Q0N0l0D1U1_1{201$231Y26280^0a0e0I0A0P0H0P0u0J180Q0e0Z1@0A0A0D0K2t1b2b0Q1j0w1I2G1:1=1;1V0T2d1x0J0Q252q1U1r1t0+1#2Q2S0Q0P2W1U0H2z1j2E2G2-0{1`2u2Y212$0A0 0b1U0N1L2z0z0:030f0f0K2%0D1Q2#0P0o0L0o0U0^0e0U1b0N2.2;0_2:2c2?1$2^2`2|2~0D3001323436382T3b0o1~040e0m3i3k1{3m2E2P013r0N2{1j2}0F2 3133350Z3B2$3D0v3f0v3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0g3f0g3+1c3-3n2=1v3q0P2_3R3t3V3v3X3z3!3}3$3c0M3f0M432-3.2;3O3=4d3_3y3Z374j3a3c0n3f0n4p453/483;4a3s3T3u3w4x3|393D0B3f0B4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0r3f0r4X2F4Z472Z4$4b3?3^4f3`4h4z4.0o0d3f0d4?3M4s3:4{4M3@4O4g4y3#4B3d0L0^0U0L584^4t4%4}5f505h4A3D0U3e045z581m2+1b2W2J0T1=2O5b4y2V1s1j2*0D2,3l3,3L054y5T2c0J0T0:332E5y3t5#5%515i5*0e2h0D5-5w535A3+4I4`0R0^0Z0z5V2F463O0s3f625Z4_2@0z0^260J0z0f250k0D0A0u68645b0@040c6n5|2@0^0X0D0V6x6t5a4#6q0O680e6o4#0Q0^0l0P0=61445W6u1$6q0W0h680`6Q633N5,015(2;3D3F5e6$4,523~3E1 5=5@4R6:6+0w3j0e6}6H6S3;0^2R1r0K0D6m6Z3G6I4`0P0^0j6G7a216q0G0x6X6B5!5$6%0f5)3c3(4N6-5.5x7s6=275?7p5^6:7t3J6~6 6C4`6K040J7f70017c047e787I4!7K0E0^2g7m6a6T0^6s787g3q6L6N6f7#3O6U7O7J217R0o7?7W210l0J5m7l7*6#7o6(1{3D407u847w53405;7A6@4-6:887G6~7+0:5~040s1M1Y7{7$717M8t3O7R020b0X0i7T2-7V8u3P7Y047!827@7%6r7:5b7L6x6z0D8Q6D0^0W8x5b7_8!4#7~808M7|8O6W786Y2/835-7r0o4m898g6/4k8^7z288{5/4l1U6{3G7H8l7P7L0R8%7b7d9c7}7 045o8/7:7v8@4D8`7C6^8}4D8e909q8h9s946|976}8m018o8q249f7,049b7U9D8z8B0i9I3;8J8L8;8N0:6q7)9V8,8v6M6O8W4`7=9M7P0P66041{0T9R3P7-9(8+8H7i9)2@9T259}8O9Z5U999^7/9`7;8Y9?8$9,9W018)5Bab0^7`ad9#9@9Ka19X0^7kal8H7R0j8E3l8G4t6w6y6Aa86p0^0Gapan7Nat8yaj9?9aaI6q0x8.4q9l8a8@4U9p6.920o4U9u7Ba!7xa$9z969B7H9DaPaL8#9ea?6J0^9L8F9N0^0y9?ag3h9ka89m6)4/5+8a7D8}4:a(91a+4:2G9A9B9D8oa7a}a5aoa_9d7Sax3Laz8R9 1aaE8X8PbA7Ka66P9!9{8YaT45b5aWb754b9bf5355be9w8|5j55bia.a/9Cbp730J7577bHaM040taI7L0N0H0H259=bD7h7(b:72ai04akboae0QbyaQb|b`9J9%bna4ae9+c2am7Rb0br9g8*b,aF048Zb4b,b6863c5nbQbVa#cvbUa*5_5lbZb#a;b~cj1$avaOcHcfaua b19hb3aUbM8?bO5zcwcB6:cXcA8bc!5`95a:7P8o2z0X0p0AbzcNaA7M0Q7476812/0w5Y5E5S5G5P1b0X5Jd42M2H0N1Xd10w5H6Y0Z0#0%0u04.

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

.128013_4:2-.Sw3B/]+7bpPiI{o1Mtl(9 ;=vm6u8sèfrOg}àe[hHcé05a,nkydx)050)0S0y0!0s0z0K0C0W0z0!0K0K0E010y0s0q010406050K0I0G0G0!0N0(040h0v0z0I0 0v0$050l16181a1c140q04051s1l1v0l1s140)0s0F0@0_0{0}0_0$0P0I0!0P0S0f0q0(0y0U1j0C0U0s0P0U0z1X0U0y12050/0p0z0S1E0`0|011W1Y1!1Y0y1*1,1(0y0N1t1S0@1f0K0q0!0$0}0e011.1G010M0;0S0$0!0G0S1(23252a1:2d1,2g2i120a0C0r0N0v0q0v0K0s1i0$0C0-210N0N0S0W2D1l2l0$1t0l1S2Q1}1 1~1)0)2n1H0s0$2f2A1(1B1D0^1/2!2$0$0v2*1(0q2J1t2O2Q2`15242E2,2b2:0N190z1(0!1V2J0M0}030b0b0W2;0S1!2/0v0f0w3l120C0w1l0!2{2~132}2m301:323436380S3a013c3e3g3i2%3l0f28040C0e3r3t253v2O2Z013A0!351t370U393b3d3f0-3K2:3M0j3o0j3S2N3u143W3y0}3Z3#053%3)3G3+3J2#3L3m0c3o0c3@1m3_3w2 1F3z0v333!3C3(3E3*3I3-463/3m0Z3o0Z4c2`3`2~3X3~4m423H3,3h4s3k3m0H3o0H4y4e3{4h3}4j3B3$3D3F4G453j3M0o3o0o4P3U4A3x4S3Y4U4l4W4n4Y444r4#3m0J3o0J4*2P4,4g2-4/4k3 414o434q4I4`0f0B3o0B4 3V4B3|544V404X4p4H3.4K3l0Y120w0Y5h514C4:565o595q4J3M0w0w5v3q0l3s3^4+4f5A554E584Z4_473l3O0w3R5M3T505Q5k4D4=4F4^5b5X0w3;045;5y5)4.5+5n4?5p4!5:495?4b5$5O5(4R535{574@5a5r5H4v5?4x644d5P67315B5T6b5F5c0w4M5?4O6i4z5_686n5,5U5.6d3m0w4%5?4)6w4Q5j5`6A5|5-6c5G6F4|5?4~6K6k6M6z5S6B6p5 4t3l5e5?5g6X666Z6m6#6P6C6R5c0e5u046`5^6l4i6=6a5~5W6)0e5J6|5L5N6j6/4-6!5m725E6(5s0e3O7k6~6:707f5D5V5/755=0e3?6.5i7d6;7q5}7h747j610e637a6x6 4T717r6D6S3N6f0e6h7K6L7A7p4;6?6%7F3M0e6t7)7n7Y7N7C6Q6q5X0e6H7?7,527B7!7g7s6E3N6U0e6W7W3U1w2^1l2*2T0)1 2Y5k4H2)1C1t2@0S2_3u651t4H8l2m0s0)0}3d2O5H3C8s8u6^5:292r0S8A7;6)773@7M010%120-0M8n6y2b0i3o8R8L0$0M8O0s3f0b1,1_2J0K8W7o0}11040A8,7-3Y120G0v0y8=7`1:8/0+0d8n147b8q2E8z018v2~7(8y8t988B758D2h8F9e8H7j1(5$0C9p0C8S3z8O8n9r8L0v120E9v9s8.120u0Q928|0C9799253:9c8G7i9N0C8E9P7%3m5=3S9q9w8-8M120M4j9B8X120s9*9#0v8U042#9.8?0$0p120N251N9I5k8/8;949C3Y9`042q9 4.a1a9688^8`ac2b8 ag1:9y040faj0}0G0s5vao018 9194932|3W9K0b8w489O9k9QaE9S9i9U7t5s619Y9Z9qa40$9ua38L8/0TataT048_8{aV9#aXaZ9,at8/0m0m9@8}0}al9A949!9^a,ax9IaBaD0f6f5naB9l3M4vaJ2iaL7 b29oaR8L8N042J0y0I0N1ka_aSaU6xa(8r9d9L0$3M6tb3bt9f5s4Mb89j7Q5cbx5$ay8maAbzb06Hbyba7R4%bDbQ5cbO64bf8O3Eat9;9rbra=3Y8Z040k0x0Va-12a2az9#a!0y0S0*b_b:040#a;4Cae0 8Qb(3Xav9Hc5a 9a4{aFbF5X4|bTaG9V0f6UaP9pbo041B3fc05ka@cs5`8!8$8(1}0S8+c5a0b;a+a#8`0sc4b?8?aia}c9bMcb5dcdbA3M5echce6)6+cma`b)a!2#cqcBcv53cubnaW120Ta:cOcL96cQ9M6F6{bPciaM5H5ucXcUc|9n3s9Zco9-c/9/9zc,31a6a8cDaacFdiadcHc3b}0+deak12andb8?aqasdvb)0W77039J0C0K0S0N0y0C0R0C240N3fbk0s0N0Cb_b{1-0!0F2K2FcBdF0!1h0K0g0C0O2EdNdJ0)0I0C0p0v1h2Fd;a$cJ0gc8c^9Jc`bv6F8J37b4aH3l5Jd3b5e3d63vcP8Ab05!cTeb5Y9hb9c 7 ei2Qd7be9#bg0i1W1,dr3}a|2`c$3Xal020z0y0Da^eCaSdg2fb}b=bKb@12dUb|dlah12dqdzeEdtez01dx5?b}awbqd cac{3l9Xe5bzek5;embEd4e;edaQeta{040%e%c.eL8Le)5xc@eRbsegcR0waOe?bU60e`fi8IaObde a4evex0Se%a!f3e!ct12eGeIfueNbmd cE8:cGd{cKfbb)cNf69/9;250)fuc2cJb}aYeW3zfDePfIcIfK85c:04eZfO8?alduf-b)e)5Lf;e#amfTf2b}c?f^fy040EeK3ueD5*eTb`eVfFdj04fXgadmdaf 4.f/f{fwgeeX040me,g4bJf)4Be/e23lb2fheo7R0wb79TgA6rbcese d89+f|fxgiddgNdmglg4a4al0ne%f?d~fLe0fde:6seje7g(eag*bHgIaQfq9,f(2Pg5cwgMghc-9zg33Ug^68f!fY9DfHh38@dnfVh6c7a_cn8LdB12dDd,0C371}d@0F0X0C1,0CfJgZgtfc9eehbOgzcY5s6GfkgF5:bWg/gJh0319,0$c*cCgmds04d}h6a!0!0q0q2ffShadkhPeA9=f4e$gQdf12dhh$auh#g!g6h8g?95c6eYh)04gWh+1:gYh!f+ht2P5Qgv5Hclhze|0wcggEhAi8e~hIf0c%bZ0W3!1Mfth a?gPg{2bi1e-g!i76Fc!iae^cWieibc!foiid9h|g~g@iJiq01gVf{0-im0_9~hca4hf04hh2 0UdH0Wi$0C0I2Ed%cAhrf%dK2F2x2Cipiwhuc_g$gw6`g)cji~g,j0c}iHgKeu123hdGe+i4h_iy3Ne4g#hE75e9iEek76ihiihJ1:bgh9it9t04eUi^h=gbgdjzgfh|f:gTgLgSi`h`gof49;9?iOa!cq0vjbfajJje7ki d03mjXj2jZ3N3Oc#jphdeScp2KiniVjuirg1fCh-eOi2eQjJh?hsi2f,jGdcf`iOivk2f.h*j=h7jRfWcGjxkdhTeBk7b)gjjP12jIi5f*a/jci6e17(e=jhifj!3;j$7 7wjoj+j,f1ggkjf_iL3PeM8^0!0*f#khh(iOklkafv9vjqj?h~kWilj:jyj}gbb kmkTkaiQk5are*k0kYiXdC0C0t0z9S1-0Mi-dM0`0C2JdY0$dR0C2fhj2I0s0L2JksbLi|7(fgkxe|7IhDky3NfnhHgJg;04j9k)kpa)12gq5PefhwcR7UjYkCgDaKji7jgH3PkFijc1j.iTioiKj^a7j`h/abkSj lZh{jUlyhvbu7(bxiBe77)lolmg.lOlPkZh7kIg gUiskJh?l|iM9xk9m0g_kokMm4h}iRj/iUlxlOgsl*i{lEe:7?lH7RmmkBmohGeee.kuj!i9lljmidlKlp82kElubibkfEm6gfhM8#c+l)2Q8p868k888h1l0y8bmV2W2R0!1+mS0l89930-0/0;0K04.

V. Crédits⚓︎

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