# Practical Grammar Compression Based on Maximal Repeats +
## 5 Experiments  
We implemented and conducted some comparative experiments. In particular, we compared the sizes of constructed grammars and execution times of the proposed MR-RePair, several existing RePair implementations, and Re-PairImp ([[https://bitbucket.org/IguanaBen/repairimproved](https://bitbucket.org/IguanaBen/repairimproved)]([https://bitbucket.org/IguanaBen/repairimproved](https://bitbucket.org/IguanaBen/repairimproved))), which was recently proposed in [20] as an improvement of RePair. As stated in Remark 1, the MR-order affects the size of a constructed grammar. In practice, the MR-order varies depending on the implementation of the priority queue that manages pairs. For this reason, we used four different implementations of RePair in the comparative analysis, and they were implemented by [PERSON] ([[https://code.google.com/archive/p/re-pair/](https://code.google.com/archive/p/re-pair/)]([https://code.google.com/archive/p/re-pair/](https://code.google.com/archive/p/re-pair/))), [PERSON] ([[https://www.dcc.uchile.cl/~gnavarro/software/index.html](https://www.dcc.uchile.cl/~gnavarro/software/index.html)]([https://www.dcc.uchile.cl/~gnavarro/software/index.html](https://www.dcc.uchile.cl/~gnavarro/software/index.html))), [PERSON] ([[https://github.com/nicolaprezza/Re-Pair](https://github.com/nicolaprezza/Re-Pair)]([https://github.com/nicolaprezza/Re-Pair](https://github.com/nicolaprezza/Re-Pair))) [7], and [PERSON] ([[https://github.com/rwanwork/Re-Pair](https://github.com/rwanwork/Re-Pair)]([https://github.com/rwanwork/Re-Pair](https://github.com/rwanwork/Re-Pair))); we ran it with level 0 (no heuristic option), respectively. Table 1 lists the details of the texts that we used in the experiments. In particular, we employed three texts as highly repetitive texts: one is a randomly generated text (rand77.txt), and the other two are a Fibonacci string (fib41) and a German text (einstein.de.txt) selected from the Repetitive Corpus of the Pizza&Chili Corpus ([[http://pizzachili.dcc.uchile.cl/reporpus.html](http://pizzachili.dcc.uchile.cl/reporpus.html)]([http://pizzachili.dcc.uchile.cl/reporpus.html](http://pizzachili.dcc.uchile.cl/reporpus.html))). The randomly generated text, rand77.txt, consists of alphanumeric symbols and some special symbols. It was generated by concatenating 32 copies of a block that includes 1024 random strings of length 64 each, i.e., the size of the randomly generated text is \(64\times 1024\times 32=2,097,152\) byte. In addition, we used three texts (E.coli, bible.txt, and world192.txt) selected from the Large Corpus ([[http://corpus.canterbury.ac.nz/descriptions/#large](http://corpus.canterbury.ac.nz/descriptions/#large)]([http://corpus.canterbury.ac.nz/descriptions/#large](http://corpus.canterbury.ac.nz/descriptions/#large))) to consider a real-data case. We executed each program seven times for each text and measured the elapsed CPU time only for the grammar generation process. We calculated the average time across five results, excluding the minimum and maximum values among the seven runs. The experiments were run on a computer equipped with an Intel(R) Core i7-8700 3.2-4.6 GHz 6 core, 32 GB RAM, and using Ubuntu 16.04. All of the programs were compiled using gcc version 7.4 with the \"-O3\" option. Table 2 summarizes the experimental results. Unfortunately, Re-PairImp was unable to process fib41 in our experimental environment because of a lack of memory. Here, we excluded the number of rules generating a single terminal symbol from the number of rules since they are the same between RePair and MR-RePair. As shown in the table, the sizes of grammars constructed by each RePair implementation differ from each other for all texts except fib41. In any case, MR-RePair is not inferior to RePair in terms of the size of grammars while in Theorem 6 we show that the grammar can be larger in MR-RePair than in RePair if their MR-orders are different. For rand77.txt, the number of rules and size of the grammars for MR-RePair decreased to about 11% and 55% of those for RePair, respectively.