Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101932
Title: Comparison of LZ77-type parsings
Authors: Kosolobov, D.
Shur, A. M.
Issue Date: 2019
Publisher: Elsevier B.V.
Citation: Kosolobov D. Comparison of LZ77-type parsings / D. Kosolobov, A. M. Shur. — DOI 10.1016/j.ipl.2018.09.005 // Information Processing Letters. — 2019. — Vol. 141. — P. 25-29.
Abstract: We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of them are defined as greedily constructed parsings encoding each phrase by reference to a string occurring earlier in the input. They differ by the phrase encodings: encoded by pairs (length + position of an earlier occurrence) or by triples (length + position of an earlier occurrence + the letter following the earlier occurring part); and they differ by allowing or not allowing overlaps between the phrase and its earlier occurrence. For a given string of length n over an alphabet of size σ, denote the numbers of phrases in the parsings allowing (resp., not allowing) overlaps by z (resp., zˆ) for “pairs”, and by z3 (resp., zˆ3) for “triples”. We prove the following bounds and provide series of examples showing that these bounds are tight: • z≤zˆ≤z⋅O(log⁡[Formula presented]) and z3≤zˆ3≤z3⋅O(log⁡[Formula presented]); • [Formula presented]zˆ<zˆ3≤zˆ and [Formula presented]z<z3≤z. © 2018 Elsevier B.V.
Keywords: COMBINATORIAL PROBLEMS
GREEDY PARSING
LOSSLESS DATA COMPRESSION
LZ77
NON-OVERLAPPING PHRASES
COMPUTER APPLICATIONS
DATA PROCESSING
COMBINATORIAL PROBLEM
GREEDY PARSING
LOSSLESS DATA COMPRESSION
LZ77
NON-OVERLAPPING PHRASES
ENCODING (SYMBOLS)
URI: http://hdl.handle.net/10995/101932
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85054021322
PURE ID: 7888207
0cd6bb20-7b56-4e4c-abb1-b10658cce18d
ISSN: 200190
DOI: 10.1016/j.ipl.2018.09.005
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85054021322.pdf136,2 kBAdobe PDFView/Open


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