Indexation de texte compressé

Nous concevons deux structures de données compressées pour le problème d'indexation de texte intégral qui prennent en charge des recherches de sous-chaînes efficaces en utilisant à peu près l'espace requis pour stocker le texte sous forme compressée. Notre première structure de données compressée récupère les occurrences occ d'un motif P 1, p dans un texte T 1, n en O ( p + occ log 1+ε n ) temps pour tout ε choisi, 0<ε<1. Cette structure de données utilise au maximum 5 n H k ( T ) + o ( n ) bits de stockage, où H k ( T ) est l'entropie empirique d'ordre k de T. L'utilisation de l'espace est Θ( n ) bits dans le pire des cas et o ( n ) bits pour les textes compressibles. Cette structure de données exploite la relation entre les tableaux de suffixes et la transformation de Burrows--Wheeler, et peut être considérée comme un tableau de suffixes compressé. Notre deuxième structure de données compressée atteint O ( p + occ ) temps de requête en utilisant O ( n H k ( T ) log ε n ) + o ( n ) bits de stockage pour tout ε choisi, 0<ε<1. Par conséquent, elle fournit un temps de requête sensible à la sortie optimal en utilisant o ( n log n ) bits dans le pire des cas. Cette deuxième structure de données s'appuie sur la première et exploite l'interaction entre deux compresseurs : la transformation de Burrows--Wheeler et l'algorithme LZ78.