Faster Lightweight Lempel-Ziv Parsing

Abstract

We present an algorithm that computes the Lempel-Ziv decomposition in $O(n(\log \sigma +\log \log n))$ time and $n\log \sigma +\epsilon n$ bits of space, where $\epsilon$ is a constant rational parameter, $n$ is the length of the input string, and $\sigma$ is the alphabet size. The $n\log \sigma$ bits in the space bound are for the input string itself which is treated as read-only.

16 pages, 5 figures, accepted to MFCS 2015

References in corpus (2)

• Lempel-Ziv Factorization May Be Harder Than Computing All Runs
• Lempel Ziv Computation In Small Space (LZ-CISS)