Table des suffixes et des plus long préfixes communs

Les structures d’indexation de suffixes ont pour principal intérêt la recherche rapide de chaînes requêtes sur un ensemble de chaînes indexées. Elles présentent également une utilité pour la recherche de chaînes répétées. À l’origine celles-ci ont été utilisées pour la manipulation de séquences biologiques ou pour la recherche de facteurs requêtes sur du texte en langue naturelle. Elles ont ensuite également été employées par certaines implantations d’outil de recherche de similarité sur du code source (ou sur du langage naturel [132]). Nous pouvons ainsi citer Phoenix [78] et CCFinder [71, 89] qui réalisent une recherche de facteurs répétés par table ou arbre de suffixes sur des chaînes issues de la lexémisation de code source. Dans [72], Koschke et al. proposent une approche équivalente en travaillant sur une représentation par arbre de syntaxe abstrait qui est ensuite transformé en chaîne de lexèmes par parcours de l’arbre. Une recherche de facteurs répétés est ensuite réalisée après construction d’un arbre de suffixes.

Nous décrivons dans le chapitre 7 une méthode de factorisation de fonctions représentées par des chaînes de lexèmes utilisant une table de suffixes pour la détermination des facteurs factoriser et externaliser. Enfin dans le chapitre 10, une méthode d’extension de correspon-dances sur empreintes de sous-arbres de syntaxe abstraits utilisant une structure de table de suffixes est développée. Celle-ci permet de retrouver des chaînes d’arbres frères similaires au sein d’arbres de syntaxe en évitant la lexémisation complète de ces arbres telle qu’elle est effectuée dans [72].

Définition 6.4. (Arbre de suffixes) L’arbre des suffixes ST (T ) des chaînes de lexèmes T est l’arbre de racine ǫ dont les nœuds sont étiquetés par des facteurs de T et dont :

1. L’ensemble des chemins (concaténation des étiquettes des nœuds) est homomorphe à l’ensemble des facteurs de T .

2. L’ensemble des chemins terminés par un nœud terminal est homomorphe à l’ensemble des suffixes de T .

3. Chaque facteur correspond à un chemin unique.

L’arbre de suffixes de l’ensemble des chaînes de lexèmes T = {T1, . . . , Tn} est l’arbre lexi-cographique construit à partir de l’ensemble des suffixes de T . Un tel arbre représentant L suffixes est composé dans le pire des cas de L(L+1) + 1 nœuds si tous les facteurs sont distincts.

En pratique, seuls les nœuds internes d’arité sortante d’au moins 2 ne représentant pas une occurrence de suffixe sont conservés en fusionnant les chaînes de nœuds non-suffixes successifs d’arité sortante unitaire. Nous obtenons ainsi l’arbre compact de suffixes de T comportant au maximum 2L−1 nœuds 1. Par la suite tous les arbres de suffixes manipulés sont présumés com-pacts. Chacune des feuilles de l’arbre représente au moins un suffixe (plusieurs si les chaînes comportent plusieurs suffixes égaux) : elles sont étiquetées par les chaînes d’appartenance et les positions des suffixes.

Nous notons que pour chaque nœud a · u de l’arbre de suffixes (a ∈ Σ, u ∈ Σ∗) il existe son suffixe u : a · u est connecté à u par un lien suffixe. L’arbre de suffixes de l’exemple introduit en 6.1.1 est présenté en figure 6.1 avec les liens suffixes des seuls nœuds internes.

Différents algorithmes ont été proposés pour la construction d’un arbre de suffixes d’un ensemble de chaînes T de taille cumulée L en O(L). Une première approche naïve consiste insérer les suffixes de chaque chaîne de T dans l’ordre inverse de leur position dans un arbre lexicographique. Chaque suffixe devant être entièrement parcouru pour son insertion, cela nécessite dans le pire des cas |T | k=1 21 lk (lk + 1) recherches de caractères dans l’arbre lexi-cographique pour des chaînes de puissance d’un même lexème. Cette première approche en temps quadratique est écartée au profit de méthodes de complexité plus favorables exploitant l’existence de liens suffixes entre les nœuds [30]. En effet s’il existe un nœud étiqueté a · u (a ∈ Σ, u ∈ Σ∗) dans ST (T ) (ce qui signifie l’existence du facteur au dans T ), il existe égale-ment un nœud étiqueté u pour son suffixe direct : la forêt des nœuds enfants de u est l’union des forêts des nœuds enfants des nœuds (x · u)x∈Σ {ǫ}.

Nous décrivons ci-après succinctement un algorithme en temps linéaire proposé par Mc-Creight [36]. Parmi d’autres algorithmes de construction, nous pouvons citer l’algorithme historique de Weiner [41] ainsi que celui plus récent d’Ukkonen [40] réalisant une construc-tion incrémentale de l’arbre des suffixes. Un facteur logarithmique en la taille de l’alphabet manipulé doit être introduit dans la complexité temporelle de construction afin de trouver pour chaque nœud interne, le nœud enfant d’étiquette commençant par un lexème donné. Si l’alphabet manipulé est énumérable, l’algorithme de Farach [28] permet de s’abstraire de ce facteur logarithmique en construisant et fusionnant deux arbres de suffixes (suffixes de position paire et impaire) à l’aide d’un tri par bacs des lexèmes.

