Structure de données compressée
Le terme structure de données compressée (en anglais : compressed data structure) apparaît dans les domaines informatiques que sont l'algorithmique, les structures de données, et l'informatique théorique. Il désigne une structure de données dont les opérations sont à peu près aussi rapides que celles sur les structures de données conventionnelles pour un problème, mais dont la taille est substantiellement plus petite. En général, la taille d'une structure de données compressée dépend fortement de l’entropie des données à représenter.
Exemples modifier
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.
Structure de données succincte modifier
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.
Notes et références modifier
- Roberto Grossi, Jeffrey Scott Vitter, « Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching », Proceedings of the 32nd ACM Symposium on Theory of Computing, Mai 2000, 397-406. Version journal dans : SIAM Journal on Computing, 35(2), 2005, 378-407.
- Roberto Grossi, Ankur Gupta et Jeffrey Scott Vitter, « High-order entropy-compressed text indexes », Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA), January 2003, 841-850.
- Paolo Ferragina and Giovanni Manzini, « Opportunistic Data Structures with Applications », Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, Novembre 2000, 390-398. Version journal : « Indexing Compressed Text », Journal of the ACM, 52(4), 2005, 552-581.
