Lempel-Ziv parsing for sequences of blocks

Show full item record



Permalink

http://hdl.handle.net/10138/340786

Citation

Kosolobov , D & Valenzuela , D 2021 , ' Lempel-Ziv parsing for sequences of blocks ' , Algorithms , vol. 14 , no. 12 , 359 . https://doi.org/10.3390/a14120359

Title: Lempel-Ziv parsing for sequences of blocks
Author: Kosolobov, Dmitry; Valenzuela, Daniel
Contributor organization: Helsinki Institute for Information Technology
Department of Computer Science
Date: 2021-12
Language: eng
Number of pages: 11
Belongs to series: Algorithms
ISSN: 1999-4893
DOI: https://doi.org/10.3390/a14120359
URI: http://hdl.handle.net/10138/340786
Abstract: The Lempel-Ziv parsing (LZ77) is a widely popular construction lying at the heart of many compression algorithms. These algorithms usually treat the data as a sequence of bytes, i.e., blocks of fixed length 8. Another common option is to view the data as a sequence of bits. We investigate the following natural question: what is the relationship between the LZ77 parsings of the same data interpreted as a sequence of fixed-length blocks and as a sequence of bits (or other “elementary” letters)? In this paper, we prove that, for any integer b > 1, the number z of phrases in the LZ77 parsing of a string of length n and the number zb of phrases in the LZ77 parsing of the same string in which blocks of length b are interpreted as separate letters (e.g., b = 8 in case of bytes) are related as zb = O(bz lognz ). The bound holds for both “overlapping” and “non-overlapping” versions of LZ77. Further, we establish a tight bound zb = O(bz) for the special case when each phrase in the LZ77 parsing of the string has a “phrase-aligned” earlier occurrence (an occurrence equal to the concatenation of consecutive phrases). The latter is an important particular case of parsing produced, for instance, by grammar-based compression methods.
Subject: Blocks
Grammar
Lempel-Ziv
LZ77
SLP
113 Computer and information sciences
Peer reviewed: Yes
Rights: cc_by
Usage restriction: openAccess
Self-archived version: publishedVersion


Files in this item

Total number of downloads: Loading...

Files Size Format View
algorithms_14_00359.pdf 326.2Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record