Résumé: Let string S[1..n]be parsed into zphrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes Sin O(z)space, but it does not support random access to S. We introduce a data structure, the block tree, that represents Sin O(zlog(n/z))space and extracts any symbol of Sin time O(log(n/z)), among other space-time tradeoffs. The structure also supports other queries that are useful for building compressed data structures on top of S. Further, block trees can be built in linear time and in a scalable manner. Our experiments show that block trees offer relevant space-time tradeoffs compared to other compressed string representations for highly repetitive strings.

Langue: Anglais
Thème Informatique

Mots clés:
Compressed data structures
Repetitive string collections
Lempel-Ziv compression