  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..
