## 3 Compression Algorithm
### Basic Idea  
The basic task of the algorithm is to replace a pair \(XY\) occurring in a string by a new symbol \(Z\) and generate a production \(Z\to XY\) to \(\mathcal{D}\), where all occurrences of \(XY\) that are determined to be replaced are replaced by a same \(Z\). We note, however, that not all occurrences of \(XY\) are replaced by \(Z\). The critical task is to determine which occurrence of \(XY\) is replaced such that replaced pairs in common substrings are almost synchronized as shown in Figure 1. That is, the aim of this algorithm becomes to minimize the number of different nonterminals generated. Here we explain the three decision rules for the replacement. The rules introduced in this paper are modified version of the [PERSON] _et al_. 's algorithm [25] to extend to our online compression in the next subsection. Figure 1: An example of replacing pairs. Our aim is to replace pairs that are almost synchronized in common substrings. **The first rule (repetitive pair):** Let a current string \(\mathcal{S}\) contain a maximal repetition \(\mathcal{S}[i,j]=a^{k}\). We generate \(A\to aa\in\mathcal{D}\) for an appropriate nonterminal \(A\), and replace \(\mathcal{S}[i,j]=A^{k/2}\) if \(k\) is even, or replace \(\mathcal{S}[i,j-1]=A^{(k-1)/2}\) if \(k\) is odd. **The second rule (minimal pair):** We assume a total order over \(\Sigma\cup N\); that is, any symbol is represented by an integer. If a current string contains a substring \(A_{i}A_{j}A_{k}\) such that \(j<i,k\), then the occurrence of \(A_{j}\) is called _minimal_. The second decision rule is to replace all such pairs \(A_{j}A_{k}\) in \(A_{i}A_{j}A_{k}\) by an appropriate nonterminal. In order to introduce the third decision rule, we explain the notion of the lowest common ancestor on a tree. **Definition 1**. : _Let \(p\) be a positive integer and \(k=\lceil\log p\rceil\). The index tree \(T_{p}\) is the rooted, ordered complete binary tree whose leaves are labeled with \(1,\ldots,2^{k}\) from the left. The height of a node \(v\) refers to the number of edges in the longest path from \(v\) to a descendant of \(v\). Then, the height of the lowest common ancestor of leaves \(i,j\) is denoted by \(\text{lca}(i,j)\) (We can get the \(lca\) for any leaves \(i\) and \(j\) of (virtual) complete binary tree in \(O(1)\) time/space under RAM model [28].) for short._  
Figure 2 shows an example of the index tree and lowest common ancestor. **The third rule (maximal pair):** For a fixed order of alphabet, let a current string contain a substring \(A_{i}A_{j}A_{k}A_{\ell}\) such that the integers \(i,j,k,\ell\) are either increasing or decreasing in this order. If \(lca(j,k)>lca(i,j),lca(k,\ell)\), then the occurrence of the middle pair \(A_{j}A_{k}\) is called _maximal_. The third decision rule is to replace all such pairs by an appropriate nonterminal. We call pairs replaced by the above rules _special pairs_ which appear in almost synchronized position in the common substrings. Be careful that we need to set the priority of the decision rules because such cases possibly overlap and we cannot apply the repetitive and minimal rules simultaneously. For example, the substring \(a_{2}a_{1}a_{3}a_{3}a_{3}\) contains such overlapping pairs. We therefore apply the repetitive and minimal rules in this order to keep uniqueness of the replacement. Indeed, no cases overlap with this priority. If pairs \(w[i-2,i-1]\) and \(w[j+1,j+2]\)\((i<j)\) are special pairs and a substring \(w[i,j]\) contains no special pairs, then we suitably determine replaced pairs in \(w[i,j]\) with left priority, that is, if \(j-i\) is odd  
Figure 2: The (virtual) index tree \(T_{16}\) for \(\Sigma\cup N=\{a_{1},a_{2},\ldots,a_{16}\}\). then the pairs \(w[i,i+1],w[i+2,i+3],\ldots,w[j-1,j]\) are replaced, otherwise \(w[i,i+1],w[i+2,i+3],\ldots,w[j-2,j-1]\). By this replacement, the length of the interval not replaced for a string becomes at most one. In the case of offline compression, it is easy to generate a grammar by the replacement rules.