Indexing Text using the Ziv-Lempel Trie

Gonzalo Navarro

Let a text of u characters over an alphabet of size s be compressible to n symbols by the LZ78 or LZW algorithm. We show that it is possible to build a data structure based on the Ziv-Lempel trie that takes 4n log_2 n (1+o(1)) bits of space and reports the R occurrences of a pattern of length m in worst case time O(m^2 log (ms) + (m+R) log n).