Arbre des suffixes
Un article de Wikipédia, l'encyclopédie libre.
En informatique, un arbre des suffixes est une structure de données en forme d'arbre qui contient tous les suffixes d'un texte.
Sommaire |
[modifier] Définition
Soit un texte dont on veut construire l'arbre des suffixes. L'arbre a les propriétés suivantes :
- Les feuilles de l'arbre contiennent un numéro qui correpond à la position de début du suffixe dans le texte.
- Les branches peuvent être étiquetées de différentes manières :
- par une seule lettre
- par une chaîne de caractères de longueur supérieure ou égale à 1
- par un couple (p,l) qui correpond à la sous chaîne commençant à la position p, de longueur l, 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 noeuds de l'arbre.
On peut parler d'arbre compact des suffixes, si :
- chaque noeud a au moins deux fils,
- toutes les étiquettes des branches sortant d'un même noeud commencent par une lettre différente.
[modifier] Utilisations
[modifier] 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 m, dans un texte de longueur n en temps O(m). Ainsi, la recherche prend un temps qui dépend de la longueur du motif et non du texte.
La recherche de motifs est assez facile, il suffit de lire le motif et de descendre en même temps dans l'arbre (avec les lettres lues). Plusieurs cas se présentent alors
- on ne peut pas descendre dans l'arbre par la lettre lue, il n'y a pas d'occurence de M dans le texte,
- après avoir lu M en entier, on arrive
- sur un noeud de l'arbre ou au milieu d'une branche. Le nombre de feuilles présentes dans le sous arbre correspond au nombre d'occurences de M dans le texte. De plus chaque feuille contenant la position du début de suffixe, on peut déterminer la position de chacune des occurences.
- sur une feuille. Il n'y a qu'une seule occurence de M dans le texte, elle se trouve à la position indiquée par le numéro de la feuille.
[modifier] Détection de répétitions
Considérons un arbre compact des suffixes. Lorsqu'il y a un noeud, il a au moins deux fils. Cela signifie que la chaîne de caractères qui nous a menée à ce noeud est répétée au moins deux fois dans le texte. Ainsi, en considérant tous les noeuds de l'arbre on peut connaître toutes les répétitions dans le texte.
[modifier] Construction
La construction de l'arbre des suffixes, sur un texte de longueur n, peut être effectuée en temps O(n)[1][2], dans un espace O(nlogn) (en pratique de l'ordre de 12n) L'espace utilisé par une telle méthode peut être un problème pour indexer des textes très longs (centaines de Mo à quelques Go). D'autres méthodes existent afin de réduire l'espace mémoire nécessaire aux structures d'indexation. La table des suffixes en est un exemple, bien que l'espace requis puisse être trop important (de l'ordre de 4n). De nouvelles méthodes consistant à compacter ou compresser les structures font leur apparition et sont encore l'objet de recherches de nos jours.
