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

Badkobeh, Golnaz; Gagie, Travis; Inenaga, shunsuke; Kociumaka, Tomasz; Kosolobov, Dmitry and Puglisi, Simon. 2017. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation. Lecture Notes in Computer Science, 1058, pp. 51-67. ISSN 0302-9743 [Article]

main.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (388kB) | Preview

Abstract or Description

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 Ω(n13)Ω(n13) but is always within a factor O((nlogn)23)O((nlog⁡n)23) . In addition, we show that the standard algorithms using Θ(z)Θ(z) working space to construct the LZD and LZMW parsings, where z is the size of the parsing, work in Ω(n54)Ω(n54) time in the worst case. We then describe a new Las Vegas LZD/LZMW parsing algorithm that uses O(zlogn)O(zlog⁡n) space and O(n+zlog2n)O(n+zlog2⁡n) time w.h.p.

Item Type:


Identification Number (DOI):


Additional Information:

International Symposium on String Processing and Information Retrieval. Part of the Lecture Notes in Computer Science book series (LNCS, volume 10508).

G. Badkobeh—Supported by the Leverhulme Trust’s Early Career Scheme.

T. Kociumaka—Supported by Polish budget funds for science in 2013–2017 under the ‘Diamond Grant’ program.

S.J. Puglisi—Supported by the Academy of Finland via grant 294143.


LZMW, LZD, LZ78, Compression, Smallest grammar

Departments, Centres and Research Units:



10 July 2017Accepted
6 September 2017Published Online

Item ID:


Date Deposited:

03 Oct 2017 12:23

Last Modified:

29 Apr 2020 16:39

Peer Reviewed:

Yes, this version has been peer-reviewed.



View statistics for this item...

Edit Record Edit Record (login required)