Block Trees

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.

Journal article

In Journal of Computer and System Sciences