# Practical Grammar Compression Based on Maximal Repeats +
## 3 Analysis of RePair
### Greatest Size Difference of RePair  
We consider the problem of determining the greatest size difference between possible outcomes of RePair.  
**Definition 1** (Greatest size difference).: _Let \(g\) and \(g^{\prime}\) be the sizes of any two possible grammars that can be generated by RePair for a given text. Then, the greatest size difference of RePair (GSDRP) is \(\max(|g-g^{\prime}|)\)._  
A lower bound of the GSDRP can be established according to the following theorem.  
**Theorem 3**.: _Given a text with a length of \(n\), a lower bound of GSDRP is \(\frac{1}{6}(\sqrt{6n+1}+13)\)._  
Proof.: Let \(B\), \(L\), and \(R\) be strings such that  
\[B =l_{1}xyr_{1}l_{2}xyr_{2}\cdots l_{f-1}xyr_{f-1}l_{f}xyr_{f},\] \[L =\Diamond l_{1}x\Diamond l_{2}x\cdots\Diamond l_{f}x,\] \[R =\Diamond yr_{1}\Diamond yr_{2}\cdots\Diamond yr_{f},\]  
where \(x,y,l_{1},\ldots,l_{f},r_{1},\ldots,r_{f}\) denote distinct symbols, and each occurrence of \(\Diamond\) denotes a distinct symbol. Consider text \(T=BL^{f-1}R^{f-1}\). Here, \(xy\), \(l_{1}x\), \(\cdots\), \(l_{f}x\), \(yr_{1}\), \(\cdots\), \(yr_{f}\) are the most frequent maximal repeats with a frequency \(f\) in \(T\). Let \(G\) and \(G^{\prime}\) be grammars generated by RePair for \(T\) in different MR-order, such that (i) \(xy\) precedes all other maximal repeats and (ii) \(xy\) follows all other maximal repeats, respectively. We denote the sizes of \(G\) and \(G^{\prime}\) as \(g\) and \(g^{\prime}\), respectively.  
First, we consider \(G\) and how RePair generates it. The first rule generated by the replacement is \(v_{1}\to xy\) considering the MR-order. After the replacement, \(L\) and \(R\) remain unchanged, whereas \(B\) becomes the following text:  
\[B_{1}=l_{1}v_{1}r_{1}l_{2}v_{1}r_{2}\cdots l_{f-1}v_{1}r_{f-1}l_{f}v_{1}r_{f}.\]  
Each pair in \(B_{1}\) occurs only once in the entire text \(B_{1}L^{f-1}R^{f-1}\). This means that \(B_{1}\) can never be shortened from the current length of \(3f\). In the remaining steps, \(l;x\) and \(yr_{i}\) (for \(i=1,\cdots,f\)) are replaced. \(L\) and \(R\) are changed to texts with a length of \(2f\) each. Hence, the following holds:  
\[g=3f+2\cdot 2f+2(1+2f)=11f+2. \tag{1}\]  
Next, we consider \(G^{\prime}\) and how RePair generates it. According to their MR-order, \(l_{1}x\), \(\cdots\), \(l_{f}x\), \(yr_{1}\), \(\cdots\), \(yr_{f}\) are replaced before \(xy\) is selected. They do not overlap with each other, and after they are replaced, \(xy\) does not occur in the generated text. Therefore, there are \(2f\) rules in \(G^{\prime}\) deriving \(l_{i}x\) and \(yr_{i}\) (for \(i=1,\cdots,f\)), whereas the rule deriving \(xy\) is absent. \(L\) and \(R\) are changed to texts with a length of \(2f\) each, and \(B\) is changed to a text with a length \(2f\). Hence, the following holds:  
\[g^{\prime}=2f+2\cdot 2f+2\cdot 2f=10f. \tag{2}\]  
Let us denote the length of the original text \(T=BL^{f-1}R^{f-1}\) by \(n\). Then, the following holds:  
\[n=4f+2(3f)(f-1)=6f^{2}-2f.\]  
Therefore,  
\[f=\frac{1}{6}(\sqrt{6n+1}+1) \tag{3}\]holds. According to Equations (1)-(3),  
\[g-g^{\prime} =11f+2-10f=f+2\] \[=\frac{1}{6}(\sqrt{6n+1}+13)\]  
holds and the theorem follows.