Vidéo pédagogique
Notice
Sous-titrage
Sous-titre
Langue :
Français
Crédits
François Rechenmann (Intervention), Thierry Parmentelat (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/7hbe-hz24
Citer cette ressource :
François Rechenmann, Thierry Parmentelat. Inria. (2015, 1 juin). 3.7. Index et arbre des suffixes , in 3. Prédiction des gènes. [Vidéo]. Canal-U. https://doi.org/10.60527/7hbe-hz24. (Consultée le 18 septembre 2024)

3.7. Index et arbre des suffixes

Réalisation : 1 juin 2015 - Mise en ligne : 4 octobre 2016
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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...

Intervention

Dans la même collection

Avec les mêmes intervenants et intervenantes

Sur le même thème