# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 5 RePair and LongestMatch  
In this section, we analyze the global grammar-based compressors RePair and LongestMatch. In each round \(i\), RePair selects a most frequent maximal string of \(\mathbb{A}_{i-1}\) and LongestMatch selects a longest maximal string of \(\mathbb{A}_{i-1}\). We will abbreviate the approximation ratio \(\alpha_{\text{LongestMatch}}\) by \(\alpha_{\text{LM}}\) for better readability. We will first show that RePair and LongestMatch produce SLPs of equal size for unary inputs \(a^{n}\) and we show what the exact size of these SLPs depending on \(n\) is. We then use this information to obtain our result for \(\alpha_{\text{RePair}}(1,n)\) and \(\alpha_{\text{LM}}(1,n)\), respectively. Fix an integer \(n\geq 2\) and consider the binary representation  
\[n=\sum_{i=0}^{\lfloor\log_{2}n\rfloor}b_{i}\cdot 2^{i} \tag{2}\]  
of \(n\), where \(b_{i}\in\{0,1\}\) for \(i\in[0,\lfloor\log_{2}n\rfloor]\). We denote by \(\
u(n)\) the number of \(1\)'s in the binary representation of \(n\), i.e.,  
\[\
u(n)=\sum_{i=0}^{\lfloor\log_{2}n\rfloor}b_{i}.\]  
For example, we have \(11=1\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}\) and thus \(b_{0}=b_{1}=b_{3}=1\), \(b_{2}=0\) and \(\
u(11)=3\). Proposition 2: _For \(n\geq 2\), let \(\mathbb{A}\) be the SLP produced by RePair on input \(a^{n}\) and \(\mathbb{B}\) be the SLP produced by LongestMatch on input \(a^{n}\). We have_  
\[|\mathbb{A}|=|\mathbb{B}|=2\lfloor\log_{2}n\rfloor+\
u(n)-1.\]  
Proof: If \(n=2\) or \(n=3\) then \(a^{n}\) has no maximal string and thus the final SLP of any global algorithm has a single rule \(S\to a^{n}\). The reader can easily verify the claimed result for these cases. We now assume that \(n\geq 4\). Let \(m=\lfloor\log_{2}n\rfloor-1\). We prove the claim for RePair first and for LongestMatch after. On input \(a^{n}\), RePair runs for exactly \(m\) rounds and creates rules\(X_{1}\to aa\) and \(X_{i}\to X_{i-1}X_{i-1}\) for \(i\in[2,m]\), i.e., the nonterminal \(X_{i}\) produces the string \(a^{2^{i}}\). These rules have a total size of \(2m\). After these steps, the start rule is  
\[S\to X_{m}X_{m}X_{m}^{b_{m}}X_{m-1}^{b_{m-1}}\cdots X_{1}^{b_{1}}a^{b_{0}},\]  
where the \(b_{i}\)'s are the coefficients occurring in the binary representation of \(n\), see equation (2). In other words, the symbol \(a\) only occurs in the start rule if the least significant bit is \(b_{0}=1\), and the nonterminal \(X_{i}\) (\(i\in[1,m-1]\)) occurs in the start rule if and only if \(b_{i}=1\). Since \(\mathsf{RePair}\) only replaces words with at least two occurrences, the most significant bit \(b_{m+1}=1\) is represented by \(X_{m}X_{m}\). A third \(X_{m}\) occurs in the start rule if and only if \(b_{m}=1\). The size of the start rule is \(2+\sum_{i=0}^{m}b_{i}\). It follows that the total size of the SLP produced by \(\mathsf{RePair}\) on input \(a^{n}\) is \(2m+2+\sum_{i=0}^{m}b_{i}\), which together with \(m=\lfloor\log_{2}n\rfloor-1\) and \(b_{\lfloor\log_{2}n\rfloor}=1\) (the most significant bit is always 1) yields the claimed size. Now we prove the same result for LongestMatch. In the first round, the chosen maximal string is \(a^{\lfloor n/2\rfloor}\), which yields rules \(X_{1}\to a^{\lfloor n/2\rfloor}\) and \(S\to X_{1}X_{1}a^{b_{0}}\), i.e., the symbol \(a\) occurs in the start rule if and only if \(n\) is odd and thus the least significant bit is \(b_{0}=1\). Assuming that \(n\geq 8\), this procedure is now repeated for the rule \(X_{1}\to a^{\lfloor n/2\rfloor}\) (for \(n<8\) there is no maximal string, and the algorithm stops after the first round). This yields \(X_{2}\to a^{\lfloor n/4\rfloor}\), \(X_{1}\to X_{2}X_{2}a^{b_{1}}\) and \(S\to X_{1}X_{1}a^{b_{0}}\) (note that \(\lfloor(\lfloor n/2\rfloor)/2\rfloor=\lfloor n/4\rfloor\)). After \(m=\lfloor\log_{2}n\rfloor-1\) steps, the iteration of this process results in the final SLP with rules \(S\to X_{1}X_{1}a^{b_{0}}\), \(X_{1}\to X_{1}X_{i+1}a^{b_{i}}\) for \(i\in[1,m-1]\) and \(X_{m}\to aa^{b_{m}}\).