Lempel-Ziv parsing for sequences of blocks

Dmitry Kosolobov, Daniel Valenzuela

Research output: Contribution to journalArticleScientificpeer-review


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.

Original languageEnglish
Article number359
Issue number12
Number of pages11
Publication statusPublished - Dec 2021
MoE publication typeA1 Journal article-refereed

Fields of Science

  • Blocks
  • Grammar
  • Lempel-Ziv
  • LZ77
  • SLP
  • 113 Computer and information sciences

Cite this