# Lempel-Ziv Parsing for Sequences of Blocks
## 4 Upper Bounds on LZ77 Parsings for Block Contractions
### Basic Analysis of the Number of Produced Phrases  
Suppose that every time a new phrase is emitted by the described procedure, we \"pay\" one point. We are to show that the total payment is \(O(bz^{\prime})\), which is \(O(bz)\). For the \"payment\", it will suffice to reserve a budget of \(7 bz^{\prime}\) points. In this section of the proof, we explain how \(4 bz^{\prime}\) points are spent (4 points per phrase \(t_{h,k}\); details follow); the remaining \(3 bz^{\prime}\) points will be discussed in the following final section of the proof. The described process reads the string \(s\) from left to right, emitting new phrases for the parsing of \(s_{b}\) and, during the run, advances a pointer \(p\), the last parameter of the function parse, from 1 to \(n\). Along the way, block-aligned occurrences of some fragments from \(h\)-shifted block parsings appear. The key observation is that once a block-aligned occurrence of a 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}}\) appeared in the string \(s\) at a position \(p\), any subsequent block-aligned substring \(t_{h,a}d_{h,a}t_{h,a+1}d_{h,a+1}\ldots d_{h,a^{\prime}-1}t_{h,a^{\prime}}\) with \(k\leq a\leq a^{\prime}\leq k^{\prime}\) that appears during the processing of phrases after the position \(p\) can be united into one chunk, and there is no need to analyze it by splitting into smaller chunks again. For each phrase \(t_{h,k}\) with \(k\in[1\ldots z^{\prime}]\) and \(h\in[0..b-1]\), we reserve four points (hence, \(4 bz^{\prime}\) points in total). These points are spent when the string \(t_{h,k}\) is first encountered in the function parse (the spending scheme is detailed below), namely when the function is invoked as \(\mathsf{parse}(k_{0},k_{0}^{\prime},h_{0},p)\) with parameters such that \(t_{h,k}=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_{h_{h},k_{0}^{\prime}-1}t_{h_{0},k_{0}^{\prime}}}\) and \(t_{h,k}\) occur at the position \(p\) (the position is necessarily block-aligned; therefore, this is a block-aligned occurrence of \(t_{h,k}\)). We note that this case includes the initial calls \(\mathsf{parse}(k,k^{\prime},h,p)\) that process phrases \(t_{i}\): it is a particular case where \(h=0\). We call such an invocation of parse for the phrase \(t_{h,k}\) a _generating call_. The generating call \"generates\" a block-aligned occurrence of \(t_{h,k}\) in the string \(s\). For each phrase \(t_{h,k}\), at most, one generating call might happen: the only place where a generating call could have happened twice is in item 1 of the description of the function parse, but any subsequent occurrence of \(t_{h,k}\) will have a block-aligned earlier occurrence, and hence, the condition in item 1 could not be satisfied. Therefore, there are, at most, \(bz^{\prime}\) generating calls in total, and we spend, at most, \(4 bz^{\prime}\) points on all of them. Let us consider the work of a generating call. For simplicity, let it be a call for a phrase \(t_{i}\) as in the description of \(\mathsf{parse}(k,k^{\prime},h,p)\) above, i.e., we have \(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}}\), \(h+|t_{h,1}d_{h,1}t_{h,2}d_{h,2}\ldots d_{h,k^{\prime}-1}t_{h,k^{\prime}}|<p\), and \(s[p..p^{\prime}]=t_{i}\), for an appropriate \(p^{\prime}>p\) (the analysis for phrases \(t_{h^{\prime},i}\) from other \(h^{\prime}\)-shifted block parsings is analogous to the analysis for \(t_{i}\)). The work of \(\mathsf{parse}\) can be essentially viewed as follows.