A self-index on block trees

Abstract

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\lg (n/z))\) words and finds the occ occurrences of a pattern of length m in time \(O(m^2\lg n+occ\lg ^\epsilon n)\) for any constant \(\epsilon >0\).