Voir la source de Arbre des suffixes

{{Voir homonymes| Arbre (homonymie)}}
[[Image:Suffix tree BANANA.svg|thumb|250px|right|Arbre des suffixes pour le texte <code>BANANA</code> terminé par <code>$</code>. Les six chemins de la racine à une feuille (représentée par une boîte) correspondent aux six suffixes <code>A$</code>, <code>NA$</code>, <code>ANA$</code>, <code>NANA$</code>, <code>ANANA$</code> et <code>BANANA$</code>. Les nombres dans les boîtes donnent la position de départ du suffixe correspondant. En pointillés sont dessinés les liens suffixes.]]
En [[informatique]], un '''arbre des suffixes''' (en [[anglais]] {{lang|en|suffix tree}}) est une [[structure de données]] [[arbre (informatique)|arborescente]] contenant tous les [[Affixe|suffixe]]s d'un texte. L'arbre des suffixes est utilisé pour l'indexation de textes et la recherche de motifs, notamment en [[bio-informatique]].

== Définition ==
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 <math>(p,l)</math> qui correspond à la sous-chaîne commençant à la position <math>p</math>, de longueur <math>l</math>, 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.

== Utilisations ==

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.

=== 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 <math>m</math>, dans un texte de longueur <math>n</math> en temps <math>O(m)</math>. 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'à :
* ne plus pouvoir descendre dans l'arbre par la lettre lue, il n'y a pas d'occurrence de M dans le texte,
* avoir lu M en entier, on arrive
** sur un nœud de l'arbre ou au milieu d'une branche. Le nombre de feuilles présentes dans le sous arbre correspond au nombre d'occurrences 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 occurrences.
** sur une feuille. Il n'y a qu'une seule occurrence de M dans le texte, elle se trouve à la position indiquée par le numéro de la feuille.

=== Détection de répétitions ===
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.

=== Autres ===
Diverses autres tâches, comme détecter des [[palindrome]]s, peuvent être effectuées rapidement grâce à l'arbre des suffixes en utilisant des algorithmes de [[plus petit ancêtre commun]].

== Construction ==

Les principaux algorithmes de construction de l'arbre des suffixes sont ceux de Weiner {{harv|Weiner|1973}}, McCreight {{harv|McCreight|1976}} et Ukkonen {{harv|Ukkonen|1995}}. Ces trois algorithmes ont une [[complexité en temps]] linéaire. Asymptotiquement en moyenne, ces algorithmes nécessitent un [[complexité en espace|espace]] en <math>O(n\log n)</math> {{refnec|(en pratique de l'ordre de 12n)}}. L'algorithme d'Ukkonen a l'avantage d'être [[algorithme online|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 {{refnec|(de l'ordre de 4n)}}.

L'algorithme de {{harvsp|Farach-Colton|Ferragina|Muthukrishnan|2000}}, prend comme mesure de complexité le nombre d'appels à une mémoire externe, et est optimal selon ce point de vue.

== Voir aussi ==

* [[Trie (informatique)|Trie]]
* [[Tableau des suffixes]]

== Bibliographie ==

=== Articles ===

* {{article
 |langue=en
 | nom = McCreight
 | prénom = Edward M.
 | titre=A Space-Economical Suffix Tree Construction Algorithm
 | journal=Journal of the ACM
 | volume=23
 | numéro=2
 | année=1976
 | pages=262--272
 | url=http://doi.acm.org/10.1145/321941.321946
}}

* {{article
 |langue=en
 | nom =  Ukkonen
 | prénom = Esko
 | titre = On-line construction of suffix trees
 | journal = [[Algorithmica]]
 | volume = 14
 | numéro = 3
 | année = 1995
 | pages = 249--260
 | url = http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
}}

* {{chapitre
 | langue = en
 | nom = Weiner 
 | prénom = P.
 | titre chapitre = Linear pattern matching algorithms
 | passage = 1-11
 | titre ouvrage = [[Symposium on Foundations of Computer Science|14th Annual IEEE Symposium on Switching and Automata Theory]]
 | année = 1973
 | doi = 10.1109/SWAT.1973.13
}}.

*{{article
 | nom1 = Farach-Colton | prénom1 = Martin
 | nom2 = Ferragina | prénom2 = Paolo
 | nom3 = Muthukrishnan | prénom3 = S.
 | titre = On the sorting-complexity of suffix tree construction.
 | périodique = Journal of the ACM | lien périodique = Journal of the ACM
 | numéro = 6  | volume = 47 | passage = 987-1011
 | année = 2000
 | doi = 10.1145/355541.355547}}.

=== Ouvrages ===

*{{Ouvrage
 | langue=en
 | auteur1=[[Dan Gusfield]]
 | titre=Algorithms on Strings, Trees and Sequences
 | sous-titre=Computer Science and Computational Biology
 | lieu=Cambridge
 | éditeur=[[Cambridge University Press]]
 | année=1999
 | pages totales=534
 | isbn=978-0-521-58519-4
 | isbn10=0-521-58519-8
 | bnf=37532677
}}.

== Notes et références ==
<references/>

== Liens externes ==
{{Autres projets|commons=Category:Suffix tree}}
* [http://www-desir.lip6.fr/~herpsonc/uploads/Arbres-de-Suffixes-Suffix-Tree-Construction-Herpson2008.pdf Construction d'arbres de suffixes] Introduction à la construction et à l'utilisation d'arbres de suffixes, présentation et comparaison des algorithmes de Ukkonen et de Hunt avec l'approche TDD.

* [http://www.iro.umontreal.ca/~hamelsyl/ArbresSuffixes2012.pdf Présentation] générale et approfondie des arbres des suffixes. Université de Montréal. 

{{Palette Algorithmes de manipulation de texte}}
{{Palette|Arbres informatiques}}
{{Portail|Informatique théorique|Linguistique}}

[[Catégorie:Arbre (structure de données)]]
[[Catégorie:Algorithme sur les chaînes de caractères]]