# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Total Number of Type (a) Chunks  
We estimate the total number of chunks of type (a) by connecting them to a common combinatorial structure defined as follows. The structure is called a _segment system_: it starts with \(z^{\prime}\) unit integer segments \([1\ldots 1],[2\ldots 2],\ldots,[z^{\prime}\ldots z^{\prime}]\), and we can perform _merge queries_, which, given two neighboring segments \([i\ldots j]\) and \([j\!+\!1\ldots k]\) with \(i\leq j\leq k\), create a new united segment \([i\ldots k]\) and remove the old segments \([i\ldots j]\) and \([j\!+\!1\ldots k]\). Clearly, after \(z^{\prime}\) merge queries, everything will be fused into one segment \([1\ldots z^{\prime}]\). Fix \(h\in[1\ldots b\!-\!1]\). We maintain a segment system connected with \(h\), and we associate with each phrase \(t_{h,k}\) the segment \([k\ldots k]\). During the work of the function parse, the following invariant is maintained:  
* if a segment \([k.k^{\prime}]\) such that \(k^{\prime}>k\) belongs to the current segment system, then there is a block-aligned occurrence of the string \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}\) before the currently processed position \(p\). Observe that, at most, \((b-1)z^{\prime}\leq bz^{\prime}\) merge queries can be performed in total on all \(b-1\) introduced segment systems. We will spend 3 points per query from our remaining budget of \(3 bz^{\prime}\) points. The segment systems, their merge queries, and chunks of type (a) are related as follows. Let us temporarily alter the algorithm parse as follows: item 2 first chooses the number \(m\in[k..k^{\prime}]\) as in the original version (as the maximal \(m\in[k..k^{\prime}]\) such that \(t_{h,k}d_{h,k}t_{h,k+1}d_{h,k+1}\ldots d_{h,m-1}t_{h,m}\) can serve as a new chunk), but then, we take the segment \([a..a^{\prime}]\) containing \(k\) from the segment system, i.e., \(a\leq k\leq a^{\prime}\), and we assign \(m:=\min\{m,a^{\prime}\}\). Thus, possibly, \(m\) in the altered version will be smaller than in the original version. Such choice of \(m\) is correct too since, due to our invariant, the altered condition still guarantees 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}\) is either of length \(b\) or has a block-aligned earlier occurrence. It is obvious that the case when \(a\
eq k\) in the altered function parse can only occur for the leftmost chunk in the decomposition of \(t_{i}\) into chunks. Further, the number of chunks of type (a) obtained for \(t_{i}\) by the altered procedure is not less than the number of chunks of type (a) constructed by the original greedy version. It follows straightforwardly from the description that each chunk of type (a) in the altered version that is not the leftmost or rightmost chunk corresponds to a segment from the segment system associated with \(h\), i.e., if \(t_{h,a}d_{h,a}t_{h,a+1}d_{h,a+1}\ldots d_{h,a^{\prime}-1}t_{h,a^{\prime}}\), is such a chunk, then \([a\ldots a^{\prime}]\) belongs to the system. Similarly, the invariant implies that the unit segments \([a\ldots a]\) corresponding to chunks \(t_{h,a}\) of type (b) belong to the system too. For instance, if the example of Figure 3 was obtained by this altered way, the segments \([a..k],[k+1\ldots k+1],[k+2\ldots k+4],[k+5\ldots k+5],[k+6\ldots a^{\prime}]\) would belong to the segment system for some \(a\leq k\) and \(a^{\prime}\geq k+7\). We then perform merge queries uniting the segments corresponding to all chunks generated for \(t_{i}\), except the leftmost and rightmost chunks. (For the example in Figure 3, we unite all subsegments of \([k+1\ldots k+5]\), performing two merge queries in total.) The number of merge queries for \(t_{i}\) is equal to the number of chunks between the leftmost and rightmost chunks from the decomposition of \(t_{i}\) minus one.