Artículo de revista
A self-index on block trees
Fecha
2017Registro en:
Lecture Notes in Computer Science, LNCS, volume 10508, 2017
16113349
03029743
10.1007/978-3-319-67428-5_24
Autor
Navarro, Gonzalo
Institución
Resumen
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\).