TY - GEN
T1 - Lightweight Lempel-Ziv parsing
AU - Kärkkäinen, Juha
AU - Kempa, Dominik
AU - Puglisi, Simon J.
PY - 2013
Y1 - 2013
N2 - We introduce a new approach to LZ77 factorization that uses words of working space and time for any d ≥ 1 (for polylogarithmic alphabet sizes). We also describe carefully engineered implementations of alternative approaches to lightweight LZ77 factorization. Extensive experiments show that the new algorithm is superior, and particularly so at the lowest memory levels and for highly repetitive data. As a part of the algorithm, we describe new methods for computing matching statistics which may be of independent interest.
AB - We introduce a new approach to LZ77 factorization that uses words of working space and time for any d ≥ 1 (for polylogarithmic alphabet sizes). We also describe carefully engineered implementations of alternative approaches to lightweight LZ77 factorization. Extensive experiments show that the new algorithm is superior, and particularly so at the lowest memory levels and for highly repetitive data. As a part of the algorithm, we describe new methods for computing matching statistics which may be of independent interest.
UR - https://www.scopus.com/pages/publications/84884294008
U2 - 10.1007/978-3-642-38527-8_14
DO - 10.1007/978-3-642-38527-8_14
M3 - Conference contribution
AN - SCOPUS:84884294008
SN - 9783642385261
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 139
EP - 150
BT - Experimental Algorithms - 12th International Symposium, SEA 2013, Proceedings
T2 - 12th International Symposium on Experimental Algorithms, SEA 2013
Y2 - 5 June 2013 through 7 June 2013
ER -