# Practical Grammar Compression Based on Maximal Repeats +
## 3 Analysis of RePair
### RePair and Maximal Repeats  
The following theorem describes an essential property of RePair, that is, RePair recursively replaces the most frequent maximal repeats. **Theorem 1**. : _Let \(T\) be a given text, assuming that every most frequent maximal repeat of \(T\) does not appear with overlaps with itself. Let \(f\) be the frequency of the most frequent pairs of \(T\), and \(t\) be a text obtained after all pairs with frequency \(f\) in \(T\) are replaced by variables. Then, there is a text \(s\) such that \(s\) is obtained after all maximal repeats with frequency \(f\) in \(T\) are replaced by variables, and \(s\) and \(t\) are isomorphic to each other._  
We need two lemmas and a corollary to prove Theorem 1. The following lemma shows a fundamental relation between the most frequent maximal repeats and the most frequent pairs in a text. **Lemma 2**. : _A pair \(p\) of variables is most frequent in a text \(T\) if and only if \(p\) occurs once in exactly one of the most frequent maximal repeats of \(T\)._  
Proof. : (\(\Rightarrow\)) Let \(r\) be a most frequent maximal repeat containing \(p\) as a substring. It is clear that \(p\) can only occur once in \(r\), since otherwise, \(\#\text{occ}(p)>\#\text{occ}(r)\) would hold, implying the existence of a frequent maximal repeat that is more frequent than \(r\), contradicting the assumption that \(r\) is most frequent. Suppose that there exists a different most frequent maximal repeat \(r^{\prime}\) containing \(p\) as a substring. Similarly, \(p\) occurs only once in \(r^{\prime}\). Furthermore, since \(r\) and \(r^{\prime}\) can be obtained by left and right extensions to \(p\), \(\#\text{occ}(r)=\#\text{occ}(r^{\prime})=\#\text{occ}(p)\), and any occurrence of \(p\) is contained in an occurrence of both \(r\) and \(r^{\prime}\). Since \(r^{\prime}\) cannot be a substring of \(r\), there exists a string \(w\) that is a superstring of \(r\) and \(r^{\prime}\), such that \(\#\text{occ}(w)=\#\text{occ}(r)=\#\text{occ}(r^{\prime})=\#\text{occ}(p).\) However, this contradicts that \(r\) and \(r^{\prime}\) are maximal repeats. (\(\Leftarrow\)) Let \(r\) be the most frequent maximal repeat such that \(p\) occurs once in it. By definition, \(\#\text{occ}(r)=\#\text{occ}(p)\). If \(p\) is not the most frequent symbol pair in \(T\), there exists a pair \(p^{\prime}\) in \(T\) such that \(\#\text{occ}(p^{\prime})>\#\text{occ}(p)=\#\text{occ}(r)\). However, this implies that there is a maximal repeat \(r^{\prime}\) with \(\#\text{occ}(r^{\prime})=\#\text{occ}(p^{\prime})>\#\text{occ}(r)\), contradicting that \(r\) is most frequent. \(\qed\)  
The following corollary is derived directly from Lemma 2. Corollary 1: _For a given text, the frequency of the most frequent pairs and that of the most frequent maximal repeats are the same._  
The following lemma shows an important property of the most frequent maximal repeats. Lemma 3: _The length of the overlap between any two occurrences of most frequent maximal repeats is at most \(1\)._  
Proof: Let \(xw\) and \(wy\) be the most frequent maximal repeats that have an overlapping occurrence \(xwy\), where \(x,y,w\in\Sigma^{+}\). If we assume that \(|w|\geq 2\), since \(xw\) and \(wy\) are most frequent maximal repeats, it holds that \(\#\text{occ}(w)=\#\text{occ}(xw)=\#\text{occ}(wy)\), i.e., every occurrence of \(w\) is preceded by \(x\) and followed by \(y\). This implies that \(\#\text{occ}(xwy)=\#\text{occ}(xw)=\#\text{occ}(wy)\) as well, but contradicts that \(xw\) and \(wy\) are maximal repeats. \(\qed\)  
Theorem 1 can now be proved based on the above lemmas and corollary. Proof of Theorem 1: According to Corollary 1, the frequency of the most frequent maximal repeats in \(T\) is \(f\). Let \(p\) be one of the most frequent pairs in \(T\). According to Lemma 2, there is a unique maximal repeat that is most frequent and contains \(p\) once. We denote such maximal repeat as \(r\). Let us assume that there is a substring \(zxpyw\) in \(T\), where \(z,w\in\Sigma\), \(x,y\in\Sigma^{*}\), and \(xpy=r\).