Block Trees

dc.contributor.authorBelazzougui, Djamal
dc.contributor.authorCáceres, Manuel
dc.contributor.authorGagie, Travis
dc.contributor.authorGawrychowski, Paweł
dc.contributor.authorKärkkäinen, Juha
dc.contributor.authorNavarro, Gonzalo
dc.contributor.authorOrdóñez, Alberto
dc.contributor.authorPuglisi, Simon J.
dc.contributor.authorTabei, Yasuo
dc.description.abstractLet string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes S in 𝒪(z) space, but it does not support random access to S. We introduce a data structure, the block tree, that represents S in 𝒪(z log(n/z)) space and extracts any symbol of T in time 𝒪(log(n/z)), among other space-time tradeoffs. By multiplying the space by the alphabet size, we also support rank and select queries, which are useful for building compressed data structures on top of S. Further, block trees can be built 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.
dc.relation.ispartofseriesJournal of Computer and System Sciences; 117
dc.structureCAlcul Parallèle et Applications
dc.subjectCompressed data structures
dc.subjectRepetitive string collections
dc.subjectLempel-Ziv compression
dc.titleBlock Trees