Indexing Text using the Ziv-Lempel Trie.
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 how to
build a data structure, called the LZ-index, based on the Ziv-Lempel trie that
takes 4n log_2(n) (1+o(1)) bits of space (that is, 4 times the entropy of
the text) and reports the R occurrences of a pattern of length m
in worst case time O(m^3 log(s) + (m+R)log(n)).
We present a practical implementation of the LZ-index, which is faster than
current alternatives when we take into consideration the time to report the
positions or text contexts of the occurrences found.