# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 1 Introduction  
The goal of grammar-based compression is to represent a word \(w\) by a small context-free grammar that produces exactly \(\{w\}\). Such a grammar is called a straight-line program (SLP) for \(w\). In the best case, one gets an SLP of size \(\Theta(\log n)\) for a word of length \(n\), where the size of an SLP is the total length of all right-hand sides of the rules of the grammar. A grammar-based compressor is an algorithm that produces an SLP for a given word \(w\). There are various grammar-based compressors that can be found in many places in the literature. A well-known example is the classic LZ78-compressor of Lempel and Ziv [1]. Although it was not introduced as a grammar-based compressor, it is straightforward to compute from the LZ78-factorization of \(w\) an SLP for \(w\) of roughly the same size. Other examples include BISECTION[2] and SEQUITUR[3]. In this work, we study the global grammar-based compressors Greedy[4, 5, 6], RePair[7] and LongestMatch[8], to which we will also refer to as global algorithms. Global algorithms are important in practice because they show excellent compression results in various fields. For example, Greedy is used in [5] to compress DNA sequences. Among all global algorithms, RePair is probably the most used one. Examples include compressing web graphs [9], searching compressed text [10], suffix array compression [11] and compressing XML [12]. A key concept of global compressors are maximal strings. A maximal string of an SLP \(A\) is a word that has length at least two and occurs at least twice without overlap as a factor of the right-hand sides of the rules of \(A\). Furthermore, no strictly longer word appears at least as many times without overlap as a factor of the right-hand sides of \(A\). For an input word \(w\), a global grammar-based compressor starts with the SLP that has a single rule \(S\to w\), where \(S\) is the start nonterminal of the grammar. The SLP is then recursively updated by choosing a maximal string \(\gamma\) of the current SLP and replacing a maximal set of pairwise nonoverlapping occurrences of \(\gamma\) by a new nonterminal \(X\). Additionally, a new rule \(X\to\gamma\) is introduced. The algorithm stops when the obtained SLP has no maximal string. In thecase of Greedy the chosen maximal string minimizes the size of the SLP in each round, while RePair selects in each round a most frequent maximal string, and LongestMatch chooses a longest maximal string. Please note that the Greedy algorithm as originally presented in [4; 5; 6] is different from the version studied in this work as well as in [13]: The original Greedy algorithm only considers the right-hand side of the start rule for the choice and the replacement of the maximal string. In particular, all other rules do not change after they are introduced. In [13] the worst-case approximation ratio of grammar-based compressors is studied. For a grammar-based compressor \(\mathcal{C}\) that computes an SLP \(\mathcal{C}(w)\) for a given word \(w\), one defines the approximation ratio of \(\mathcal{C}\) on \(w\) as the quotient of the size of \(\mathcal{C}(w)\) and the size \(g(w)\) of a smallest SLP for \(w\). The approximation ratio \(\alpha_{\mathcal{C}}(n)\) is the maximal approximation ratio of \(\mathcal{C}\) among all words of length \(n\). In [13] the authors provide upper and lower bounds for the approximation ratios of several grammar-based compressors (among them are all compressors mentioned so far), but for none of the compressors the lower and upper bounds match. For LZ78 and BISECTION these gaps were closed in [14]. For all global algorithms the best upper bound on the approximation ratio is \(\mathcal{O}((n/\log n)^{2/3})\)[13], while the best known lower bounds so far are \(\Omega(\log n/\log\log n)\) for RePair [15], \(\Omega(\log\log n)\) for LongestMatch and \(5/(3\log_{3}(5))=1.137\dots\) for Greedy[13]. In general, the achieved bounds \"leave a large gap of understanding surrounding the global algorithms\" as the authors in [13] conclude.