Structure de données compressée

Des exemples importants de structures de données compressées comprennent le tableau des suffixes compressé (en)[1] - [2] et le FM-index[3]. Ces deux structures permettent de représenter un texte arbitraire T pour la recherche de sous-chaîne. Pour un motif P donné, elles permettent l'opération de recherche et de localisation des occurrences de P dans T. Le temps de recherche est proportionnel à la somme de la longueur du motif P, d'une fonction croissant très lentement et fonction de la longueur du texte T, et du nombre d'occurrences trouvées. La place occupée est à peu près la taille du texte T dans une forme compressée par entropie, telle qu'elle est obtenue par la prédiction par reconnaissance partielle ou par les algorithmes de Lempel et Ziv. Elles représentent une amélioration substantielle, en ce qui concerne la place, par rapport aux habituels arbre des suffixes et tableau des suffixes, qui eux occupent bien plus de place que le texte T. Elles peuvent de plus être utilisées pour la recherche de motifs arbitraires, contrairement à l'index inversé, qui ne permet que la recherche de mots. Les index inversés n'ont pas la propriété d'auto-indexation.

Une notion proche est celle de structure de données succincte (en). Une telle structure occupe une place à peu près égale au minimum donné par la théorie de l'information, qui est la borne inférieure de l'espace nécessaire pour représenter des données. La place prise par une structure de données compressée au contraire dépend des données particulières qui sont compressées. Quand les données sont compressibles, comme c'est souvent le cas par exemple dans des textes en langue naturelle, la structure de données compressée peut effectivement occuper une place proche du minimum théorique, possiblement nettement inférieure que celle d'autres schémas de compression.

• Arbre d'ondelettes