###
Block Trees

####
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.