Algorithme d'Ukkonen

Algorithme d'Ukkonen

Construction de l'arbre des suffixes du mot $baobab$

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

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n)$

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²) 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 $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.

À 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$

Articles connexes

• Arbre des suffixes
• Algorithme en ligne

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