# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Greedy Phrase-Splitting Procedure
Namely, we greedily take the maximum \(m\in[k.k^{\prime}]\) such that the substring \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,m-1}t_{h,m}\) either has length \(b\) or has a block-aligned earlier occurrence (i.e., a block-aligned occurrence in the prefix \(t_{1}d_{1}t_{2}d_{2}\ldots t_{i-1}d_{i-1}\)); then, the \(b\)-block contraction of the string \(q_{1}=t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,m-1}t_{h,m}\) is emitted as a new phrase into the parsing of \(s_{b}\) under construction. If \(m=k^{\prime}\), then the whole string \(t_{i}\) was \"split\" into one chunk \(q_{1}\) and we are done. Otherwise (if \(m<k^{\prime}\)), we further emit the next (one-letter) phrase, the \(b\)-block contraction of \(d_{h,m}\), and proceed taking the maximum \(m^{\prime}\in[m+1..k^{\prime}]\) such that the substring \(q_{2}=t_{h,m+1}d_{h,m+1}t_{h,m+2}d_{h,m+2}\ldots d_{h,m^{\prime}-1}t_{h,m^{ \prime}}\) either has length \(b\) or has a block-aligned earlier occurrence (i.e., a block-aligned occurrence in the prefix \(t_{1}d_{1}t_{2}d_{2}\ldots t_{i-1}d_{i-1}\cdot q_{1}d_{h,m}\)). Similarly, we emit the contraction of \(q_{2}\) and the one-letter contraction of \(d_{h,m^{\prime}}\) into the resulting parsing of \(s_{b}\). The greedy procedure then analogously continues reading \(t_{i}\) from left to right until the whole string \(t_{i}\) is decomposed into chunks \(q_{1},d_{h,m},q_{2},d_{h,m^{\prime}},\ldots\) and all the corresponding new phrases for \(s_{b}\) are emitted. The described process works correctly if each of the chunks \(t_{h,k^{\prime}}\), \(t_{h,k+1},\ldots,t_{h,k^{\prime}}\) in the expansion of \(t_{i}\) in Parsing (1) either has a block-aligned earlier occurrence or is of length at most. 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} \ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}, \tag{2}\]  
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}\), \(t_{h,k},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. Namely, we greedily take the maximum \(m\in[k.k^{\prime}]\) such that the substring \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,m-1}t_{h,m}\) either has length \(b\) or has a block-aligned earlier occurrence in the prefix \(t_{1}d_{1}t_{2}d_{2}\ldots t_{i-1}d_{i-1}\cdot q_{1}d_{h,m}\)); then, the \(b\)-block contraction of the string \(q_{1}=t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,m-1}t_{h,m}\) is emitted as a new phrase into the parsing of \(s_{b}\) under construction. If \(m=k^{\prime}\), then the whole string \(t_{i}\) was \"split\" into one chunk \(q_{1}\) and we are done.