TY - GEN
T1 - O(n log n)-time text compression by LZ-style longest first substitution
AU - Nishi, Akihiro
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© Proceedings of the Prague Stringology Conference, PSC 2018. All rights reserved.
PY - 2018
Y1 - 2018
N2 - Mauer et al. [A Lempel-Ziv-style Compression Method for Repetitive Texts, PSC 2017] proposed a hybrid text compression method called LZ-LFS which has both features of Lempel-Ziv 77 factorization and longest first substitution. They showed that LZ-LFS can achieve better compression ratio for repetitive texts, compared to some state-of-the-art compression algorithms. The drawback of Mauer et al.'s method is that their LZ-LFS compression algorithm takes O(n2) time on an input string of length n. In this paper, we show a faster LZ-LFS compression algorithm that works in O(n log n) time. We also propose a simpler version of LZ-LFS that can be computed in O(n) time.
AB - Mauer et al. [A Lempel-Ziv-style Compression Method for Repetitive Texts, PSC 2017] proposed a hybrid text compression method called LZ-LFS which has both features of Lempel-Ziv 77 factorization and longest first substitution. They showed that LZ-LFS can achieve better compression ratio for repetitive texts, compared to some state-of-the-art compression algorithms. The drawback of Mauer et al.'s method is that their LZ-LFS compression algorithm takes O(n2) time on an input string of length n. In this paper, we show a faster LZ-LFS compression algorithm that works in O(n log n) time. We also propose a simpler version of LZ-LFS that can be computed in O(n) time.
UR - http://www.scopus.com/inward/record.url?scp=85074818063&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074818063&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85074818063
T3 - Proceedings of the Prague Stringology Conference, PSC 2018
SP - 12
EP - 26
BT - Proceedings of the Prague Stringology Conference, PSC 2018
A2 - Holub, Jan
A2 - Zdarek, Jan
PB - Prague Stringology Club
T2 - 22nd Prague Stringology Conference, PSC 2018
Y2 - 27 August 2018 through 28 August 2018
ER -