# Practical Grammar Compression Based on Maximal Repeats +
## 4 MR-RePair
### MR-RePair  
The grammar size of Naive-MR-RePair becomes larger than that of RePair as shown in Theorem 4 because Naive-MR-RePair cannot replace all occurrences of most frequent maximal repeats if it overlaps with another occurrence of itself. In the remainder of this section, we describe MR-RePair, which is an improved version of Naive-MR-RePair. **Definition 3** (MR-RePair). : _For an input text \(T\), let \(G=\{V,\Sigma,S,R\}\) be the grammar generated by MR-RePair. MR-RePair constructs \(T\) through the following steps:_  
**Step 1. **_Replace each symbol \(a\in\Sigma\) with a new variable \(v_{a}\) and add \(v_{a}\to a\) to \(R\)._  
**Step 2. **_Find the most frequent maximal repeat \(r\) in \(T\)._  
**Step 3. **_Check if \(|r|>2\) and \(r[1]=r[|r|]\), and if so, use \(r[1..|r|-1]\) instead of \(r\) in_ **Step 4**_._  
**Step 4. **_Replace every occurrence of \(r\) with a new variable \(v\) and then add \(v\to r\) to \(R\)._  
**Step 5. **_Re-evaluate the frequencies of maximal repeats for the updated text generated in_ **Step 4**_. If the maximum frequency is 1, add \(S\rightarrow(\text{current text})\) to \(R\) and terminate. Otherwise, return to_ **Step 2**_._  
We can easily extend the concept of the MR-order to MR-RePair. We do not care if it uses \(r[2..|r|]\) in **Step 3**, instead of \(r[1..|r|-1]\). MR-RePair can replace all occurrences of \(r\) even if it overlaps with itself in some occurrences since, according to Lemma 3, the length of the overlaps of the most frequent maximal repeats is at most 1. If \(r[1]=r[|r|]\) but \(r\) does not overlap with itself, then \(vr[|r|]\) becomes the most frequent maximal repeat after \(r[1..|r|-1]\) is replaced by \(v\) and \(vr[|r|]\) is replaced immediately. Similar to RePair, MR-RePair still cannot replace all of them if \(|r|=2\). Figure 3 illustrates an example of the grammar generation process of MR-RePair. Although the size of the grammar generated by MR-RePair as shown in Figure 3 is larger than that generated by Naive-MR-RePair as shown in Figure 2, it is still smaller than that generated by RePair as shown in Figure 1.  
**Theorem 5**: _Assume that RePair and MR-RePair work based on the same MR-order for a given text. Let \(g_{rp}\) and \(g_{nr}\) be the sizes of the grammars generated by RePair and MR-RePair, respectively. Then, \(\frac{1}{2}g_{rp}<g_{nr}\leq g_{rp}\) holds._ \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \cline{2-11} \multicolumn{1}{c|}{} & a & b & r & a & c & a & d & a & b & r & a \\ \hline \(v_{a}\rightarrow\alpha\ (\alpha=\texttt{a},\texttt{b},\texttt{r},\texttt{c},\texttt{d})\) & \(v_{a}\) & \(v_{b}\) & \(v_{r}\) & \(v_{a}\) & \(v_{c}\) & \(v_{a}\) & \(v_{d}\) & \(v_{a}\) & \(v_{b}\) & \(v_{r}\) & \(v_{a}\) \\ \hline \(v_{1}\rightarrow v_{a}v_{b}v_{r}\) & & \(v_{1}\) & \(v_{a}\) & \(v_{c}\) & \(v_{a}\) & \(v_{d}\) & & \(v_{1}\) & & \(v_{a}\) \\ \hline \(v_{2}\rightarrow v_{1}v_{a}\) & & \(v_{2}\) & & \(v_{c}\) & \(v_{a}\) & \(v_{d}\) & & \(v_{2}\) & \\ \hline \(S\rightarrow v_{2}v_{c}v_{a}v_{d}v_{2}\) & & & & \(S\) & & & & & & \\ \hline \end{tabular}   
**Figure 3.** An example of the grammar generation process of MR-RePair for the text abracadabra. The generated grammar is \(\{\{v_{a},v_{b},v_{r},v_{c},v_{d},v_{1}\},\{\texttt{a},\texttt{b},\texttt{r}, \texttt{c},\texttt{d}\},S,\{v_{a}\rightarrow\texttt{a},v_{b}\rightarrow\texttt{ b},v_{r}\rightarrow\texttt{r},v_{c}\rightarrow\texttt{c},v_{d} \rightarrow\texttt{d},v_{1}\rightarrow v_{a}v_{b}v_{r},v_{2}\rightarrow v_{1}v_{a},S\rightarrow v_{2}v_{c}v_{a}v_{d}v_{2}\}\) with a size of 15. Proof. : Assume that \(G_{rp}=\{V_{rp},\Sigma_{rp},S_{rp},R_{rp}\}\) and \(G_{mr}=\{V_{mr},\Sigma_{mr},S_{mr},R_{mr}\}\) are grammars generated by RePair and MR-RePair, respectively, for a given text \(T\) with a length of \(n\).