Block Trees

Block Tree


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.

In Journal of Computer and System Sciences
Manuel Cáceres
Manuel Cáceres
Postdoctoral Researcher

My research interests include algorithmic bioinformatics, graph algorithms, string algorithms, algorithmic bioinformatics, compressed data structures, safe & complete algorithms and parameterized algorithms.