Tableau des suffixes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un tableau des suffixes (parfois nommé table des suffixes, en anglais : suffix array) est une structure de données utilisée en informatique, et plus particulièrement en combinatoire des mots et en bio-informatique. Pour un mot donné, le tableau contient une liste d'entiers qui correspondent aux positions de début des suffixes du mot.

L'objectif du tableau est de fournir les mêmes facilités de recherche qu'un arbre des suffixes tout en réduisant la taille mémoire utilisée. La structure a été introduite en 1990 par Manber et Myers[1] et redécouverte en 1992[2].

Définition[modifier | modifier le code]

Soient un alphabet de taille finie \mathcal{A} et un ordre lexicographique sur cet alphabet.

Soit w un mot sur l'alphabet \mathcal{A}. Ce mot de longueur |w|=n compte n suffixes. Ces suffixes peuvent être ordonnés de manière croissante selon l'ordre lexicographique. À chaque suffixe correspond une position de début dans le mot w, par exemple, le suffixe à la position 1 est le mot w lui-même. Une fois les suffixes ordonnés, leurs positions de début correspondantes forment le tableau des suffixes.

Exemple[modifier | modifier le code]

Prenons le mot w=abracadabra. Le mot w, de longueur 11, a 11 suffixes (abracadabra, bracadabra, racadabra, …, a). Chacun de ces 11 suffixes peut être rangé de manière croissante selon l'ordre lexicographique. Dans le tableau ci-dessous, les suffixes sont rangés par ordre croissant. La deuxième colonne indique la position de début du suffixe dans le mot :

Suffixe Position de début
a 11
abra 8
abracadabra 1
acadabra 4
adabra 6
bra 9
bracadabra 2
cadabra 5
dabra 7
ra 10
racadabra 3

Le tableau des suffixes T formé à partir du mot w est constitué des positions de début des 11 suffixes rangés par ordre lexicographique croissant, soit T={11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3}.

Utilisation[modifier | modifier le code]

Le tableau des suffixes est utilisé comme index pour la recherche de motifs dans un texte. La recherche d'un motif dans un texte est équivalente à la recherche du motif comme préfixe des suffixes du texte.

Le tableau est construit à partir du texte. Le tableau contient les positions de début des suffixes du texte. Or ces suffixes sont rangés par ordre lexicographique lors de la construction du tableau, donc les suffixes commençant par le motif recherché ont leurs positions dans des cases consécutives du tableau. Il n'est cependant pas possible, initialement, de savoir dans quelle section du tableau se trouve cet amas de positions recherchées. L'algorithme va donc utiliser une recherche dichotomique pour identifier cet amas.

Aspects algorithmiques[modifier | modifier le code]

Complexité[modifier | modifier le code]

Deux complexités sont à considérer : celle concernant le tri des suffixes selon l'ordre lexicographique (lors de la construction du tableau), et celle concernant la recherche d'un motif par dichotomie.

Le tri des suffixes est un algorithme qui prend naïvement O(n\log n) comparaisons en moyenne (où n est la longueur du mot), et où chaque comparaison de suffixe prend en moyenne O(n). Donc, naïvement, le tri des suffixes prend un temps O(n^{2}\log n). Plusieurs algorithmes améliorent cette borne, proposant des complexités de l'ordre de O(n\log n)[1], voire \Theta(n)[3].

Compression[modifier | modifier le code]

Pour réduire la place prise par un tableau des suffixes, deux types de structures de données compressées ont été créés : les tableaux des suffixes compressés (en) et le FM-index (en) (basé sur la transformée de Burrows-Wheeler).

En ligne[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Udi Manber et Gene Myers, « Suffix arrays: a new method for on-line string searches », dans First Annual ACM-SIAM Symposium on Discrete Algorithms,‎ 1990 (résumé), p. 319–327.
  • Gaston Gonnet, Ricardo Baeza-Yates et T Snider, « New indices for text: PAT trees and PAT arrays », Information retrieval: data structures and algorithms,‎ 1992

Référence[modifier | modifier le code]

  1. a et b (Manber et Myers 1990)
  2. (Gonnet, Baeza-Yates et Snider 1992)
  3. (en) N. Jesper Larson et Kunihiko Sadakane, « Faster suffix sorting », Theoretical Computer Science, vol. 387, no 3,‎ 2007, p. 258-272 (lien DOI?, lire en ligne).

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]