# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Greedy Phrase-Splitting Procedure  
Our construction of an LZ77 parsing for \(s_{b}\) transforms the zero-shifted block parsing of \(s\). We consecutively consider the phrases \(t_{1},d_{1},t_{2},d_{2},\ldots,d_{z^{\prime}-1},t_{z^{\prime}}\) from left to right: for each \(d_{i}\), we emit a one-letter phrase--the \(b\)-block contraction of \(d_{i}\)--into the resulting parsing for \(s_{b}\); for each \(t_{i}\), we perform a process splitting \(t_{i}\) into chunks whose lengths are multiples of \(b\), and each of which either is of length \(b\) or has a block-aligned earlier occurrence, and the \(b\)-block contractions of these chunks are the new phrases emitted into the resulting parsing for \(s_{b}\). Let us describe the process splitting \(t_{i}\). Figure 1: The \(h\)-shifted block parsings for \(h=0,1,2,3,4\). Gray and blue rectangles denote, respectively, phrases \(d_{h,i}\) and \(t_{h,i}\). Here, we have \(b=5\). Note that some phrases \(t_{h,i}\) are empty and, thus, not depicted. Consider a phrase \(t_{i}\) and suppose that the phrases \(t_{1},d_{1},t_{2},d_{2},\ldots,d_{i-1}\) were already processed, and new phrases corresponding to them in the parsing of \(s_{b}\) under construction were emitted. If \(|t_{i}|=0\), we skip this step. If \(|t_{i}|=b\), we simply emit a new one-letter phrase by contracting \(t_{i}\). Suppose that \(|t_{i}|>b\). Denote by \(f_{\ell}\) the phrase into which \(t_{i}\) is \"inscribed\", i.e., \(0\leq|f_{1}f_{2}\ldots f_{\ell}|-|t_{1}d_{1}\ldots t_{i-1}d_{i-1}t_{i}|<|f_{ \ell}|\). By the assumption of the theorem, there exists a phrase-aligned earlier occurrence of \(f_{\ell}\), i.e., there exist \(j\) and \(j^{\prime}\) such that \(j<j^{\prime}<\ell\) and \(f_{\ell}=f_{j}f_{j+1}\ldots f_{j^{\prime}}\). Thus, there is a copy of the phrase \(t_{i}\) in the substring \(f_{j}f_{j+1}\ldots f_{j^{\prime}}\). While the phrase \(t_{i}\) itself is block-aligned, its copy does not have to be block-aligned. However, the copy is necessarily block-aligned in the \(h\)-shifted block parsing with appropriate \(h\), namely with \(h=(|f_{1}f_{2}\ldots f_{j-1}|+|t_{1}d_{1}t_{2}d_{2}\ldots d_{i-1}|-|f_{1}f_{2} \ldots f_{\ell-1}|)\bmod b\); see Figure 2.  
Let \(t_{h,k},d_{h,k},t_{h,k+1},d_{h,k+1},\ldots,d_{h,k^{\prime}-1},t_{h,k^{\prime}}\) be the phrases of the \(h\)-shifted block parsing that are \"inscribed\" into the substring \(f_{j}f_{j+1}\ldots f_{j^{\prime}}\) (the phrase \(d_{h,k-1}\) could be \"inscribed\" too, but we omit it in this case). The key observation for our construction is that the following equality holds (see Figure 2):  
\[t_{i}=t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,k^{\prime}-1}t_{h,k^{\prime }}.\]  
Now consider the following parsing:  
\[t_{1}d_{1}t_{2}d_{2}\ldots t_{i-1}d_{i-1}\ \cdot\ t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1} \ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}, \tag{1}\]  
which is the zero-shifted block parsing of \(s\) up to the phrase \(t_{i}\) in which phrase \(t_{i}\) was expanded into the chunks \(t_{h,k^{\prime}},d_{h,k},t_{h,k+1},d_{h,k+1},\ldots,d_{h,k^{\prime}-1},t_{h,k^ {\prime}}\). If each of the chunks \(t_{h,k}\), \(t_{h,k+1},\ldots,t_{h,k^{\prime}}\) from the expansion of \(t_{i}\) in Parsing (1) either is of length, at most, \(b\) or has a block-aligned earlier occurrence, then, in principle, we could have emitted into the resulting parsing of \(s_{b}\) the \(b\)-block contractions of \(t_{h,k},d_{h,k^{\prime}},t_{h,k+1},d_{h,k+1},\ldots,d_{h,k^{\prime}-1},t_{h,k^ {\prime}}\), generating, at most, \(2(k^{\prime}-k)+1\) new phrases for \(s_{b}\) in total. Unfortunately, this simple approach produces too many phrases for \(s_{b}\) in the end. Instead, we greedily unite the chunks \(t_{h,k^{\prime}},d_{h,k^{\prime}},\ldots\) from left to right so that the resulting united chunks still either have length \(b\) or have block-aligned earlier occurrences.