Bounds on two LZ78-style Grammars

Golnaz Badkobeh

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 Ω(n^⅓). We also show that the standard algorithms using Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n^54) time in the worst case.