2013/05/27 by Junichi Yamamoto, I Tomohiro, Yamamoto, Jun'ichi +7 · 1 citation
Computer Science · Engineering · #Advanced Data Compression Techniques #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1305.6095
openalex publication_date 2013/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(Nlog N) time and uses only O(Nlogσ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(Nlog3N) time (Okanohara & Sadakane 2009) or O(Nlog2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization on-line, in O(m ⋅ min \((loglog m)(log log N))/(logloglog N), √((log m)/(log log m)) \) time and O(mlog N) bits of space, which is faster and more space efficient when the string is run-length compressible.