On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation

Abstract

We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length $n$; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor $\Omega (n^{\frac{1}{3}})$ but is always within a factor $O((\frac{n}{\log n}{)}^{\frac{2}{3}})$. In addition, we show that the standard algorithms using $\Theta (z)$ working space to construct the LZD and LZMW parsings, where $z$ is the size of the parsing, work in $\Omega (n^{\frac{5}{4}})$ time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses $O(z\log n)$ space and $O(n+z{\log }^{2}n)$ time w.h.p..

12 pages, accepted to SPIRE 2017

References in corpus (1)

• A Faster Grammar-Based Self-Index