TY - GEN
T1 - Simpler and faster Lempel Ziv factorization
AU - Goto, Keisuke
AU - Bannai, Hideo
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - We present a new, simple, and efficient approach for computing the Lempel-Ziv (LZ77) factorization of a string in linear time, based on suffix arrays. Computational experiments on various data sets show that our approach constantly outperforms the fastest previous algorithm LZOG (Ohlebusch and Gog 2011), and can be up to 2 to 3 times faster in the processing after obtaining the suffix array, while requiring the same or a little more space.
AB - We present a new, simple, and efficient approach for computing the Lempel-Ziv (LZ77) factorization of a string in linear time, based on suffix arrays. Computational experiments on various data sets show that our approach constantly outperforms the fastest previous algorithm LZOG (Ohlebusch and Gog 2011), and can be up to 2 to 3 times faster in the processing after obtaining the suffix array, while requiring the same or a little more space.
UR - http://www.scopus.com/inward/record.url?scp=84881082973&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881082973&partnerID=8YFLogxK
U2 - 10.1109/DCC.2013.21
DO - 10.1109/DCC.2013.21
M3 - Conference contribution
AN - SCOPUS:84881082973
SN - 9780769549651
T3 - Data Compression Conference Proceedings
SP - 133
EP - 142
BT - Proceedings - DCC 2013
T2 - 2013 Data Compression Conference, DCC 2013
Y2 - 20 March 2013 through 22 March 2013
ER -