# Lempel-Ziv Parsing for Sequences of Blocks
## 3 Block Contractions and a Lower Bound for Their LZ77 Parsings  
Fix an integer \(b>0\). A \(b\)-_block contraction_ for a string \(s\) is a string \(t\) such that \(|t|=\lceil|s|/b\rceil\) and, for any \(i,j\in[1\ldots|t|]\), we have \(t[i]=t[j]\) iff \(s[b(i{-}1){+}1\ldots bi]=s[b(j{-}1){+}1\ldots bj]\). (The string \(s\) is padded arbitrarily with new letters so that these two substrings are well defined.) The substrings \(s[b(i{-}1){+}1\ldots bi]\) are called \(b\)-_blocks_ or _blocks_ if \(b\) is clear from the context. We say that a substring \(s[i\ldots j]\)_starts_ (respectively, _ends_) _on a block boundary_ if \(i\equiv 1\pmod{b}\) (respectively, \(j\equiv 0\pmod{b}\)). A substring \(s[i\ldots j]\) is _block-aligned_ if it starts and ends on block boundaries.  
For example, consider \(s=ababbabc\) and \(b=2\). A \(b\)-block contraction of \(s\) is _ddef_, where the letter \(d\) corresponds to the blocks \(ab\), \(e\) corresponds to \(ba\), and \(f\) to \(bc\). The string \(ab\) has two block-aligned occurrences at positions \(1\) and \(3\) and one non-block-aligned occurrence at position \(6\).  
In this paper, we are interested in the comparison of LZ77 parsings for a string and its \(b\)-block contraction. The next theorem establishes a lower bound by providing a series of examples. We will then show in the following section that this lower bound is tight for phrase-aligned LZ77 parsings.  
**Theorem 1**.: _For any integers \(b\) and \(z\) such that \(1<b\leq z/2\), there exists a string that has a phrase-aligned LZ77 parsing of size \(\Theta(z)\) and whose \(b\)-block contraction can have only LZ77 parsings of size at least \(\Omega(bz)\)._  
Proof.: Consider a string \(t\) over the alphabet \(\{a,b\}\) whose greedy LZ77 parsing is phrase-aligned and has size \(z^{\prime}=z-b\). For \(h\in[0\ldots b-1]\), define a morphism \(\phi_{h}\) such that \(\phi_{h}(a)=c^{b-h-1}ac^{h}\) and \(\phi_{h}(b)=c^{b-h-1}bc^{h}\), where \(c\) is a letter different from \(a\) and \(b\). Note that \(|\phi_{h}(a)|=|\phi_{h}(b)|=b\). The example string is \(s=\phi_{0}(t)c^{b}\phi_{1}(t)\phi_{2}(t)\ldots\phi_{b-2}(t)\). It has a phrase-aligned LZ77 parsing of size \(z=O(z^{\prime}+b)\) constructed as follows. The first occurrences of the substrings \(\phi_{0}(a)\) and \(\phi_{0}(b)\) take \(O(b)\) phrases to encode; therefore, \(\phi_{0}(t)\) can be encoded into \(O(z^{\prime}+b)\) phrases by mimicking the parsing of \(t\). Further, each substring \(\phi_{h}(t)\), for \(h>0\), occurs at position \(h+1\) and, thus, can be encoded by one phrase referring to this occurrence. The latter referenced occurrence is phrase-aligned provided the prefix \(s[1\ldots b]\) and the substring \(s[|\phi_{0}(t)|+1\ldots|\phi_{0}(t)|+b]=c^{b}\) were parsed trivially as sequences of \(b\) letters.  
At the same time, any LZ77 parsing of a \(b\)-block contraction of the string \(s\) must have size at least \((b-1)z^{\prime}\): the \(b\)-block contraction of each substring \(\phi_{h}(t)\) produces a \"copy\" of \(t\) over a different alphabet, but the new \"contracted\" letters of these \"copies\" are pairwise distinct; therefore, each contraction should be parsed without references to other substrings, hence, occupying at least \(z^{\prime}\) phrases. It remains to note that \((b-1)z^{\prime}=(b-1)(z-b)\geq(b-1)z/2=\Omega(bz)\).