The LZ-index: A Text Index Based on the Ziv-Lempel Trie Export

@misc{citeulike:460519, abstract = {Let a text of u characters over an alphabet of size  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 log +(m+R) log n). We present a practical implementation of the LZ-index with average search time O(m log u + uR). It ...}, author = {Navarro, G.}, citeulike-article-id = {460519}, citeulike-linkout-0 = {http://citeseer.ist.psu.edu/navarro03lzindex.html}, citeulike-linkout-1 = {http://citeseer.lcs.mit.edu/navarro03lzindex.html}, citeulike-linkout-2 = {http://citeseer.ifi.unizh.ch/navarro03lzindex.html}, citeulike-linkout-3 = {http://citeseer.comp.nus.edu.sg/navarro03lzindex.html}, keywords = {compression}, posted-at = {2009-11-08 12:08:53}, priority = {2}, title = {The LZ-index: A Text Index Based on the Ziv-Lempel Trie}, url = {http://citeseer.ist.psu.edu/navarro03lzindex.html}, year = {2003} }

TY - GEN ID - citeulike:460519 L3 - citeulike-article-id:460519 N2 - Let a text of u characters over an alphabet of size  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 log +(m+R) log n). We present a practical implementation of the LZ-index with average search time O(m log u + uR). It ... TI - The LZ-index: A Text Index Based on the Ziv-Lempel Trie KW - compression AU - Navarro, G PY - 2003/// UR - http://citeseer.ist.psu.edu/navarro03lzindex.html ER -