@inproceedings{225abf27438b4280810440af011a93a0,
title = "Lempel-Ziv factorization: Simple, fast, practical",
abstract = "For decades the Lempel-Ziv (LZ77) factorization has been a cornerstone of data compression and string processing algorithms, and uses for it are still being uncovered. For example, LZ77 is central to several recent text indexing data structures designed to search highly repetitive collections. However, in many applications computation of the factorization remains a bottleneck in practice. In this paper we describe simple and fast algorithms for computing the LZ77 factorization. These new methods consistently outperform all previous approaches in practice, use less memory, and still offer strong worstcase performance guarantees. A common feature of the new algorithms is their avoidance of the longest-common-prefix array, essential to nearly all prior art.",
author = "Dominik Kempa and Puglisi, \{Simon J.\}",
year = "2013",
doi = "10.1137/1.9781611972931.9",
language = "English",
series = "Proceedings of the Workshop on Algorithm Engineering and Experiments",
publisher = "Society for Industrial and Applied Mathematics Publications",
pages = "103--112",
editor = "Norbert Zeh and Peter Sanders",
booktitle = "2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013",
note = "15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013 ; Conference date: 07-01-2013",
}