Tableau de suffixes

Les tableaux de suffixes sont étroitement liés aux arbres de suffixes :

• Les tableaux de suffixes peuvent être construits en effectuant un parcours en profondeur d'un arbre de suffixes. Le tableau de suffixes correspond aux étiquettes des feuilles, données dans l'ordre de leur visite lors du parcours, si les arêtes sont visitées dans l'ordre lexicographique de leur premier caractère.
• On peut construire un arbre de suffixes en temps linéaire en combinant un tableau de suffixes et un tableau LCP . Pour une description de l'algorithme, voir la section correspondante de l' article sur les tableaux LCP .

Il a été démontré que tout algorithme d'arbre de suffixes peut être systématiquement remplacé par un algorithme utilisant un tableau de suffixes enrichi d'informations supplémentaires (comme le tableau LCP ) et résolvant le même problème avec la même complexité temporelle. Les avantages des tableaux de suffixes par rapport aux arbres de suffixes incluent une réduction de l'espace mémoire requis, des algorithmes de construction linéaires plus simples (par exemple, comparés à l'algorithme d'Ukkonen ) et une meilleure localité du cache.

Les tableaux de suffixes ont été introduits par les arbres de suffixes : les tableaux de suffixes stockententiers. Supposer qu'un entier nécessiteoctets, un tableau de suffixes nécessiteoctets au total. C'est nettement inférieur àoctets requis par une implémentation soignée de l'arbre de suffixes.

Cependant, dans certaines applications, l'espace requis par les tableaux de suffixes peut encore être prohibitif. Analysé en bits, un tableau de suffixes nécessiteespace, alors que le texte original sur un alphabet de taillene nécessite quebits. Pour un génome humain avecetLe tableau de suffixes occuperait donc environ 16 fois plus de mémoire que le génome lui-même.

Ces divergences ont favorisé l'essor des tableaux de suffixes compressés et des index de texte intégral compressés basés sur la transformée en ondelettes bayésienne (BWT) , tels que l' index FM . Ces structures de données ne nécessitent qu'un espace mémoire équivalent à la taille du texte, voire inférieur.

Un arbre de suffixes peut être construit danset peut être converti en un tableau de suffixes en parcourant l'arbre en profondeur d'abord également dansIl existe donc des algorithmes capables de construire un tableau de suffixes dans.

Une approche naïve pour construire un tableau de suffixes consiste à utiliser un algorithme de tri par comparaison . Ces algorithmes nécessitentcomparaisons de suffixes, mais une comparaison de suffixes s'exécute dansle temps, donc le temps d'exécution global de cette approche est.

Les algorithmes plus avancés tirent parti du fait que les suffixes à trier ne sont pas des chaînes arbitraires mais sont liés entre eux. Ces algorithmes s'efforcent d'atteindre les objectifs suivants :

• complexité asymptotique minimale
• léger en termes d'espace, ce qui signifie que peu ou pas de mémoire de travail est nécessaire en dehors du texte et du tableau de suffixes lui-même.
• rapide en pratique

L'un des premiers algorithmes à atteindre tous les objectifs est l'algorithme SA-IS de lignes de code ) et peut être optimisé pour construire simultanément le tableau LCP . L'algorithme SA-IS est l'un des algorithmes de construction de tableaux de suffixes les plus rapides connus. Une implémentation soignée par Yuta Mori surpasse la plupart des autres approches de construction linéaires ou super-linéaires.

Outre les contraintes de temps et d'espace, les algorithmes de construction de tableaux de suffixes se distinguent également par l' alphabet qu'ils prennent en charge : les alphabets constants, où la taille de l'alphabet est limitée par une constante, et les alphabets entiers, où les caractères sont des entiers compris dans une plage dépendant de…et les alphabets généraux où seules les comparaisons de caractères sont autorisées.

La plupart des algorithmes de construction de tableaux de suffixes sont basés sur l'une des approches suivantes :

• Les algorithmes de doublement de préfixes s'appuient sur une stratégie proposée par à mémoire externe .

  Des travaux récents de , il semble fonctionner correctement en pratique : les résultats expérimentaux des auteurs ont montré que leur implémentation de tableaux de suffixes dynamiques est généralement plus efficace que la reconstruction lorsqu’on considère l’insertion d’un nombre raisonnable de lettres dans le texte original.

  Dans le domaine des logiciels libres , la routine qsufsort, basée sur l'algorithme de Larsson-Sadakane de 1999, était couramment utilisée pour la construction de tableaux de suffixes . Cette routine a été remplacée par DivSufSort de Yuta Mori, « l'algorithme de tri de suffixes le plus rapide connu en mémoire vive » en 2017. DivSufSort peut également être modifié pour calculer un tableau LCP. Il utilise une copie induite combinée à l'algorithme d'Itoh-Tanaka . En 2021, Ilya Grebnov a présenté une implémentation plus rapide de cet algorithme , qui a démontré une amélioration des performances de 65 % en moyenne par rapport à l'implémentation de DivSufSort sur le corpus Silesia .

