# Practical Grammar Compression Based on Maximal Repeats +
## 4 MR-RePair
### MR-RePair
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_{mr}\) and \(v_{i}\to T[i]\in R_{rp}\cap R_{mr}\) (for \(i=1,\cdots,n\)). Let \(f_{1}\) be the maximum frequency of the maximal repeats in \(T^{\prime}\). According to Corollary 1, the maximum frequency of the pairs in \(T^{\prime}\) is also \(f_{1}\). Let \(\hat{G}_{rp}^{(f_{1})}\) (or \(\hat{G}_{mr}^{(f_{1})}\)) be a subgrammar of \(G_{rp}\) (or \(G_{mr}\)) generated while RePair (or MR-RePair) replaces pairs (or maximal repeats) with the frequency \(f_{1}\), \(\hat{g}_{rp}^{(f_{1})}\) (or \(\hat{g}_{mr}^{(f_{1})}\)) be the size of this subgrammar, and \(T_{rp}^{(f_{1})}\) (or \(T_{mr}^{(f_{1})}\)) be the updated text after all pairs (or maximal repeats) with the frequency \(f_{1}\) are replaced. Let \(r_{1}^{(f_{1})},\cdots,r_{m_{1}}^{(f_{1})}\) be maximal repeats with frequency \(f_{1}\) in \(T^{\prime}\) assuming that they are prioritized in this order by the MR-order. Let \(l_{i}^{(f_{1})}\) (for \(i=1,\cdots,m_{1}\)) be the length of the longest substring of \(r_{i}^{(f_{1})}\) such that there are variables that derive the substring in both \(\hat{G}_{rp}^{(f_{1})}\) and \(\hat{G}_{mr}^{(f_{1})}\). Note that this substring is common to RePair and MR-RePair, and each \(l_{i}^{(f_{1})}\) is at least 2. Since RePair replaces such substring step by step and MR-RePair replaces it at once, the following holds:  
\[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\] \[\hat{g}_{mr}^{(f_{1})} =\sum_{i=1}^{m_{1}}l_{i}^{(f_{1})}. \tag{7}\]From these,  
\[\hat{g}_{rp}^{(f_{1})}-\hat{g}_{mr}^{(f_{1})} =2\sum_{i=1}^{m_{1}}l_{i}^{(f_{1})}-2m_{1}-\sum_{i=1}^{m_{1}}l_{i}^{( f_{1})}\] \[=\sum_{i=1}^{m_{1}}l_{i}^{(f_{1})}-2m_{1}\] \[\geq 2m_{1}-2m_{1}=0\ \ (\because l_{i}\geq 2\ \ \text{holds for each $i$}).\]  
Hence,  
\[\hat{g}_{mr}^{(f_{i})}\leq\hat{g}_{rp}^{(f_{i})} \tag{8}\]  
holds. According to Equation (6),  
\[\hat{g}_{rp}^{(f_{1})} =2\sum_{i=1}^{m_{1}}l_{i}^{(f_{1})}-2m_{1}\] \[=2\hat{g}_{mr}^{(f_{1})}-2m_{1}\ \ \ (\text{by Equation \eqref{eq:g_rp}}).\]  
Hence,  
\[\frac{1}{2}\hat{g}_{rp}^{(f_{1})}<\hat{g}_{mr}^{(f_{1})} \tag{9}\]  
holds. Therefore, according to Equations (8) and (9),  
\[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\]0  
holds. The updated texts \(T_{rp}^{(f_{1})}\) and \(T_{mr}^{(f_{1})}\) are isomorphic for \(V_{rp}\) and \(V_{mr}\). Let \(f_{2}\) be the maximum frequency of the maximal repeats in \(T_{rp}^{(f_{1})}\) (and \(T_{mr}^{(f_{1})}\)). Then, a similar analysis holds for \(\hat{G}_{rp}^{(f_{2})}\) and \(\hat{G}_{mr}^{(f_{2})}\). Hence, \(\frac{1}{2}\hat{g}_{rp}^{(f_{2})}<\hat{g}_{mr}^{(f_{2})}\leq\hat{g}_{rp}^{(f_{ 2})}\) holds similarly to Equation (10), and the updated texts \(T_{rp}^{(f_{2})}\) and \(T_{mr}^{(f_{2})}\) are isomorphic. Inductively, for every maximum frequency of maximal repeats \(f_{i}\), \(\frac{1}{2}\hat{g}_{rp}^{(f_{i})}<\hat{g}_{mr}^{(f_{i})}\leq\hat{g}_{rp}^{(f_{ i})}\) holds and the updated texts \(T_{rp}^{(f_{i})}\) and \(T_{mr}^{(f_{i})}\) are isomorphic. Let \(k\) be a natural number such that \(f_{k}>1\) and \(f_{k+1}=1\), that is, \(k\) is the number of times that the maximum frequency decreases through the entire process of RePair and MR-RePair. Then,  
\[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\]1 \[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\]2 \[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\]3 \[\hat{g}_{rp}^{(f_{1})} =\sum_{i=1}^{m_{1}}2(l_{i}^{(f_{1})}-1)\, \tag{6}\]4  
hold. Recall that each symbol \(a\in\Sigma\) is replaced with a new variable in the first step both in RePair and in MR-RePair. \(|\Sigma|\) is the size of the subgrammar consisting of the rules generated in the first step.