# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Greedy Phrase-Splitting Procedure
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 most \(b\). What if this is not the case? Suppose that \(t_{h,k}\) is such a \"bad\" chunk in Parsing (1): it does not have a block-aligned earlier occurrence and \(|t_{h,k}|>b\). In a certain sense, we arrive at an analogous problem that we had with the phrase \(t_{i}\): we have to split \(t_{h,k}\) (here, we are talking about the occurrence of \(t_{h,k}\) from the expansion of \(t_{i}\) in Parsing (1)) into a number of chunks whose lengths are multiples of \(b\) and each of which either is of length \(b\) or has a block-aligned earlier occurrence; we will then emit the \(b\)-block contractions of these chunks into the resulting parsing for \(s_{b}\). We solve this problem recursively by the same procedure, which can be roughly sketched as follows. The phrase \(t_{h,k}\) from the \(h\)-shifted block parsing of \(s\) (not \(t_{h,k}\) from the expansion of \(t_{i}\) in Parsing (1)!) was \"inscribed\" into a phrase \(f_{\ell_{0}}\) (such as, analogously, \(t_{i}\) was \"inscribed\" into \(f_{\ell}\)), which, by the assumption of the theorem, has a phrase-aligned earlier occurrences \(f_{\ell_{0}}=f_{i_{0}}f_{i_{0}+1}\cdots f_{i_{\ell}}\), for some \(j_{0}<j_{0}^{\prime}<\ell_{0}\) (like, similarly, \(f_{\ell}\) had an occurrence \(f_{\ell}=f_{j}f_{j+1}\ldots f_{j^{\prime}}\)). There is, thus, a copy of \(t_{h,k}\) in the substring \(f_{j_{0}}f_{j_{0}+1}\ldots f_{i_{\ell}}\). This copy is not necessarily block-aligned according to neither zero-shifted nor \(h\)-shifted block parsings. However, the copy is block-aligned with respect to the \(h_{0}\)-shifted block parsing for appropriate \(h_{0}\) (for example, the copy of \(t_{i}\) from \(f_{j}f_{j+1}\ldots f_{j^{\prime}}\) was block-aligned according to the \(h\)-shifted block parsing). We then consider a fragment \(t_{h_{0},k_{0}}d_{h_{0},k_{0}}t_{h_{0},k_{0}+1}d_{h_{0},k_{0}+1}\ldots d_{h_{0},k_{0}^{\prime}-1}t_{h_{0},k_{0}^{\prime}}\) of the \(h_{0}\)-shifted block parsing \"inscribed\" into the substring \(f_{i_{0}}f_{i_{0}+1}\ldots f_{i_{\ell}}\) and conclude that this fragment is equal to \(t_{h,k}\) (such as, analogously, the fragment \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}\) \"inscribed\" into \(f_{j}f_{j+1}\ldots f_{j^{\prime}}\) was equal to \(t_{i}\)). We proceed recursively decomposing \(t_{h,k}\) into chunks by greedily uniting \(t_{h_{0},k_{0}}d_{h_{0},k_{0}}t_{h_{0},k_{0}+1},d_{h_{0},k_{0}+1},\ldots d_{h_{0 },k_{0}^{\prime}-1},t_{h_{0},k_{0}^{\prime}}\) by analogy to the procedure for \(t_{i}\). This recursion, in turn, itself can arrive at an analogous splitting problem for another chunk (say, \(t_{h_{0},k^{\prime}}\)), which, in the same way, is solved recursively.