Voir la source de Tableau des suffixes

Un '''tableau des suffixes''' (parfois nommé table des suffixes, en {{lang-en|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, lorsqu'ils sont triés selon l'ordre lexicographique.

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<ref name="manber_myers">{{harv|Manber|Myers|1990}}</ref> et redécouverte en 1992<ref>{{harv|Gonnet|Baeza-Yates|Snider|1992}}</ref>.

== Définition ==

Soient un alphabet de taille finie <math>\mathcal{A}</math> et un [[ordre lexicographique]] sur cet alphabet.

Soit <math>w</math> un mot sur l'alphabet <math>\mathcal{A}</math>. Ce mot de longueur <math>|w|=n</math> compte <math>n</math> suffixes<ref>On ignore le suffixe de longueur 0 : le mot vide.</ref>. 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 <math>w</math> ; par exemple, le suffixe à la position 0 est le mot <math>w</math> lui-même. Une fois les suffixes ordonnés, leurs positions de début correspondantes forment le ''tableau des suffixes''.

=== Exemple ===

Prenons le mot <math>w</math>=abracadabra. Ce mot <math>w</math>, de longueur 11, a les 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 :

:{| class="wikitable" 
|-
! Suffixe
! Position de début
|-
| a
| 10
|-
| abra
| 7
|-
| abracadabra
| 0
|-
| acadabra
| 3
|-
| adabra
| 5
|-
| bra
| 8
|-
| bracadabra
| 1
|-
| cadabra
| 4
|-
| dabra
| 6
|-
| ra
| 9
|-
| racadabra
| 2
|}

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'' = {10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2}.

== Utilisation ==

Le tableau des suffixes est utilisé comme [[Index (base de données)|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 ==
=== Complexité ===

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 <math>O(n\log n)</math> comparaisons en moyenne (où <math>n</math> est la longueur du mot), et où chaque comparaison de suffixe prend dans le pire des cas <math>O(n)</math>. Donc, naïvement, le tri des suffixes prend un temps <math>O(n^{2}\log n)</math> dans le pire des cas. Plusieurs algorithmes améliorent cette borne, proposant des complexités de l'ordre de <math>O(n\log n)</math><ref name="manber_myers"/>, voire <math>\Theta(n)</math><ref>{{En}} {{article
 | titre = Faster suffix sorting | année = 2007
 | périodique = Theoretical Computer Science | volume = 387 | numéro = 3 | page = 258-272
 | nom1 = Larson | prénom1 =  N. Jesper| nom2 =  Sadakane | prénom2 =  Kunihiko
 | url = http://www.sciencedirect.com/science/article/pii/S0304397507005257
 | doi= 10.1016/j.tcs.2007.07.017
}}.</ref>.

{{harv|Li|Li|Huo|2016}} ont donné le premier algorithme de construction du tableau des suffixes en complexité <math>O(n)</math> qui est optimal à la fois en temps et en place, où « en place » signifie que l'algorithme n'a besoin que de <math>O(1)</math> espace supplémentaire au-delà de la chaîne entrée et du tableau de suffixes en sortie. Un autre algorithme linéaire est donné en 2016 par Uwe Baier<ref name="Baier2016">{{chapitre|auteur1=Uwe Baier|titre =Linear-time Suffix Sorting - A New Approach for Suffix Array Construction
|titre ouvrage = 27th Annual Symposium on Combinatorial Pattern Matching 
|auteur ouvrage = Roberto Grossi et Moshe Lewenstein (éditeurs)
|date = 2016| isbn = 978-3-95977-012-5 | passage=123:1-23:12
|collection = Leibniz International Proceedings in Informatics (LIPIcs) |numéro dans collection = 54
|éditeur = Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
|url = http://drops.dagstuhl.de/opus/volltexte/2016/6069
|doi = 10.4230/LIPIcs.CPM.2016.23}}</ref>. D'après la monographie ''Construction of Fundamental Data Structures for Strings''<ref>{{Ouvrage
|langue=
|auteur1= Felipe A. Louza |auteur2=Simon Gog |auteur3= Guilherme P. Telles
|titre= Construction of Fundamental Data Structures for Strings
|sous-titre=
|éditeur= Springer
|collection= Springer Briefs in Computer Science
|lieu=
|année= 2020
|volume=
|tome=
|pages totales= ix+104
|passage=
|isbn= 978-3-030-55107-0 |isbn2= 978-3-030-55108-7  
|doi=10.1007/978-3-030-55108-7 
|consulté le=26 décembre 2020
}}.</ref>, l'algorithme de {{harv|Li|Li|Huo|2016}} est consécutif à deux algorithmes de Nong et al. en 2009 (appelé SAIS) et Nong en 2013 (appelé SACA-K) qui sont aussi linéaires. Un algorithme de Keisuke Goto<ref>{{chapitre
|auteur1= Keisuke Goto
|titre = Optimal time and space construction of suffix arrays and LCP arrays for integer alphabets
|titre ouvrage = Proc. Prague Stringology Conference 
|date= 2019
|pages= 111–125
|issn=
|lire en ligne= http://www.stringology.org/event/2019/p11.html
|consulté le=26 décembre 2020
}}.</ref> est de même complexité optimale (en temps et en place).

