Arbre des suffixes
structure de données De Wikipédia, l'encyclopédie libre
structure de données De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir Arbre (homonymie).
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.
BANANA terminé par $. Les six chemins de la racine à une feuille (représentée par une boîte) correspondent aux six suffixes A$, NA$, ANA$, NANA$, ANANA$ et BANANA$. Les nombres dans les boîtes donnent la position de départ du suffixe correspondant. En pointillés sont dessinés les liens suffixes.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 :
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 :
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. Le processus est répété jusqu'à :
Considérons un arbre compact des suffixes. Lorsqu'il y a un nœud, il a au moins deux fils. Cela signifie que la chaîne de caractères qui nous a mené à ce nœud est répétée au moins deux fois dans le texte. Ainsi, en considérant tous les nœuds de l'arbre on peut connaître toutes les répétitions dans le texte.
Diverses autres tâches, comme détecter des palindromes, peuvent être effectuées rapidement grâce à l'arbre des suffixes en utilisant des algorithmes de plus petit ancêtre commun.
Les principaux algorithmes de construction de l'arbre des suffixes sont ceux de Weiner (Weiner 1973), McCreight (McCreight 1976) et Ukkonen (Ukkonen 1995). Ces trois algorithmes ont une complexité en temps linéaire. Asymptotiquement en moyenne, ces algorithmes nécessitent un espace en (en pratique de l'ordre de 12n)[réf. nécessaire]. L'algorithme d'Ukkonen a l'avantage d'être online.
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)[réf. nécessaire].
L'algorithme de Farach-Colton, Ferragina et Muthukrishnan 2000, prend comme mesure de complexité le nombre d'appels à une mémoire externe, et est optimal selon ce point de vue.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
