Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel
Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro, Alberto
Ordóñez, Simon J. Puglisi, and Yasuo Tabei
Let string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm.
The corresponding compression algorithm encodes S in O(z) space, but it
does not support random access to S. We introduce a data structure, the
block tree, that represents S in O(z log(n/z)) space and
extracts any symbol of S in 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.