# Practical Grammar Compression Based on Maximal Repeats +
## 4 MR-RePair
### Naive-MR-RePair  
**Definition 2** (Naive-MR-RePair). : _For an input text \(T\), let \(G=\{V,\Sigma,S,R\}\) be the grammar generated by Naive-MR-RePair. Naive-MR-RePair constructs \(G\) 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. **_Replace every occurrence (or as many occurrences as possible, when there are overlaps) of \(r\) in \(T\) with a new variable \(v\) and then add \(v\to r\) to \(R\)._  
**Step 4. **_Re-evaluate the frequencies of maximal repeats for the updated text generated in_ **Step 3**_. If the maximum frequency is 1, add \(S\to(\text{current text})\) to \(R\) and terminate. Otherwise, return to_ **Step 2**_._  
We can easily extend the concept of the MR-order to Naive-MR-RePair. Figure 2 illustrates an example of the grammar generation process of Naive-MR-RePair. Figures 1 and 2 explain why the strategy of using maximal repeats is more effective compared to that using pairs. When compressing the text \(v_{a}v_{b}v_{\tau}v_{a}v_{c}v_{a}v_{d}v_{a}v_{b}v_{\tau}v_{a}\), both RePair and Naive-MR-RePair generate subgrammars deriving the most frequent maximal repeat \(v_{a}v_{b}v_{\tau}v_{a}\). The rule set of the subgrammar generated by RePair is \(\{v_{1}\to v_{a}v_{b},v_{2}\to v_{1}v_{\tau},v_{3}\to v_{2}v_{a}\}\) with a size of 6. At the same time, the rule set of the subgrammar generated by Naive-MR-RePair is \(\{v_{1}\to v_{a}v_{b}v_{\tau}v_{a}\}\) with a size of 4. However, the following theorem indicates that the size of the grammar generated by Naive-MR-RePair is larger than that generated by RePair in certain cases, even when they work in the same MR-order. Roughly speaking, this is caused by the overlaps of maximal repeats. When there is an occurrence of the most frequent maximal repeat that overlaps with its occurrence, little difference would arise in grammar constructing processes of RePair and Naive-MR-RePair from the view point of maximal repeats, that is, the targeted maximal repeats would vary in RePair and in Naive-MR-RePair (RePair replaces the targeted maximal repeat step by step and Naive-MR-RePair replaces it at once). Indeed, if maximal repeats are carefully embedded in a text for increasing the difference, the case presented in the following theorem occurs. **Theorem 4**. : _Given a text \(T\) with a length of \(n\), let \(g_{rp}\) and \(g_{nmr}\) be the sizes of the grammars generated by RePair and Naive-MR-RePair for \(T\), respectively, assuming that RePair and Naive-MR-RePair work in the same MR-order. Then, there is a case when \(g_{nmr}=g_{rp}+\Omega(\log n)\) holds. (We show a concrete example of this theorem in Appendix A. )_  
Proof. : Let \(G_{rp}=\{V_{rp},\Sigma_{rp},S_{rp},R_{rp}\}\) and \(G_{mmr}=\{V_{nmr},\Sigma_{nmr},S_{nmr},R_{nmr}\}\) be the grammars generated by RePair and Naive-MR-RePair, respectively. Let \(T^{\prime}\) be the text generated just after **Step 1** of RePair or Naive-MR-RePair (the **Step 1** is common in both algorithms), that is, \(T^{\prime}=v_{1}\cdots v_{n}\) such that \(v_{i}\in V_{rp}\cap V_{mmr}\) and \(v_{i}\to T[i]\in R_{rp}\cap R_{mmr}\) (for \(i=1,\cdots,n\)), and \(\hat{G}_{rp}=\{\hat{V}_{rp},\hat{\Sigma}_{rp},\hat{S}_{rp},\hat{R}_{rp}\}\) (or \(\hat{G}_{nmr}=\{\hat{V}_{nmr},\hat{\Sigma}_{nmr},\hat{S}_{nmr},\hat{R}_{nmr}\}\)) be a subgrammar of \(G_{rp}\) (or \(G_{nmr}\)) deriving \(T^{\prime}\). Let \(T^{\prime}=(uw)^{2^{n+1}-1}u\), where \(u\in V_{rp}\cap V_{mmr}\), \(w\in(V_{rp}\cap V_{mmr})^{+}\) such that \(uwu\) is the most frequent maximal repeat of \(T^{\prime}\), and \(m\in\mathbb{N}^{+}\). Note that \(2^{m+1}-1=\sum_{i=0}^{m}2^{i}\).