Canal-U

Mon compte
Inria

3.6. L’algorithme de Boyer-Moore


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/3_6_l_algorithme_de_boyer_moore.24590?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
RECHENMANN Francois
PARMENTELAT Thierry

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

3.6. L’algorithme de Boyer-Moore

Vous avez compris que la recherche de motifs, c'est-à-dire de sous-chaînes de caractères dans une chaîne plus importante, était un composant important de beaucoup d'algorithmes de bio-informatique. Les algorithmiciens ont toujours cette obsession de l'efficacité de leurs algorithmes. Pourquoi ? Parce qu'on travaille sur des textes qui sont assez longs, on en a vu des ordres de grandeur, et moins, on aura à faire de comparaison, plus rapide sera l'exécution de nos algorithmes. 

Donc, travailler sur l'efficacité des algorithmes de recherche de motifs est largement justifié. Regardons en effet, quelle est l'efficacité de l'algorithme qu'on appelle naïf ? Naïf au sens de : on applique l'algorithme le plus basique auquel on pourrait penser. De quoi s'agit-il ? Vous avez un motif ici de taille 6, qui est le motif à rechercher dans un texte, dans une séquence plus longue de longueur M. Comment faites-vous ? Eh bien, vous placez votre motif au début de la séquence et vous comparez : ici ça correspond, ici ça ne correspond pas. Donc, ce n'est pas la peine de continuer, j'avance mon motif d'une position. Et je refais la comparaison avec la première lettre, il n'y a pas de correspondance. J'avance. Comparaison avec la première lettre, une correspondance. Par contre ici, G et A ne sont pas en correspondance. J'avance. Ici même chose, le A "match" comme on dit avec la position courante de la séquence. Par contre, pas la lettre suivante. Donc j'avance même chose, j'avance. Ici, correspondance, correspondance, pas de correspondance. Donc j'avance et ainsi de suite jusqu'à effectivement trouver ou pas une occurrence de mon motif dans la séquence complète...

 

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 

Dans la même collection

FMSH
 
Facebook Twitter Google+
Mon Compte