Algorithme d'Ukkonen

Complexité en temps
Découvreur ou inventeur	Esko Ukkonen (en)
Date de découverte	1995
Problème lié	Recherche des suffixes dans une chaîne de caractères
Structure des données	arbre
Pire cas	O(nlog⁡n)
Moyenne	O(n)

En informatique, plus précisément en algorithmique du texte, 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^[1]. 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 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)^[2]. Edward M. McCreight propose plus tard un algorithme plus simple, allant toujours de droite à gauche dans la lecture du mot^[3]. 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²) voire O(n³) 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 $b a o b a b$ . L'algorithme part de l'arbre ne contenant qu'une racine. Lisons les lettres de $b a o b a b$ de gauche à droite.

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

Comme aucun arc 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 $b a$ . Le suffixe $b$ devient $b a$ 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 $b a o$ . Comme précédemment, on met à jour les suffixes $b a$ et $a$ qui deviennent respectivement $b a o$ et $a o$ puis on ajoute $o$ comme suffixe.

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

À ce stade, le mot entier considéré est $b a o b$ . On met à jour les suffixes $b a o$ , $a o$ et $o$ qui deviennent respectivement $b a o b$ , $a o b$ et $o b$ . 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 $b a o b$ . On retient maintenant que les prochaines modifications vont avoir lieu sur l'arête $b a o b$ , et que le plus long préfixe commun est $b$ .

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

L'arête courante est $b a o b$ , dont $b a$ est toujours le préfixe. Il suffit donc de mettre à jour les suffixes $b a o b$ , $a o b$ et $o b$ qui deviennent $b a o b a$ , $a o b a$ et $o b a$ . Le plus long préfixe commun devient $b a$ .

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

Les suffixes $b a o b a$ , $a o b a$ et $o b a$ deviennent $b a o b a b$ , $a o b a b$ et $o b a b$ . En revanche, le suffixe $b a b$ n'est plus préfixe de $b a o b a b$ . Il faut scinder l'arête $b a o b a b$ après $b a$ qui est le plus long préfixe commun.

Étape 6.1 : on insère un nœud entre $b a$ et $o b a b$ , puis on rajoute une arête $b$ partant de ce nœud (on a introduit un branchement). On a ainsi ajouté les suffixes $b a o b a b$ et $b a b$ dans l'arbre. Il reste à traiter les suffixes $a b$ et $b$ .
Étape 6.2 : le suffixe $a b$ a comme plus long préfixe commun $a$ avec l'arête $a o b a b$ . On sépare donc l'arête $a o b a b$ en insérant un nœud entre $a$ et $o b a b$ . 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 $b a$ . On insère donc encore un nœud entre $b$ et $a$ sur l'arête $b a$

Articles connexes

Bibliographie

↑ (en) E. Ukkonen, « On-line construction of suffix trees », Algorithmica, vol. 14, n^o 3,‎ 1995, p. 249–260 (DOI 10.1007/BF01206331, lire en ligne)
↑ (en) Peter Weiner, 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), 1973, 1–11 p. (DOI 10.1109/SWAT.1973.13), « Linear pattern matching algorithms »
↑ (en) Edward Meyers McCreight, « A Space-Economical Suffix Tree Construction Algorithm », Journal of the ACM, vol. 23, n^o 2,‎ 1976, p. 262–272 (DOI 10.1145/321941.321946)

Liens externes

Explication détaillée en anglais
Recherche rapide de chaînes avec des arbres de suffixes Tutoriel de Mark Nelson. Présente un exemple d'implémentation écrit en C++.
Implémentation en C avec explication détaillée
Diapositives de la conférence de Guy Blelloch
Page d'accueil d'Ukkonen
Projet d'indexation de texte (construction en temps linéaire d'Ukkonen d'arbres de suffixes)
Implémentation en C Partie 1 Partie 2 Partie 3 Partie 4 Partie 5 Partie 6

Portail de l'informatique théorique

[1] (en) E. Ukkonen, « On-line construction of suffix trees », Algorithmica, vol. 14, n^o 3,‎ 1995, p. 249–260 (DOI 10.1007/BF01206331, lire en ligne)

[2] (en) Peter Weiner, 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), 1973, 1–11 p. (DOI 10.1109/SWAT.1973.13), « Linear pattern matching algorithms »

[3] (en) Edward Meyers McCreight, « A Space-Economical Suffix Tree Construction Algorithm », Journal of the ACM, vol. 23, n^o 2,‎ 1976, p. 262–272 (DOI 10.1145/321941.321946)

[1]

[2]

[3]

Complexité en temps
Pire cas	$O (n \log n)$
Moyenne	$O (n)$