# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Basic Ideas  
For simplicity, assume that \(|s|\) is a multiple of \(b\) (if not, \(s\) is padded with at most \(b\) new letters). Our construction relies on the following notion: for \(h\in[0..b-1]\), the \(h\)_-shifted block parsing of \(s\)_ is the following parsing for the string \(s[h+1..|s|-b+h]\):  
\[s[h+1..|s|-b+h]=t_{h,1}d_{h,1}t_{h,2}d_{h,2}\ldots t_{h,z^{\prime}-1}d_{h,z^{ \prime}-1}t_{h,z^{\prime}},\]  
where \(|d_{h,1}|=|d_{h,2}|=\ldots=|d_{h,z^{\prime}-1}|=b\), and each phrase \(t_{h,j}\) is the longest substring starting at position \(p=h+|t_{h,1}d_{h,1}\ldots t_{h,j-1}d_{h,i-1}|+1\), whose length is a multiple of \(b\) and that is entirely contained in the phrase \(f_{j}\) covering the position \(p\), i.e., \(0<p-|f_{1}f_{2}\ldots f_{j-1}|\leq|f_{j}|\) and \(p+|t_{h,j}|-1\leq|f_{1}f_{2}\ldots f_{j}|\) (in particular, \(t_{h,j}\) might be empty if \(f_{j}\) is too short). It might be viewed also as a parsing constructed by a greedy process that, starting from the position \(h+1\), alternatively chooses first a longest substring \(t_{h,j}\) whose length is a multiple of \(b\) that starts at the current position and is \"inscribed\" in the current phrase \(f_{j}\), and then chooses a phrase \(d_{h,i}\) of length exactly \(b\), which \"bridges\" neighboring phrases in \(f_{1}f_{2}\ldots f_{z}\). It is straightforward that \(z^{\prime}\leq 2z\). It is instructive to imagine the \(h\)-shifted block parsings (for \(h=0,1,\ldots,b-1\)) written one after another as in Figure 1. Let us describe briefly the rationale behind the definition. In the case \(h=0\), we omit the first index \"\(h\)\" in the notation \(t_{h,i}\), \(d_{h,i}\) and write the zero-shifted block parsing as \(t_{1}d_{1}t_{2}d_{2}\ldots d_{z^{\prime}-1}t_{z^{\prime}}\). Note that the phrases in this parsing are block-aligned, and each phrase \(t_{i}\) has an earlier occurrence; however, it is not an LZ77 parsing of \(s\) since substrings \(d_{i}\) might not have earlier occurrences. Moreover, the zero-shifted block parsing could have served as a generator of a correct LZ77 parsing for \(s_{b}\) if every substring \(t_{i}\) had a block-aligned earlier occurrence in \(s\): then, the required parsing for \(s_{b}\) would have consisted of \(2z^{\prime}-1\) phrases obtained by the \(b\)-block contractions of \(t_{1},d_{1},t_{2},d_{2},\ldots,d_{z^{\prime}-1},t_{z^{\prime}}\), respectively. (Note that each string \(d_{i}\) has length \(b\) and, thus, is contracted into one letter.) Unfortunately, albeit each substring \(t_{k}\) has earlier occurrences in \(s\), it does not necessarily have an occurrence starting and ending on block boundaries. However, each earlier occurrence \(s[i\ldots j]=t_{k}\) is block-aligned in the \(h\)-shifted block parsing of \(s\) with \(h=j\bmod b\). This observation is the primary motivation for the introduction of the \(h\)-shifted block parsings, and we use it in the sequel. Informally, our idea is as follows. Consider a phrase \(t_{\ell}\) whose earlier occurrence \(s[i\ldots j]=t_{\ell}\) does not start and end on block boundaries. The occurrence \(s[i\ldots j]\) is block-aligned according to an \(h\)-shifted block parsing and, since the initial parsing \(f_{1}f_{2}\ldots f_{z}\) was phrase-aligned, coincides with the concatenation of some consecutive phrases \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}\) in this \(h\)-shifted block parsing (details are discussed below). The phrase \(t_{\ell}\) will be disassembled in place into smaller block-aligned chunks that have earlier occurrences starting and ending on block boundaries. Thus, a block-aligned copy of the fragment \(s[i\ldots j]=t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,k^{\prime}-1}t_{h,k^{ \prime}}\) will appear in place of \(t_{\ell}\) and, if a following phrase \(t_{\ell^{\prime}}\) refers to the same fragment \(s[i\ldots j]\), we can instead refer to this reconstructed block-aligned copy without the need to disassemble into chunks again.