Canal-U

Mon compte
Inria

3.7. Index et arbre des suffixes


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_7_index_et_arbre_des_suffixes.24586?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.7. Index et arbre des suffixes

Il y a donc deux approches pour améliorer la performance des algorithmes de recherche d'un motif dans une chaîne de caractères. La première approche consiste à pré-traiter le motif. On a vu un exemple de cette approche avec l'algorithme de Boyer-Moore. 
La deuxième approche consiste à pré-traiter le texte dans lequel nous recherchons les motifs. Et nous allons voir deux exemples de mise en oeuvre de cette approche. 
La première consiste à construire un index de mots de longueur fixe. De quoi s'agit-il ? 
Considérons cette chaîne de caractères, relativement courte ici, de longueur 14. Nous allons construire un index de tous les triplets qui apparaissent dans cette séquence. Voilà ce que ça donne. Vérifions. Ce triplet AA # ou # n'appartient pas à la séquence mais marque la fin de la séquence. On trouve bien une occurrence de ce triplet à la position 13. De même pour le triplet ACG, on trouve bien une occurrence, voire même l'occurrence, la seule de ACG à la position une, et ainsi de suite...

 

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