# Practical Grammar Compression Based on Maximal Repeats +
## 4 MR-RePair
### MR-RePair
Since every \(l_{i}^{(f_{j})}\geq 2\) and \(|T_{rp}^{(f_{k})}|=|T_{mr}^{(f_{k})}|\), \(\frac{1}{2}g_{rp}<g_{mr}\leq g_{rp}\) follows Equations (11) and (12), and thus, the proposition holds. \(g_{mr}=g_{rp}\) holds when every length \(l_{i}^{(f_{j})}\) is \(2\). However, when the MR-orders of RePair and MR-RePair are different, then the grammar generated by MR-RePair can be larger than that generated by RePair, as the following theorem indicates:  
**Theorem 6**. : _Unless the MR-order of RePair and MR-RePair are the same, there is a case where the size of the grammar generated by MR-RePair becomes larger than that generated by RePair._  
Proof. : We show a concrete example of the case stated in the proposition. Consider text abcxabcyab czcxcxcycyczcz. There are four most-frequent maximal repeats, abc, cx, cy, and cz. Let \(A\) and \(B\) be two different MR-orders such that \(A\) prioritizes the maximal repeats in order of abc, cx, cy, cz and \(B\) prioritizes the maximal repeats in order of cx, cy, cz, abc, respectively. MR-RePair working in \(A\) generates a grammar whose rules are \(\{v_{\mathtt{a}}\rightarrow\mathtt{a},v_{\mathtt{b}}\rightarrow\mathtt{b},v_{ \mathtt{c}}\rightarrow\mathtt{c},v_{\mathtt{x}}\rightarrow\mathtt{x},v_{ \mathtt{y}}\rightarrow\mathtt{y},v_{\mathtt{z}}\rightarrow\mathtt{z},v_{ \mathtt{1}}\rightarrow v_{\mathtt{a}}v_{\mathtt{b}}v_{\mathtt{c}},v_{\mathtt{2 }}\rightarrow v_{\mathtt{c}}v_{\mathtt{x}},v_{\mathtt{3}}\to v_{ \mathtt{c}}v_{\mathtt{y}},v_{\mathtt{4}}\rightarrow v_{\mathtt{c}}v_{\mathtt{2 }},S\to v_{1}xv_{1}yv_{1}zv_{2}v_{2}v_{3}v_{3}v_{4}v_{4}\}\), where \(S\) is the start variable. Meanwhile, RePair working in \(B\) generates a grammar whose rules are \(\{v_{\mathtt{a}}\rightarrow\mathtt{a},v_{\mathtt{b}}\rightarrow\mathtt{b},v_{ \mathtt{c}}\rightarrow\mathtt{c},v_{\mathtt{x}}\rightarrow\mathtt{x},v_{ \mathtt{y}}\rightarrow\mathtt{y},v_{\mathtt{z}}\rightarrow\mathtt{z},v_{ \mathtt{1}}\rightarrow v_{\mathtt{c}}v_{\mathtt{x}},v_{\mathtt{2}}\rightarrow v_{ \mathtt{c}}v_{\mathtt{y}},v_{\mathtt{3}}\rightarrow v_{\mathtt{c}}v_{\mathtt{ z}},v_{\mathtt{4}}\rightarrow v_{\mathtt{a}}v_{\mathtt{b}},S\to v_{\mathtt{4}}v_{ \mathtt{1}}v_{\mathtt{4}}v_{\mathtt{2}}v_{\mathtt{4}}v_{\mathtt{3}}v_{\mathtt{ 1}}v_{\mathtt{2}}v_{\mathtt{2}}v_{\mathtt{3}}v_{\mathtt{3}}\}\), where \(S\) is the start variable. The size of the grammar generated by MR-RePair working in \(A\) is \(27\), whereas the size of that generated by RePair working in \(B\) is \(26\). While Theorem 6 indicates that the grammar can be larger in MR-RePair than in RePair, in Section 5 we demonstrate that MR-RePair outperforms RePair in practice. We can implement MR-RePair by extending the original implementation of RePair stated in [2] and holding the same complexity. **Theorem 7**. : _Let \(G=\{V,\Sigma,S,R\}\) be the grammar generated by MR-RePair for a given text with a length of \(n\). Then, MR-RePair works in \(\mathcal{O}(n)\) expected time and \(5n+4k^{2}+4k^{\prime}+\lceil\sqrt{n+1}\rceil-1\) word space, where \(k\) and \(k^{\prime}\) denote the cardinalities of \(\Sigma\) and \(V\), respectively._  
Proof. : Compared to RePair, the additional operations performed by MR-RePair are (i) extending the selected pair to left and right until it becomes a maximal repeat and (ii) checking and excluding either the beginning or the end of the obtained maximal repeat if they are the same. These additional operations can be realized using the same data structures as those employed in RePair. Then, the space complexity of MR-RePair follows Lemma 1. We can clearly execute operation (ii) in a constant time. Hence, we consider how the time complexity is affected by operation (i). Let \(l\) be the length of the maximal repeat containing the focused pair, as well as \(f\) be the frequency of the pair. Then, \(\mathcal{O}(fl)\) more time is required for MR-RePair to check the left- and right-extensions for all occurrences of the focused pair compared to RePair.