=== Compression ===

Pour réduire la place prise par un tableau des suffixes, deux types de [[structure de données compressée|structures de données compressées]] ont été créés : les {{Lien|langue=en|trad=Compressed suffix array|fr=tableau des suffixes compressé|texte=tableaux des suffixes compressés}} et le [[FM-index]] (basé sur la [[transformée de Burrows-Wheeler]]).

=== En ligne ===
{{...}}

== Bibliographie ==
* {{chapitre
 | nom1 = Manber | prénom1 =  Udi | lien auteur1 = Udi Manber
 | nom2 = Myers	 | prénom2 =  Gene | lien auteur2 = Gene Myers
 | titre ouvrage = First Annual ACM-SIAM [[Symposium on Discrete Algorithms]]
 | titre chapitre = Suffix arrays: a new method for on-line string searches
 | année = 1990
 | passage = 319–327
 | présentation en ligne = http://dl.acm.org/citation.cfm?id=320176.320218
}}.
* {{chapitre
 | titre = New indices for text: PAT trees and PAT arrays
 | année = 1992
 | titre ouvrage = Information retrieval: data structures and algorithms
 | auteur ouvrage = William B. Frakes et Ricardo A. Baeza-Yates (éditeurs)
 | nom1 = Gonnet | prénom1 =  Gaston
 | nom2 =  Baeza-Yates | prénom2 =  Ricardo
 | nom3 = Snider | prénom3 = Tim
 | éditeur = [[Prentice-Hall]]
 | passage = 66–82
}}
* {{chapitre
 | doi = 10.1007/978-3-030-00479-8_22
 | titre = Optimal In-Place Suffix Sorting
 | arxiv = 1610.08305
 | année = 2016
 | titre ouvrage = Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE)
 | collection = Lecture Notes in Computer Science
 | numéro dans collection = 11147
 | isbn = 978-3-030-00478-1
 | nom2 =  Li|prénom2=Jian|nom3=Huo|prénom3=Hongwei 
 | nom1 =Li |prénom1=Zhize
 | éditeur = 268–284 
 | passage = 268–284 
}}

== Référence ==
<references />

== Articles connexes ==
* [[Structure de données compressée]]
* [[Arbre d'ondelettes]]
* [[Tableau de Lyndon]]

== Liens externes ==
* [https://web.archive.org/web/20120717213704/http://homepage3.nifty.com/wpage/links/suffix_arrays.html Liens vers les articles sur les tableaux des suffixes jusqu'en 2008]
* [http://www-igm.univ-mlv.fr/~lecroq/m1ita/sa.pdf Exposé de Thierry Lecroq sur les tableaux des suffixes]

{{Palette Algorithmes de manipulation de texte}}
{{Portail|Informatique théorique}}

[[Catégorie:Structure de données]]
[[Catégorie:Algorithme sur les chaînes de caractères]]