L’algorithme de McCreight [36] procède à la construction de l’arbre des suffixes compact en temps linéaire par ajout itératif des suffixes de la première à la dernière position. L’ajout du suffixe de position j d’une chaîne ti ne requiert que la seule connaissance des caractères ti [j|kj ] avec kj un nombre fini de caractères. On notera en fait que kj est défini de telle sorte que le nœud ti [j|kj − 1] existe déjà dans l’arbre2. ti [j|kj − 1] existant déjà et ayant été créé lors de l’ajout d’un suffixe précédent (suffixe ti[l..] avec ti [l|kj − 1] = ti [j|kj − 1]), le nœud de chemin ti [j + 1|kj − 2] a également été créé par l’insertion d’un suffixe précédent, ti[l + 1..] en l’occurrence. Ainsi l’ajout du suffixe ti[j + 1..] peut être réalisé en se rendant d’abord au nœud de chemin ti [j + 1|kj − 2] par le suivi du lien suffixe de ti [l|kj − 1] puis en y ajoutant autant de lexèmes que nécessaire cj+1 = kj+1 − (kj − 1) afin de créer effectivement un nouveau nœud dans l’arbre compact. La première étape est réalisée rapidement puisqu’il s’agit de suivre un lien suffixe en temps constant. Nous avons ainsi un nombre total de comparaisons linéaire j∈[1..n] cj = n).

Étant donné l’arbre de suffixes ST (T ), nous déterminons pour chacun des nœuds p :

    1. Le nombre d’occurrences de suffixes p pour lequel p est terminal, que nous notons |t(p)|.

    2. Le nombre de nœuds enfants mono-feuille de p noté |Cmono(p)|, étant précisé qu’une mono-feuille q est définie par |t(q)| = 1 et ne possède pas d’enfant.

    3. Le nombre total de nœuds enfants de p noté |C(p)|.

Nous en déduisons une taxonomie des nœuds p de l’arbre de suffixes selon leurs valeurs |t(p)|, |Cmono(p)|, |C(p)| :

    1. |C(p)| = 0 : p est une feuille

        (a) |t(p)| = 1 : p est une mono-feuille ne représentant qu’une occurrence de suffixe.

        (b) |t(p)| > 1 : p est une multi-feuille représentant plusieurs occurrences t(p) du suffixe p.

    2. |C(p)| > 0 : p est un nœud interne

        (a) |Cmono(p)| = |C(p)| : p est un nœud faiblement interne qui est le plus grand préfixe commun de ses mono-feuilles enfants Cmono(p).

        (b) |Cmono(p)| < |C(p)| : p est un nœud fortement interne.

Cette taxonomie est appliquée sur l’arbre de suffixes présenté en figure 6.1.

L’ensemble des occurrences de suffixes atteignables depuis le sous-arbre de racine p est noté suff (p) : il s’agit de tous les suffixes de T partageant le préfixe commun p.

Nous notons que les nœuds n’étant pas des mono-feuilles représentent des facteurs répétés non-extensibles sur la droite. Si un facteur p représenté par un nœud interne ou multi-feuille était extensible sur la droite avec le lexème a, celui-ci ne comporterait qu’un seul enfant d’étiquette pa ce qui contredit sa compacité. L’ensemble des nœuds internes et multi-feuilles de l’arbre de suffixes est donc un sur-ensemble de farmax(T ). Il reste maintenant à vérifier que chacun des nœuds internes ne puisse être étendu sur la gauche.

Définition 6.5. (Liens suffixes inverses) Soit ST(T ) l’arbre de suffixes de T muni de liens suffixes. Soit p un nœud (chemin) dans cet arbre. Nous notons S−1 (p) l’ensemble des nœuds connectés par un lien suffixe vers p. S−1 (p) = {l1p, l2p, · · · , lk p} avec l1, l2, · · · , lk des lexèmes deux à deux distincts.

Ainsi le facteur répété p est extensible sur la gauche en ap ssi il n’existe qu’un unique nœud connecté par un lien suffixe à p : S−1 (p) = {ap} et que le sous-arbre de racine p ne comporte aucune feuille qui soit une occurrence de début de chaîne (une telle feuille ne pouvant admettre un lien suffixe pointant vers elle). L’existence d’un lexème a tel que |suff (ap)| = |suff (p)| est équivalente à l’extensibilité de p sur la gauche.

Nous proposons la méthode suivante pour récupérer tous les farmax de T . Nous partons de chaque nœud p qui ne soit pas une mono-feuille de profondeur maximale en posant l = S−1 (p) . Si l = 1 et que p ne comporte pas de feuille de début de chaîne, nous suivons la source du lien suffixe et ceci itérativement jusqu’à parvenir à un nœud p′ ne respectant plus ces conditions : le chemin de ce nœud représente un facteur répété non-extensible à gauche. Il s’agit donc d’un farmax.