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]

Preview

Text 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:	Article
Identification Number (DOI):	https://doi.org/10.1007/978-3-319-67428-5_5
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
Dates:	Date Event 10 July 2017 Accepted 6 September 2017 Published Online
Item ID:	21674
Date Deposited:	03 Oct 2017 12:23
Last Modified:	29 Apr 2020 16:39
Peer Reviewed:	Yes, this version has been peer-reviewed.
URI:	https://research.gold.ac.uk/id/eprint/21674

View statistics for this item...

Edit Record (login required)