Back to Search
Start Over
Lempel-Ziv Parsing for Sequences of Blocks
- Source :
- Algorithms, Vol 14, Iss 12, p 359 (2021)
- Publication Year :
- 2021
- Publisher :
- MDPI AG, 2021.
-
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(bzlognz). 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.
Details
- Language :
- English
- ISSN :
- 19994893
- Volume :
- 14
- Issue :
- 12
- Database :
- Directory of Open Access Journals
- Journal :
- Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.281b95b91a7e48c3853687e0f446fc67
- Document Type :
- article
- Full Text :
- https://doi.org/10.3390/a14120359