# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 1 Introduction
Unary words have the form \(a^{n}\) for some symbol \(a\) and integer \(n\geq 1\). Grammar-based compression on unary words is strongly related to the field of addition chains, which has been studied for decades (see [16] (Chapter 4.6.3) for a survey) and still is an active topic due to the strong connection to public key cryptosystems (see [17] for a review from that point of view). An addition chain for an integer \(n\) of size \(m\) is a sequence of integers \(1=k_{1},k_{2},\dots,k_{m}=n\) such that for each \(d\) (\(2\leq d\leq m\)), there exists \(i,j\) (\(1\leq i,j<d\)) such that \(k_{i}+k_{j}=k_{d}\). It is straightforward to compute from an addition chain for an integer \(n\) of size \(m\) an SLP for \(a^{n}\) of size \(2m-2\). Vice versa, an SLP for \(a^{n}\) of size \(m\) yields an addition chain for \(n\) of size \(m\). Therefore, grammar-based compressors on unary inputs can also be thought of as addition chain solvers, i.e., algorithms that find a (small) addition chain for a given integer. The worst-case approximation ratio for global algorithms is difficult to analyze. A good starting point is therefore to analyze them on unary words because of their simplicity. Even though unary words are not interesting to compress, it is still interesting to look at how global algorithms perform on them. The improved upper bound we show for Greedy uses unary words and is the first improvement that happened in 15 years. We show the worst-case approximation ratio of RePair and LongestMatch for unary words to be \(\log_{2}(3)\). Both algorithms are basically identical to the binary method that produces an addition chain for \(n\) by creating powers of two using repeated squaring, and then the integer \(n\) is represented as the sum of those powers of two that correspond to a one in the binary representation of \(n\). Based on that information, we show that for any unary input \(w\) the produced SLPs of RePair and LongestMatch have size at most \(\log_{2}(3)\cdot g(w)\) and we also provide a lower bound. We improve the upper bound for the approximation ratio of Greedy on unary words to \(\mathcal{O}((\log n)^{8}\cdot(\log\log n)^{3})\). In [18], which is the previous version of this article, the authors showed an upper bound for the approximation ratio of Greedy of \(\mathcal{O}(n^{1/4}/\log n)\) for unary inputs, by only analyzing the first three rounds. Here, we present a more in-depth analysis that makes use of every round. We can prove that Greedy produces an SLP of size \(\mathcal{O}((\log n)^{9}\cdot(\log\log n)^{3})\) on input \(a^{n}\), which together with the fact that a smallest SLP for \(a^{n}\) has size \(\Omega(\log n)\) then yields the improved upper bound of \(\mathcal{O}((\log n)^{8}\cdot(\log\log n)^{3})\). To prove the size bound on the SLP produced by Greedy, we distinguish unary and nonunary nonterminals. A nonterminal \(X\) is called unary if its right-hand side is of the form \(X\to Z^{d}\) when it is first introduced. Otherwise, it is nonunary. We bound the total number of occurrences of all unary and nonunary nonterminals in the grammar produced by Greedy separately. For the unary nonterminals, we bound their total number to be \(\mathcal{O}((\log n)^{9})\), while each of them contributes a size of \(\mathcal{O}(\log\log n)\), which yields a total size contribution of \(\mathcal{O}((\log n)^{9}\cdot\log\log n)\). We then bound the number of occurrences of nonunary nonterminals using the already established number of unary nonterminals, which comes out to be \(\mathcal{O}((\log n)^{9}\cdot(\log\log n)^{3})\). Thus, we obtain the desired upper bound on the size of the grammar. We also show the lower bound of \(1.34847194\dots\) for the approximation ratio of Greedy. The key to achieve this bound is the sequence \(y_{k}=y_{k-1}^{2}+1\) with \(y_{0}=2\), which has been studied in [19] (among other sequences), where it is shown that \(y_{k}=\lfloor\gamma^{2^{k}}\rfloor\) for \(\gamma=2.258\dots\).