Structure de données compressée - Compressed data structure

Le terme structure de données compressées apparaît dans les sous - domaines de l' informatique des algorithmes , des structures de données et de l'informatique théorique . Il se réfère à une structure de données dont les opérations sont à peu près aussi rapides que celles d'une structure de données conventionnelle pour le problème, mais dont la taille peut être sensiblement plus petite. La taille de la structure de données compressée dépend généralement fortement de l'entropie des données représentées.

Des exemples importants de structures de données compressées incluent le tableau de suffixes compressés et l' index FM , qui peuvent tous deux représenter un texte arbitraire de caractères T pour la correspondance de modèle . Compte tenu de tout motif d'entrée P , ils prennent en charge l'opération de trouver si et où P apparaît dans T . Le temps de recherche est proportionnel à la somme de la longueur du motif P , une fonction à croissance très lente de la longueur du texte T et du nombre de correspondances rapportées. L'espace qu'ils occupent est à peu près égal à la taille du texte T sous forme compressée par entropie, comme celle obtenue par Prédiction par Matching Partiel ou gzip . De plus, les deux structures de données sont auto-indexées, en ce qu'elles peuvent reconstruire le texte T de manière aléatoire, et ainsi le texte sous-jacent T peut être ignoré. En d' autres termes, ils fournissent simultanément une représentation compressée et rapidement des recherches du texte T . Ils représentent une amélioration de l' espace considérable par rapport au traditionnel arbre suffixe et tableau suffixe , qui occupent plusieurs fois plus d' espace que la taille de T . Ils prennent également en charge la recherche de modèles arbitraires, par opposition à l' index inversé , qui ne peut prendre en charge que les recherches basées sur des mots. De plus, les index inversés ne disposent pas de la fonction d'auto-indexation.

Une notion connexe importante est celle d'une structure de données succincte , qui utilise un espace à peu près égal au minimum théorique de l'information, qui est une notion du pire des cas de l'espace nécessaire pour représenter les données. En revanche, la taille d'une structure de données compressée dépend des données particulières représentées. Lorsque les données sont compressibles, comme c'est souvent le cas dans la pratique pour le texte en langage naturel, la structure de données compressées peut occuper un espace très proche du minimum théorique de l'information, et nettement moins d'espace que la plupart des schémas de compression.

Les références