Lempel Ziv Computation In Small Space (LZ-CISS)

Abstract

For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using $(1+\epsilon )n\lg n+O(n)$ bits (for any positive constant $\epsilon \le 1$) working space (including the space for the output) for any text of size $n$ over an integer alphabet in $O(n/{\epsilon }^2)$ time.

Full Version of CPM 2015 paper

References in corpus (1)

• Alphabet-Dependent String Searching with Wexponential Search Trees

Cited by in corpus (1)

• Faster Lightweight Lempel-Ziv Parsing