Le concept de tableau de suffixes peut être étendu à plusieurs chaînes de caractères. On parle alors de tableau de suffixes généralisé (ou GSA), un tableau de suffixes qui contient tous les suffixes d'un ensemble de chaînes (par exemple,et est trié lexicographiquement avec tous les suffixes de chaque chaîne.

Le tableau des suffixes d'une chaîne peut servir d' index pour localiser rapidement chaque occurrence d'un motif de sous-chaîne.à l'intérieur de la chaîneTrouver chaque occurrence du motif revient à trouver chaque suffixe commençant par la sous-chaîne. Grâce à l'ordre lexicographique, ces suffixes sont regroupés dans le tableau des suffixes et peuvent être trouvés efficacement en deux recherches dichotomiques . La première recherche localise le début de l'intervalle, et la seconde détermine sa fin. de longueurdans la chaînede longueurprendtemps, étant donné qu'une seule comparaison de suffixes doit être comparéepersonnages. Le temps d'utilisation des informations LCP est optimisé. L'idée est qu'une comparaison de motifs n'a pas besoin de recomparer certains caractères lorsqu'on sait déjà qu'ils font partie du plus long préfixe commun du motif et de l'intervalle de recherche actuel. pour une taille d'alphabet constante, comme on le sait grâce aux arbres de suffixes .

Les algorithmes de tri par suffixes permettent de calculer la transformation de Burrows-Wheeler (BWT) . La BWT nécessite le tri de toutes les permutations cycliques d'une chaîne. Si cette chaîne se termine par un caractère de fin de chaîne spécial, lexicographiquement inférieur à tous les autres caractères (par exemple, $), alors l'ordre de la matrice BWT triée et pivotée correspond à l'ordre des suffixes dans un tableau de suffixes. La BWT peut donc être calculée en temps linéaire en construisant d'abord un tableau de suffixes du texte, puis en déduisant la chaîne BWT ..

Les tableaux de suffixes peuvent également être utilisés pour rechercher des sous-chaînes dans la traduction automatique basée sur des exemples , nécessitant beaucoup moins d'espace de stockage qu'une la traduction automatique statistique .

De nombreuses autres applications du tableau de suffixes nécessitent le tableau LCP . Certaines d'entre elles sont détaillées dans la section « Applications » de ce dernier.

Les arbres de suffixes sont des structures de données puissantes, largement utilisées pour la recherche de motifs et de chaînes de caractères, l'indexation et les statistiques textuelles. Cependant, leur taille importante constitue un inconvénient majeur pour de nombreuses applications temps réel nécessitant le traitement de volumes considérables de données, comme l'analyse génomique. Pour pallier cet inconvénient, le tableau de suffixes amélioré a été développé. Il s'agit d'une structure de données composée d'un tableau de suffixes et d'une table supplémentaire, appelée table des enfants, qui contient les informations relatives aux relations parent-enfant entre les nœuds de l'arbre de suffixes. La structure de données de branchement des nœuds de cet arbre est une liste chaînée . Les tableaux de suffixes améliorés sont supérieurs aux arbres de suffixes en termes d'efficacité spatiale et de complexité temporelle, et sont faciles à implémenter. De plus, ils peuvent être appliqués à tout algorithme utilisant un arbre de suffixes grâce au concept abstrait des arbres d'intervalles LCP. La complexité temporelle de la recherche d'un motif de longueur n est de O(n^n).dans un tableau de suffixes amélioré est.

Le tableau de suffixes amélioré est composé de deux tableaux :

1. Le tableau pos[1,...n] représente une liste triée de tous les suffixes S. Seules les positions initiales des suffixes sont stockées dans le tableau afin de réduire la complexité spatiale, car les suffixes sont très longs.
2. tableau lcp lcp[1,...n] : Il s'agit d'un tableau de n entiers qui conserve les longueurs du plus long préfixe commun de deux suffixes consécutifs stockés dans le tableau pos.