Algorithme d'Ukkonen
# Algorithme d'Ukkonen

En informatique, l'algorithme d'Ukkonen construit incrémentalement en temps linéaire l'arbre des suffixes d'un mot. Cet algorithme a été proposé par Esko Ukkonen (en) en 1995. L'algorithme est essentiellement la linéarisation d'une version naïve quadratique d'un algorithme de construction de l’arbre des suffixes.

## Principe

L'algorithme d'Ukkonen lit les caractères les l'un après l'autre, en faisant grossir la structure qu'il produit, de telle sorte que, à tout instant, l'arbre obtenu est l'arbre des suffixes du préfixe lu. Cette lecture des caractères du mot, qui progresse de gauche à droite, confère à l'algorithme d'Ukkonen son incrémentalité. Dans le premier algorithme de construction de l’arbre des suffixes, proposé par Peter Weiner, celui-ci lit le mot du dernier caractère au premier, produisant les arbres des suffixes, du plus petit suffixe du mot donné au plus grand suffixe du mot (c'est-à-dire le mot lui-même). Edward M. McCreight propose plus tard un algorithme plus simple, allant toujours de droite à gauche dans la lecture du mot. Dans sa présentation, Esko Ukkonen propose d'abord sa version quadratique incrémentale de gauche à droite qu'il linéarise ensuite.

L'implémentation naïve de la construction d'un arbre de suffixes en lisant le mot du début à la fin requiert une complexité temporelle O $(n^2)$ voire $O(n^3)$ en notation de Landau, où n est la longueur de la chaîne. En exploitant un certain nombre de techniques algorithmiques, l'algorithme d'Ukkonen réduit ce temps à O(n) (linéaire), pour les alphabets de taille constante, et O(n log n) en général, correspondant aux performances d'exécution des deux précédents algorithmes.

## Exemple

Explicitons l'exécution sur le mot $baobab$. L'algorithme part de l'arbre ne contenant qu'une racine. Lisons les lettres de $baobab$ de gauche à droite.

Étape 1 : insertion de $b$ dans l'arbre.

Comme aucune arête partant de la racine n'est étiquetée par $b$, on construit un nœud correspondant au suffixe $b$. À ce stade, on a construit un arbre suffixe correspondant au mot $b$ dont le seul suffixe est $b$.

Étape 2 : insertion de $a$ dans l'arbre.

À ce stade, le mot entier considéré est $ba$. Le suffixe $b$ devient $ba$ et on ajoute le suffixe $a$ dans l'arbre.

Étape 3 : insertion de $o$ dans l'arbre.

À ce stade, le mot entier considéré est $bao$. Comme précédemment, on met à jour les suffixes $ba$ et $a$ qui deviennent respectivement $bao$ et $ao$ puis on ajoute $o$ comme suffixe.

Étape 4 : insertion de $b$ dans l'arbre.

À ce stade, le mot entier considéré est $baob$. On met à jour les suffixes $bao$, $ao$ et $o$ qui deviennent respectivement $baob$, $aob$ et $ob$. En revanche, il n'est pas nécessaire d'insérer le suffixe $b$ qui est déjà présent dans l'arbre via l'arête $baob$. (on retient maintenant que les prochaines modifications vont avoir lieu sur l'arête $baob$, et que le plus long préfixe commun est $b$. On garde ces informations).

Étape 5 : insertion de $a$ (mot considéré est $baoba$) :

L'arête courante est $baob$, dont $ba$ est toujours le préfixe. Il suffit donc de mettre à jour les suffixes $baob$, $aob$ et $ob$ qui deviennent $baoba$, $aoba$ et $oba$. Le plus long préfixe commun devient $ba$.

Étape 6 insertion de $b$ (mot considéré est $baobab$) :

Les suffixes $baoba$, $aoba$ et $oba$ deviennent $baobab$, $aobab$ et $obab$. En revanche, le suffixe $bab$ n'est plus préfixe de $baobab$. Il faut scinder l'arête $baobab$ après $ba$ qui est le plus long préfixe commun.

* Étape 6.1 : on insère un nœud entre $ba$ et $obab$, puis on rajoute une arête $b$ partant de ce nœud (on a introduit un branchement). On a ainsi ajouté les suffixes $baobab$ et $bab$ dans l'arbre. Il reste à traiter les suffixes $ab$ et $b$.
* Étape 6.2 : le suffixe $ab$ a comme plus long préfixe commun $a$ avec l'arête $aobab$. On sépare donc l'arête $aobab$ en insérant un nœud entre $a$ et $obab$. On ajoute également une arête $b$ partant de ce nœud
* Étape 6.3 : le suffixe $b$ a comme plus long préfixe $b$ avec l'arête $ba$. On insère donc encore un nœud entre $b$ et $a$ sur l'arête $ba$
