## 3 Compression Algorithm
### Performance Analysis  
First, we estimate the running time of LCA-online. We use the following notation indicating the string enqueued to a queue. **Definition 2**. : _For each queue \(q_{i}\), let \(\mathcal{S}_{i}\) denote the string obtained by concatenating all symbols enqueued to \(q_{i}\) from left to right order._  
Note that \(\mathcal{S}_{i}\) corresponds to the \(i\)th level of string in a parse tree produced by replacing pairs as shown in Figure 3. We first prove the following characteristic. **Theorem 2**. : _The running time of LCA-online is bounded by \(O(n)\), where \(n\) is the input length._  
Proof. : For any \(\mathcal{S}_{k}\), the inequality \(\frac{1}{2}|\mathcal{S}_{k}|\leq|\mathcal{S}_{k+1}|\leq\frac{2}{3}|\mathcal{ S}_{k}|\) holds because the algorithm replaces at least one of \(\mathcal{S}_{k}[i,i+1]\) and \(\mathcal{S}_{k}[i+1,i+2]\). Therefore, \(k\leq O(\log n)\) and the total number of symbols inserted into all queues is bounded by \(O(n)\). In any queue, computing a replaced pair is \(O(1)\) time because we can verify in \(O(1)\) time whether or not \(\mathcal{S}_{k}\) contains one of the repetitive, minimal, and maximal pairs. Also, computing the appropriate nonterminal for any pair can be computed in \(O(1)\) time. Hence, the running time is bounded by \(O(n)\) time. Next, we prove that the approximation ratio of LCA-online is _reasonable_. The approximation ratio of the compression algorithm is the upper bound of \(\frac{g}{g_{*}}\) for the output grammar size \(g\) and the minimum grammar size \(g_{*}\) when arbitrary input string is given. **Definition 3**. : _Let \(\mathcal{S}\) be a string and \(\mathcal{S}[i,j]=\alpha\) be an occurrence of a substring \(\alpha\) in \(\mathcal{S}\). We call \(\mathcal{S}[i,j]\) a boundary occurrence if \(\mathcal{S}[i]\
eq\mathcal{S}[i+1]\) and \(\mathcal{S}[j]\
eq\mathcal{S}[j-1]\)._  
**Definition 4**. : _Let \(S_{t}\) be a string enqueued to \(q_{t}\). Then \(R_{t}(i,j)\) is the shortest substring of \(S_{t+1}\) which derives a string containing \(S_{t}[i,j]\)._  
**Lemma 2**. : _Let \(\mathcal{S}_{t}[i_{1},j_{1}]=\mathcal{S}_{t}[i_{2},j_{2}]=\alpha\) be any boundary occurrences. For input string length \(n\), there exists an integer \(k\leq\log n\) such that \(R_{t}(i_{1}+k,j_{1}-k)=R_{t}(i_{2}+k,j_{2}-k)\)._  
Proof. : Let us consider the index tree \(T_{n}\). If a string \(\alpha=a_{\ell_{1}},a_{\ell_{2}},\ldots,a_{\ell_{m}}\) of length \(m\) is a monotonic; _i.e._, either \(\ell_{1}>\ell_{2}>\ldots>\ell_{m}\) or \(\ell_{1}<\ell_{2}<\ldots<\ell_{m}\), and \(lca(\ell_{1},\ell_{2}),lca(\ell_{2},\ell_{3}),\ldots,lca(\ell_{m-1},\ell_{m})\) are monotonic, then \(m\) is bounded by \(\log n\). Therefore, at least one of minimal pair or maximal pair must appear within \(\log n\) consecutive symbols having no repetition. Thus, a prefix of \(\mathcal{S}_{t}[i_{1},j_{1}]\) longer than \(\log n\) contains at least one of minimal/maximal pair; it also appears in \(\mathcal{S}_{t}[i_{2},j_{2}]\) at the corresponding position. Hence, the replacements of inside \(\mathcal{S}_{t}[i_{1},j_{1}]\) and \(\mathcal{S}_{t}[i_{2},j_{2}]\), _i.e._, \(\mathcal{S}_{t}[i_{1}+k,j_{1}-k]\) and \(\mathcal{S}_{t}[i_{2}+k,j_{2}-k]\) completely synchronize. Hence, \(R_{t}(i_{1}+k,j_{1}-k)=R_{t}(i_{2}+k,j_{2}-k)\) for \(k\leq\log n\). **Theorem 3**. : _The approximation ratio \(g/g_{*}\) of LCA-online is \(O(\log^{2}n)\), where \(g\) is the output grammar size, \(g_{*}\) is the minimum grammar size, and \(n\) is the length of the input string._  
Proof. : We estimate the number of different nonterminals produced by LCA-online. Let \(w_{1},\ldots,w_{m}\) be the \(LZ\)-factorization of an input string \(w\). Let \(\#(w)\) denote the maximum number of different nonterminals generated in a single queue after the compression of \(w\) is completed. From the definition of\(LZ\)-factorization, any factor \(w_{i}\) occurs in the prefix \(w_{1},\ldots,w_{i-1}\), or \(|w_{i}|=1\). First, we consider the case that \(w_{i}\) is a boundary occurrence.