# Practical Grammar Compression Based on Maximal Repeats +
## 6 Conclusions  
In this study, we analyzed the process of RePair and revealed that the RePair algorithm replaces the most frequent pairs step by step within their corresponding most frequent maximal repeats. On the basis of this analysis, we designed MR-RePair, a novel variant of RePair. Instead of consecutively substituting the most frequent pairs, MR-RePair performs one-time substitution of the most frequent maximal repeats. Furthermore, we implemented MR-RePair and compared the sizes of its constructed grammars to those of the grammars constructed by several implementations of RePair. Through the experiments, we confirmed the effectiveness of MR-RePair especially for highly repetitive texts. \begin{table}
\begin{tabular}{l l r r r r r r} \hline \hline \multirow{2}{*}{**Text File**} & \multicolumn{3}{c}{**RePair**} & \multicolumn{3}{c}{**Re-Pair**} & \multicolumn{1}{c}{**MR-**} \\  & & **[PERSON]** & **[PERSON]** & **[PERSON]** & **[PERSON]** & **[PERSON]** & **RePair** \\ \hline rand77.txt & Rules & 41,651 & 41,642 & 41,632 & 41,675 & 41,661 & **4,492** \\  & Total length & 83,302 & 83,284 & 83,264 & 83,350 & 83,322 & **46,143** \\  & Start variable & 9 & 2 & 7 & **2** & **2** & **9** \\  & Grammar size & 83,311 & 83,286 & 83,271 & 83,352 & 83,324 & **46,152** \\  & Execution time & 0.22 & 0.34 & 2.94 & 0.94 & 2.48 & **0.20** \\ \hline fib41 & Rules & 38 & 38 & 38 & 38 & - & 38 \\  & Total length & 76 & 76 & 76 & 76 & - & 76 \\  & Start variable & **3** & **3** & **3** & **3** & - & **3** \\  & Grammar size & **79** & **79** & **79** & **79** & - & **79** \\ \cline{2-8}  & Execution time & **9.99** & 14.38 & 48.85 & 85.39 & - & 14.88 \\ \hline einstein.de.txt & Rules & 49,968 & 49,949 & 50,218 & 50,057 & 49,933 & **21,787** \\  & Total length & 99,936 & 99,898 & 100,436 & 100,114 & 99,866 & **71,709** \\  & Start variable & 12,734 & 12,665 & 13,419 & **12,610** & 12,672 & 12,683 \\  & Grammar size & 112,670 & 112,563 & 113,855 & 112,724 & 112,538 & **84,392** \\ \cline{2-8}  & Execution time & **9.04** & 13.74 & 136.49 & 40.24 & 213.73 & 9.73 \\ \hline E.coli & Rules & 66,664 & 66,757 & 66,660 & 67,368 & 66,739 & **62,363** \\  & Total length & 133,328 & 133,514 & 133,320 & 134,736 & 133,478 & **129,138** \\  & Start variable & 651,875 & **649,660** & 650,538 & 652,664 & 650,209 & 650,174 \\  & Grammar size & 785,203 & 783,174 & 783,858 & 787,400 & 783,687 & **779,312** \\ \cline{2-8}  & Execution time & **0.52** & 0.65 & 9.82 & 2.00 & 11.29 & 0.58 \\ \hline bible.txt & Rules & 81,193 & 81,169 & 80,999 & 81,229 & 81,282 & **72,082** \\  & Total length & 162,386 & 162,338 & 161,998 & 162,458 & 162,564 & **153,266** \\  & Start variable & 386,514 & 386,381 & 386,992 & 386,094 & **385,989** & 386,516 \\  & Grammar size & 548,900 & 548,719 & 548,990 & 548,552 & 548,553 & **539,782** \\ \cline{2-8}  & Execution time & **0.51** & 0.65 & 8.41 & 1.85 & 11.32 & 0.57 \\ \hline world192.txt & Rules & 55,552 & 55,798 & 55,409 & 55,473 & 55,437 & **48,601** \\  & Total length & 111,104 & 111,596 & 110,812 & 110,946 & 110,874 & **104,060** \\  & Start variable & 213,131 & 213,962 & 213,245 & **212,647** & 212,857 & 212,940 \\  & Grammar size & 324,235 & 325,558 & 324,057 & 323,593 & 323,731 & **317,000** \\ \cline{2-8}  & Execution time & **0.32** & 0.55 & 4.92 & 1.09 & 6.81 & 0.36 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Sizes of generated grammars and execution times of the considered algorithms. Each cell in the table represents the number of generated rules, total lengths of the right side of all of the rules except for the start variable, length of the right side of the start variable, and the total grammar size in the order from the top row. The total grammar size presented in the fourth row is the total of the values presented in the second row and the third row. The fifth row separated by a line represents the execution time for compression in seconds. The best results are highlighted in bold.