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]

Copy

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	Article
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.
Keywords	LZMW, LZD, LZ78, Compression, Smallest grammar
Departments, Centres and Research Units	Computing
Date Deposited	03 Oct 2017 12:23
Last Modified	29 Apr 2020 16:39