TY - GEN
T1 - Linear time Lempel-Ziv factorization
T2 - 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
AU - Kärkkäinen, Juha
AU - Kempa, Dominik
AU - Puglisi, Simon J.
PY - 2013
Y1 - 2013
N2 - Computing the LZ factorization (or LZ77 parsing) of a string is a computational bottleneck in many diverse applications, including data compression, text indexing, and pattern discovery. We describe new linear time LZ factorization algorithms, some of which require only 2nlogn + O(logn) bits of working space to factorize a string of length n. These are the most space efficient linear time algorithms to date, using n logn bits less space than any previous linear time algorithm. The algorithms are also simple to implement, very fast in practice, and amenable to streaming implementation.
AB - Computing the LZ factorization (or LZ77 parsing) of a string is a computational bottleneck in many diverse applications, including data compression, text indexing, and pattern discovery. We describe new linear time LZ factorization algorithms, some of which require only 2nlogn + O(logn) bits of working space to factorize a string of length n. These are the most space efficient linear time algorithms to date, using n logn bits less space than any previous linear time algorithm. The algorithms are also simple to implement, very fast in practice, and amenable to streaming implementation.
UR - https://www.scopus.com/pages/publications/84884316649
U2 - 10.1007/978-3-642-38905-4_19
DO - 10.1007/978-3-642-38905-4_19
M3 - Conference contribution
AN - SCOPUS:84884316649
SN - 9783642389047
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 200
BT - Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
Y2 - 17 June 2013 through 19 June 2013
ER -