# Practical Grammar Compression Based on Maximal Repeats +
## 3 Analysis of RePair
### MR-Order  
According to Theorem 1, if there is just one most frequent maximal repeat in the current text, then RePair replaces its all occurrences step by step. However, a problem arises if there are two or more most frequent maximal repeats, with some of them overlapping. In this case, the selection order of pairs (of course, they are most frequent) affects the priority of maximal repeats. We call this order of selecting (summarizing) maximal repeats as the _maximal repeat selection order_ (or simply _MR-order_). Note that, the selection order of pairs actually depends on the implementation of RePair. For instance, consider the text abcdeabccde, where abc and cde are the most frequent maximal repeats occurring twice. There are two MR-orders, depending on which of the two maximal repeats abc or cde is given priority. The results of the replacement using RePair with the MR-order are (i) \(xyxx\) with variables \(x\) and \(y\) such that \(x\stackrel{{*}}{{\Rightarrow}}\texttt{abc}\) and \(y\stackrel{{*}}{{\Rightarrow}}\texttt{de}\), and (ii) \(zwzw\) with variables \(z\) and \(w\) such that \(z\stackrel{{*}}{{\Rightarrow}}\texttt{ab}\) and \(w\stackrel{{*}}{{\Rightarrow}}\texttt{cde}\). More precisely, there are 12 possible ways in which RePair can compress the text, with the following generated rule sets:  
1. \(\{v_{1}\rightarrow\texttt{ab},v_{2}\rightarrow v_{1}c,v_{3}\rightarrow\texttt{ de},S\rightarrow v_{2}v_{3}v_{2}cv_{3}\}\),
2. \(\{v_{1}\rightarrow\texttt{ab},v_{2}\rightarrow\texttt{de},v_{3}\rightarrow v _{1}c,S\rightarrow v_{3}v_{2}v_{3}cv_{2}\}\),
3. \(\{v_{1}\rightarrow\texttt{bc},v_{2}\rightarrow\texttt{av}_{1},v_{3} \rightarrow\texttt{de},S\rightarrow v_{2}v_{3}v_{2}cv_{3}\}\),
4. \(\{v_{1}\rightarrow\texttt{bc},v_{2}\rightarrow\texttt{de},v_{3}\rightarrow \texttt{av}_{1},S\rightarrow v_{3}v_{2}v_{3}cv_{2}\}\),
5. \(\{v_{1}\rightarrow\texttt{ed},v_{2}\rightarrow\texttt{ab},v_{3}\rightarrow v _{2}c,S\rightarrow v_{3}v_{1}v_{3}cv_{1}\}\),
6. \(\{v_{1}\rightarrow\texttt{ed},v_{2}\rightarrow\texttt{bc},v_{3}\rightarrow v _{2}c,S\rightarrow v_{3}v_{1}v_{3}cv_{1}\}\),
7. \(\{v_{1}\rightarrow\texttt{ab},v_{2}\rightarrow\texttt{cd},v_{3}\rightarrow v _{2}c,S\rightarrow v_{1}v_{3}cv_{3}\}\),
8. \(\{v_{1}\rightarrow\texttt{ab},v_{2}\rightarrow\texttt{de},v_{3}\rightarrow c _{2}c,S\rightarrow v_{1}v_{3}v_{1}cv_{3}\}\),
9. \(\{v_{1}\rightarrow\texttt{cd},v_{2}\rightarrow\texttt{ab},v_{3}\rightarrow v _{1}e,S\rightarrow v_{2}v_{3}v_{2}cv_{3}\}\),
10. \(\{v_{1}\rightarrow\texttt{cd},v_{2}\rightarrow\texttt{v}_{1}e,v_{3} \rightarrow\texttt{ab},S\rightarrow v_{3}v_{2}v_{3}cv_{2}\}\),
11. \(\{v_{1}\rightarrow\texttt{ed},v_{2}\rightarrow\texttt{ab},v_{3}\rightarrow c _{1},S\rightarrow v_{2}v_{3}v_{2}cv_{3}\}\),
12. \(\{v_{1}\rightarrow\texttt{ed},v_{2}\rightarrow\texttt{cv}_{1},v_{3} \rightarrow\texttt{ab},S\rightarrow v_{3}v_{2}v_{3}cv_{2}\}\). Here, 1-6 have the same MR-order because abc precedes cde in all of them. At the same time, 7-12 have the same MR-order for the same reason: cde precedes abc. If there are several distinct most frequent pairs with overlaps, RePair constructs grammars with different sizes according to the selection order of the pairs. For example, consider the text bcxdabcyabzdabvbcuda. There are three most frequent pairs, namely, ab, bc, and da, occurring three times each. If RePair takes ab first, the rule set of the generated grammar may become \(\{v_{1}\rightarrow\texttt{ab},\ v_{2}\rightarrow\texttt{bc},\ v_{3} \rightarrow\texttt{dv}_{1},\ S\rightarrow v_{2}xv_{3}cyv_{1}v_{2}v_{3}v_{2} \texttt{uda}\}\) and its size is 19. If RePair takes da first, the rule set of the generated grammar may become \(\{v_{1}\rightarrow\texttt{da},\ v_{2}\rightarrow\texttt{bc},\ S \rightarrow v_{2}xv_{1}v_{2}y\texttt{ab}zv_{1}bvv_{2}w_{1}\}\) and its size is 18. **Remark 1**.