Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets

2013/10/05 by Goto, Keisuke, Bannai, Hideo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1310.1448

Abstract

We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length N in linear time, that utilizes only Nlog N + O(1) bits of working space, i.e., a single integer array, for constant size integer alphabets. This greatly improves the previous best space requirement for linear time LZ77 factorization (Kärkkäinen et al. CPM 2013), which requires two integer arrays of length N. Computational experiments show that despite the added complexity of the algorithm, the speed of the algorithm is only around twice as slow as previous fastest linear time algorithms.

Related

• Faster Compact On-Line Lempel-Ziv Factorization
• Simpler and Faster Lempel Ziv Factorization
• Lempel-Ziv Computation In Compressed Space (LZ-CICS)
• Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding
• Lempel Ziv Computation In Small Space (LZ-CISS)