Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre des suffixes
Résumé
En informatique, un arbre des suffixes (en anglais suffix tree) est une structure de données arborescente contenant tous les suffixes d'un texte. L'arbre des suffixes est utilisé pour l'indexation de textes et la recherche de motifs, notamment en bio-informatique.
On suppose que l'on s’intéresse à un texte, au sens informatique, c'est-à-dire une suite de caractères. Un suffixe est une partie du texte : la suite des caractères entre une certaine position et la fin du texte. L'arbre des suffixes est une structure pour stocker un ensemble de suffixes.
L'arbre a les propriétés suivantes :
Les feuilles de l'arbre contiennent un numéro qui correspond à la position de début du suffixe dans le texte.
Les branches peuvent être étiquetées de différentes manières :
par une chaîne de caractères de longueur supérieure ou égale à 1,
par un couple qui correspond à la sous-chaîne commençant à la position , de longueur , dans le texte.
En général, on termine le texte par un caractère spécial $ (non présent dans le reste du texte), pour éviter que certains suffixes se terminent sur des nœuds de l'arbre.
On peut parler d'arbre compact des suffixes, si :
chaque nœud a au moins deux fils,
toutes les étiquettes des branches sortant d'un même nœud commencent par une lettre différente.
L'arbre des suffixes est une structure assez naturelle et peut être utilisée pour résoudre un grand nombre de problèmes en temps linéaire. L'un des problèmes les plus classiques est la recherche de motifs.
L'arbre des suffixes est très utilisé comme structure d'indexation. En effet, il permet, de rechercher un motif M, de longueur , dans un texte de longueur en temps . Ainsi, la recherche prend un temps qui dépend uniquement de la longueur du motif.
La recherche de motifs est relativement simple. En partant de la racine de l'arbre, il faut suivre la branche dont l'étiquette commence comme M. En suivant cette branche on arrive alors à un nouveau nœud et on recommence le processus sur la partie restante de M.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.