A Self-Index on Block Trees

Gonzalo Navarro

The Block Tree is a recently proposed data structure that reaches compression close to Lempel-Ziv while supporting efficient direct access to text substrings. In this paper we show how a self-index can be built on top of a Block Tree so that it provides efficient pattern searches while using space proportional to that of the original data structure. More precisely, if a Lempel-Ziv parse cuts a text of length n into z non-overlapping phrases then our index uses O(z log(n/z)) words and finds the occ occurrences of a pattern of length m in time O(m^2 log n + occ log^e n) for any constant e > 0.