## 3 Compression Algorithm
### Algorithmic Detail
By the Lemma 1, we can restrict the maximum length of any queue by a constant longer than five. For linear time compression, we must prepare another data structure \(\mathcal{D}^{R}\) called _reverse dictionary_: \(\mathcal{D}^{R}(x,y)\) returns a nonterminal \(z\) associated with the pair \(xy\) by \(z\to xy\in\mathcal{D}\). In case \(z\to xy\
otin\mathcal{D}\), \(\mathcal{D}^{R}(x,y)\) creates a new nonterminal symbol \(z^{\prime}\
otin N\) and returns \(z^{\prime}\). For instance, if we have a dictionary \(\mathcal{D}=\{X_{1}\to a_{1}a_{2},X_{2}\to a_{3}a_{1},X_{3}\to a_{2}a_{2}\}\), \(\mathcal{D}^{R}(a_{3},a_{1})\) returns \(X_{2}\), \(\mathcal{D}^{R}(a_{1},a_{1})\) creates a new nonterminal \(X_{4}\) and returns it. If we use randomization, \(\mathcal{D}^{R}(x,y)\) can be computed in \(O(1)\) worst case time and inserting a new production rule can be achieved in \(O(1)\) amortized time within \(O(|\mathcal{D}|)\) space using dynamic perfect hashing [29]. Next we outline the online algorithm. We describe the online version of LCA in Algorithm 2 as well as its recursive function \(insert\_symbol(q_{i},x)\) in Algorithm 3. All queues are initialized to contain only _dummy symbol_\(d\
otin\Sigma\cup N\), which is required to compute the first pair at the each queue. In the lines 2-5 of Algorithm 2, input characters are enqueued to \(q_{1}\) one by one. In Algorithm 3, if there is \(q_{i}\) such that \(len(q_{i})\geq 5\), the algorithm decides the replaced pair in \(q_{i}[1,3]\). In case \(q_{i}[1,2]\) is replaced by an appropriate nonterminal \(z\), \(q_{i}[0,1]\) is dequeued and \(z\) is enqueued to \(q_{i+1}\). In case \(q_{i}[2,3]\) is replaced by \(z\), \(q_{i}[0,2]\) is dequeued and \(q_{i}[1]z\) is enqueued to \(q_{i+1}\). The symbol \(q_{i}[2]\) in the first case and \(q_{i}[3]\) in the second case are remaining in \(q_{j}\) to determine the next replaced pair after a new symbol is enqueued to \(q_{i}\). Figure 4 describes the action of the function \(insert\_symbol(q_{i},x)\). The algorithm recursively continues the above process until all input characters are enqueued. As the post-processing, the symbols remaining in the queues \(q_{i},\ldots,q_{h}\) are replaced by appropriate nonterminals in the left to right order. Finally the produced dictionary is returned. ```
1:\(\mathcal{D}:=\emptyset\); initialize queues;
2:repeat
3:input a new character \(c\);
4:\(insert\_symbol(q_{1},c)\);
5:until\(c\) is not the end of the inputs. 6:\(i:=1\);
7:while\(q_{i}\) is not empty do
8: replace the symbols remained in \(q_{i}[1,4]\),
9: and then enqueue the string replaced in \(q_{i}[1,4]\) into \(q_{i+1}\);
10:\(i:=i+1\);
11:endwhile
12:output\(\mathcal{D}\);
```  
**Algorithm 2** LCA-online. ```
1:\(enque(q_{i},x)\);
2:if\(len(q_{i})\geq 5\)then
3:if\(replaced\_pair(q_{i},1)=true\)then
4:\(deque(q_{i})\);
5:\(y_{1}:=deque(q_{i})\);
6:\(z:=\mathcal{D}^{R}(y_{1},y_{2})\);
7:\(\mathcal{D}:=\{z\to y_{1}y_{2}\}\cup\mathcal{D}\); /* update \(\mathcal{D}\) */
8:\(insert\_symbol(q_{i+1},z)\);
9:else
10:\(deque(q_{i})\);
11:\(y_{1}:=deque(q_{i})\);
12:\(insert\_symbol(q_{i+1},y_{1})\);
13:\(y_{2}:=deque(q_{i})\); \(y_{3}:=head(q_{i})\);
14:\(z:=\mathcal{D}^{R}(y_{2},y_{3})\);
15:\(\mathcal{D}:=\{z\to y_{2}y_{3}\}\cup\mathcal{D}\); /* update \(\mathcal{D}\) */
16:\(insert\_symbol(q_{i+1},z)\);
17:endif
18:endif
```  
**Algorithm 3**\(insert\_symbol(q_{i},x)\): a queue \(q_{i}\) and a symbol \(x\). Figure 4: The action of \(insert\_symbol(q_{i},x)\).