## 5 Experimental Results  
We implemented three compressors based on the LCA algorithm, which are available from google code project ([[http://code.google.com/p/lcacomp/](http://code.google.com/p/lcacomp/)]([http://code.google.com/p/lcacomp/](http://code.google.com/p/lcacomp/))). The first, denoted by **LCA-online**, is the online algorithm of LCA proposed in Section 3. The second, denoted by **LCA-offline**, is a faithful implementation of the offline LCA algorithm, which requires \(o(g)\) space by using \(O(n)\) external memory space, where \(g\) is the output grammar size and \(n\) is the input text size. Therefore, the compression speed of **LCA-offline** is affected by the I/O time. The third, denoted by **LCA-fast**, is another implementation of offline LCA, which requires \(O(n)\) memory space and can thus achieve faster compression than **LCA-offline**. For each generated CFG, two encoding methods are applied: one is the naive encoding for the production rules and the other is the improved encoding presented in Section 4. Recall that the improved method requires \(O(g)\) space. We distinguish between the naive encoding and the improved one by the signs **:N** and **:I**, respectively. For example, **LCA-online:I** means the implementation of **LCA-online** with the improved encoding. We compare our algorithms with other practical compressors. **LZW**[30] is a variant of LZ78-encoding [31], which we implemented. Our LZW implementation does not reset the codeword dictionary, unlike _compress_ in UNIX programs. **gzip** ([[http://www.gzip.org](http://www.gzip.org)]([http://www.gzip.org](http://www.gzip.org))) is based on LZ77-encoding [2] with limited window size. **bzip2** ([[http://www.bzip.org](http://www.bzip.org)]([http://www.bzip.org](http://www.bzip.org))) is based on the block-sorting compression using the Burrows Wheeler Transform [32]. For gzip and bzip2, although we specified **-9** option to obtain their best compressive performances, those programs run in limited memory space because they output compressed texts before they have seen all of the input. **Re-Pair**[19] ([[http://www.cbrc.jp/](http://www.cbrc.jp/)]([http://www.cbrc.jp/](http://www.cbrc.jp/))\(\sim\)rwan/en/restore.html) is an offline grammar-based compressor that recursively substitutes a new symbol for the most frequent pair. **LZMA** (p7 zip) ([http://p7 zip.sourceforge.net/](http://p7 zip.sourceforge.net/)) is a powerful compressor based on the LZ77-encoding with unlimited window size. We set its window length as the input text length to achieve the best compressive performance. Table 1 summarizes the comparison in space usage and online/offline separation, where \(g\) is the output grammar size produced by LCAs, \(z\) is the number of output phrase parsed with LZW, and \(n\) is the input text length. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Method** & **Space usage** & **Online/Offline** \\ \hline
**LCA-online:I** & \(O(g)\) & online \\
**LCA-online:N** & \(O(g)\) & online \\
**LCA-offline:I** & \(O(g)\) + external space & offline \\
**LCA-offline:N** & \(o(g)\) + external space & offline \\
**LCA-fast:I** & \(O(n)\) & offline \\
**LCA-fast:N** & \(O(n)\) & offline \\
**LZW** & \(O(z)\) & online \\
**gzip -9** & limited space & online \\
**bzip2 -9** & limited space & offline per blocks \\
**Re-Pair** & \(O(n)\) & offline \\
**LZMA** & \(O(n)\) & online \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of comparison methods. We used highly repetitive texts from repetitive corpus (Real) ([[http://pizzachili.dcc.uchile.cl/repcorpus.html](http://pizzachili.dcc.uchile.cl/repcorpus.html)]([http://pizzachili.dcc.uchile.cl/repcorpus.html](http://pizzachili.dcc.uchile.cl/repcorpus.html))), which consists of DNA sequences (_Escherichia_Coli, Para, Cere, influenza_), source codes (_coreutils, kernel_), and natural language texts (_einstein.de.txt, einstein.en.txt, world_leaders_).