Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101525
Title: Lempel–Ziv-Like Parsing in Small Space
Authors: Kosolobov, D.
Valenzuela, D.
Navarro, G.
Puglisi, S. J.
Issue Date: 2020
Publisher: Springer
Citation: Lempel–Ziv-Like Parsing in Small Space / D. Kosolobov, D. Valenzuela, G. Navarro, et al. — DOI 10.1007/s00453-020-00722-6 // Algorithmica. — 2020. — Vol. 82. — Iss. 11. — P. 3195-3215.
Abstract: Lempel–Ziv (LZ77 or, briefly, LZ) is one of the most effective and widely-used compressors for repetitive texts. However, the existing efficient methods computing the exact LZ parsing have to use linear or close to linear space to index the input text during the construction of the parsing, which is prohibitive for long inputs. An alternative is Relative Lempel–Ziv (RLZ), which indexes only a fixed reference sequence, whose size can be controlled. Deriving the reference sequence by sampling the text yields reasonable compression ratios for RLZ, but performance is not always competitive with that of LZ and depends heavily on the similarity of the reference to the text. In this paper we introduce ReLZ, a technique that uses RLZ as a preprocessor to approximate the LZ parsing using little memory. RLZ is first used to produce a sequence of phrases, and these are regarded as metasymbols that are input to LZ for a second-level parsing on a (most often) drastically shorter sequence. This parsing is finally translated into one on the original sequence. We analyze the new scheme and prove that, like LZ, it achieves the kth order empirical entropy compression nHk+ o(nlog σ) with k= o(log σn) , where n is the input length and σ is the alphabet size. In fact, we prove this entropy bound not only for ReLZ but for a wide class of LZ-like encodings. Then, we establish a lower bound on ReLZ approximation ratio showing that the number of phrases in it can be Ω (log n) times larger than the number of phrases in LZ. Our experiments show that ReLZ is faster than existing alternatives to compute the (exact or approximate) LZ parsing, at the reasonable price of an approximation factor below 2.0 in all tested scenarios, and sometimes below 1.05, to the size of LZ. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Keywords: EMPIRICAL ENTROPY
LEMPEL–ZIV COMPRESSION
RELATIVE LEMPEL–ZIV
ALGORITHMS
COMPUTER SCIENCE
ALPHABET SIZE
APPROXIMATION FACTOR
APPROXIMATION RATIOS
ENTROPY BOUND
INPUT LENGTHS
LINEAR SPACES
LOWER BOUNDS
SECOND LEVEL
ENTROPY
URI: http://hdl.handle.net/10995/101525
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85085304970
PURE ID: 14170006
bc6a15eb-f434-4667-a187-2f76b3e53bae
ISSN: 1784617
DOI: 10.1007/s00453-020-00722-6
metadata.dc.description.sponsorship: D. Kosolobov supported by the Russian Science Foundation (RSF), Project 18-71-00002 (for the upper bound analysis and a part of lower bound analysis). D. Valenzuela supported by the Academy of Finland (Grant 309048). G. Navarro funded by Basal Funds FB0001 and Fondecyt Grant 1-200038, Chile. S.J. Puglisi supported by the Academy of Finland (Grant 319454). This work started during Shonan Meeting 126 “Computation over Compressed Structured Data”. Funded in part by EU’s Horizon 2020 research and innovation programme under Marie Skłodowska-Curie Grant Agreement No. 690941 (project BIRDS).
RSCF project card: 18-71-00002
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85085304970.pdf674,7 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.