## 3 Compression Algorithm
### Algorithmic Detail  
The offline algorithm makes a bottom-up parse tree represented as a CFG. On the other hand, the online algorithm approximates the compression by simulating the left to right construction of a parse tree. To do this, we must determine a replaced pair by only a short substring. By the priority of the rules, we can determine that the pair for any position is the special pair or not by checking the rules simultaneously. In addition, the following lemma enable us to determine a replaced pair from the only a substring of length five. **Lemma 1**. : _Assume that replaced pairs in \(w[1,i-1]\) are already determined, whether \(w[i,i+1]\) becomes a replaced pair or not depends on the interval \(w[i-1,i+3]\)._  
Proof. : We consider to decide whether the substring \(w[i,i+2]\) includes the special pair under the assumption that \(w[i-2,i-1]\) is already replaced. We first need to check a repetitive pair is included or not because of the strongest rule. For the case that \(w[i,i+2]=a_{r}a_{s}(r\
eq s)\), we replace \(w[i,i+1]\) as a repetitive pair. For the case that \(w[i,i+2]=a_{r}a_{s}a_{s}(r\
eq s)\), we preferentially select \(w[i+1,i+2]\) as a replaced pair. We also pay attention to the case such that \(w[i,i+3]=a_{r}a_{s}a_{t}a_{t}(s\
eq t)\), then we forcibly replace \(w[i,i+1]\) because \(w[i+2,i+3]\) is the beginning of maximal repetition. For the minimal or  
Figure 3: An example of a parse tree produced with our replacement rules. maximal pair, we can decide \(w[i,i+1]\) is minimal and maximal pair by computing with \(w[i-1,i+1]\) and \(w[i-1,i+2]\), respectively. If \(w[i+1,i+2]\) is minimal or maximal pair, then \(w[i]\) is not selected as a replaced pair by the priority. Thus there is no conditional statement using the outside of the interval \(w[i-1,i+3]\) for computing special pairs. From the Lemma 1, we describe the Algorithm 1 that is the statement to determine \(w[i,i+1]\) is replaced or not. Note if \(w[i,i+2]\) contains no special pair, we determine \(w[i,i+1]\) as a replaced pair. By using Algorithm 1, it is easy to replace pairs in one pass over a string. ```
1:/* \(replaced\_pair(w,i)\) decides a pair \(w[i,i+1]\) is replaced or not */
2:if\(w[i,i+1]\) is the repetitive pair then
3:return\(true\);
4:elseif\(w[i+1,i+2]\) is the repetitive pair then
5:/* \(w[i+1,i+2]\) is preferentially replaced. */
6:return\(false\);
7:elseif\(w[i+2,i+3]\) is the repetitive pair then
8:/* \(w[i,i+1]\) is forcibly replaced by the priority of the repetitive pair. */
9:return\(true\);
10:elseif\(w[i,i+1]\) is the minimal or maximal pair then
11:return\(true\);
12:elseif\(w[i+1,i+2]\) is the minimal or maximal pair then
13:/* \(w[i+1,i+2]\) is preferentially replaced. */
14:return\(false\);
15:else
16:/* \(w[i,i+2]\) contains no special pair. */
17:return\(true\);
18:endif
```  
**Algorithm 1**\(replaced\_pair(w,i)\): a string \(w\) and a position \(i\). The compression algorithm determine replaced pairs in short buffers corresponding to each level of a parse tree. Let \(h\) is the height of the parse tree. We first prepare queues \(q_{1},q_{2},\ldots,q_{h}\) implemented by circular buffers. Each \(q_{i}\) has a role as a buffer to store a segment of string \(w\) at the \(i\)th level of the parse tree, where the input string corresponds to first level of the tree. The number \(h\) of queues is bounded by \(O(\log n)\) because of the height of parse tree. We define basic operations for such queues as follows:  
* \(enque(q_{i},x)\): add the symbol \(x\) into the tail of the queue \(q_{i}\). * \(deque(q_{i})\): return the head of the queue \(q_{i}\) and remove it. * \(head(q_{i})\): return the head of the queue \(q_{i}\). * \(len(q_{i})\): return the length of the queue \(q_{i}\). The head of the queue \(q_{i}\) is denoted by \(q_{i}[0]\) and thus the tail corresponds to \(q_{i}[len(q_{i})-1]\). Each queue is used for deciding a replaced pair using the function \(replaced\_pair(w,i)\) and its maximum length can be bounded by \(O(1)\).