Faster compact on-line Lempel-Ziv factorization

DOI10.4230/LIPICS.STACS.2014.675MaRDI QIDQ2965527zbMATH OpenOpenAlexWikidataFDO

Authors Jun'Ichi Yamamoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Tomohiro I

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1305.6095

zbMATH Keywords

Lempel-Ziv factorizationstring index

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Abstract: We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in $O(NlogN)$ time and uses only $O(Nlogsigma)$ bits of working space, where $N$ is the length of the string and $sigma$ 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(Nlo{g}^{3}N)$ time (Okanohara & Sadakane 2009) or $O(Nlo{g}^{2}N)$ 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 $Oleft(mcdotminleftfrac(loglogm)(loglogN)logloglogN,sqrtfraclogmloglogmightight)$ time and $O(mlogN)$ bits of space, which is faster and more space efficient when the string is run-length compressible.

Recommendations

• Computing Lempel-Ziv factorization online
• Lempel-Ziv factorization using less time \& space
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Lempel-Ziv Factorization Revisited
• Lempel-Ziv factorization: simple, fast, practical

Cited in

(12)

• Refining the \(r\)-index
• Computing Lempel-Ziv factorization online
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• Faster lightweight Lempel-Ziv parsing
• An Opportunistic Text Indexing Structure Based on Run Length Encoding
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Almost linear time computation of maximal repetitions in run length encoded strings
• Sublinear time Lempel-Ziv (LZ77) factorization
• New advances in rightmost Lempel-Ziv
• Tight bounds for compressing substring samples
• Maintaining the size of LZ77 on semi-dynamic strings
• Lempel-Ziv factorization using less time \& space

This page was built for publication: Faster compact on-line Lempel-Ziv factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965527)