# Lempel-Ziv Parsing for Sequences of Blocks
## 1 Introduction  
The Lempel-Ziv parsing (LZ77) [1, 2] is one of the central techniques in data compression and string algorithms. Its idea is simple: to compress the data, we parse the data into phrases \(f_{1}f_{2}\ldots f_{z}\) such that each phrase \(f_{i}\) is either one letter or has an earlier occurrence in \(f_{1}f_{2}\ldots f_{i}\), and the compressed encoding, instead of storing the phrases explicitly, stores the references to the occurrences. (In our investigation, we consider both non-overlapping and overlapping versions of LZ77; see precise definitions below.) Typically, algorithms that produce the parsing interpret the data as a sequence of bytes; however, some algorithms treat the data as a sequence of bits. What is the relationship between these parsings that differ only in the way they view the same input? In this paper, we investigate this question.  
Our main result is that, for any integer \(b>1\), the number \(z\) of phrases in the LZ77 parsing of a string of length \(n\) and the number \(z_{b}\) 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 \(z_{b}=O(bz\log\frac{n}{z})\) (a more precise formulation follows). We partially complement this upper bound with a lower bound \(z_{b}=\Omega(bz)\) in a series of examples. Further, we prove that a better bound \(z_{b}=O(bz)\), which is tight, holds for the special case when each phrase \(f_{i}\) in the LZ77 parsing has a \"phrase-aligned\" earlier occurrence, i.e., \(f_{i}=f_{j}f_{j+1}\ldots f_{j}\), for some \(j<j^{\prime}<i\). This special case is particularly interesting in connection to the grammar compression [3]: a grammar of size \(g\) that produces the string naturally induces such \"phrase-aligned\" LZ77 parsing of size \(O(g)\)[4].  
The present work is a continuation of the line of research focused on the comparison of different efficiently computable measures of compression, mainly centering around the LZ77 parsing, the golden standard in this field (see a discussion of other close measures in [5, 6, 7]). The results on this topic are too numerous to be listed here exhaustively. We, however, point out a couple of relevant studies and open problems.  
The relations between the LZ77 parsing and the grammar-based compression, which naturally induces an LZ77 parsing [4], are not sufficiently understood: known upper and lower bounds on their sizes differ by an \(O(\log\log n)\) factor [8; 9; 10]. A better lower bound \(z_{b}=\Omega(bz\log n)\), which would show that our main result is tight, even only for \(b=2\), would imply that the minimal grammar generating the string attaining this bound is of size \(\Omega(z\log n)\), thus removing the \(O(\log\log n)\)-factor gap. This gives a new approach to attack this problem. However, it is still quite possible that our upper bound \(O(bz\log\frac{n}{z})\) can be improved and lowered to \(O(bz)\).  
The recently introduced LZ77 variant called ReLZ [11] uses a certain preprocessing in the spirit of the so-called relative LZ77 (RLZ) [12]. The efficiency of the obtained parsing was evaluated mostly experimentally, and there are no good upper bounds comparing it to the classical LZ77. Our present result actually stems from this work in an attempt to find a good upper (or lower) bound for this version of the LZ77 parsing. We believe that techniques developed in the present paper could help to obtain such bounds.  
The paper is organized as follows. The following section provides all necessary definitions and known facts about the LZ77 parsings and related concepts. In Section 3, we formalize the idea of \"contracted\" blocks of length \(b\) and construct a series of examples showing that one of our upper bounds is tight. Then, in Section 4, we prove our upper bound results. We conclude with some open problems in Section 5.