# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 2 Preliminaries  
For \(i,j\in\mathbb{N}\) we write \([i,j]=\{i,i+1,\dots,j\}\) for \(i\leq j\) and \([i,j]=\emptyset\) otherwise. For \(m,n\in\mathbb{N}\) we denote by \(m\) div \(n\) the integer division of \(m\) and \(n\). We denote by \(m\) mod \(n\) the modulo of \(m\) and \(n\), i.e., \(m\) mod \(n\in[0,n-1]\) and  
\[m=(m\text{ div }n)\cdot n+(m\text{ mod }n).\]  
If \(m/n\) or \(\frac{m}{n}\) is used, then this refers to the standard division over \(\mathbb{R}\). Please note that \(m\) div \(n=\lfloor m/n\rfloor\) and \((m\text{ div }n)+(m\text{ mod }n)\geq m/n\). An alphabet \(\Sigma\) is a finite set of symbols. For a _word_ or _string_\(w=a_{1}\cdots a_{n}\) over \(\Sigma\) with \(a_{1},\dots,a_{n}\in\Sigma\) and \(n\geq 0\) we write \(|w|=n\) to denote \(w\)'s length. The set of \(\Sigma^{*}\) consists of all words over \(\Sigma\) and \(\Sigma^{+}=\Sigma^{*}\setminus\{\epsilon\}\), where \(\epsilon\) is the word of length \(0\). A _unary word_ is a word of the form \(a^{n}\) with \(a\in\Sigma\) and \(n\in\mathbb{N}\). All other words \(w\in\Sigma^{+}\) are called _nonunary_. For words \(w,v\in\Sigma^{+}\) we say that \(v\) is a _factor_ of \(w\) if there are \(x,y\in\Sigma^{*}\) such that \(w=xvy\). A _context-free grammar_ is a tuple \((N,\Sigma,P,S)\), where \(N\) is the finite set of nonterminals, \(\Sigma\) is the alphabet with \(\Sigma\cap N=\emptyset\), \(P\) is the set of productions of the form \(X\to v\), where \(X\in N\) and \(v\in(\Sigma\cup N)^{+}\), and \(S\in N\) is the start symbol. An _SLP_ is a context-free grammar \(\mathbb{A}=(N,\Sigma,P,S)\), where  
* every \(X\in N\) has exactly one production, i.e., \[|\{(X\to v)\in P\mid v\in(\Sigma\cup N)^{+}\}|=1,\text{ and }\]
* the relation \(\{(A,B)\in N\times N\mid(A\to v)\in P,\text{ }B\text{ occurs in }v\}\) is acyclic. This way, for every \(X\in N\) there exists a unique word \(w\in\Sigma^{+}\) with \(X\to^{+}w\). We say that \(\mathbb{A}\)_produces_\(w\) if \(S\to^{+}w\). Please note that some authors require SLPs to be in Chomsky Normal Form (CNF), i.e., every production is of the form \(A\to BC\), where \(B,C\in N\) or \(A\to a\), where \(a\in\Sigma\). We do not make this assumption here because, in general, grammar-based compressors produce SLPs that are not in CNF. Furthermore, every SLP can easily be transformed into an SLP that is in CNF, produces the same word and has roughly the same size. A grammar-based compressor \(\mathcal{C}\) is an algorithm that given an input \(w\in\Sigma^{+}\) outputs an SLP \(\mathbb{A}\) that produces \(w\). The size of an SLP is defined as \(|\mathbb{A}|=\sum_{(X\to v)\in P}|v|\). For a word \(w\in\Sigma^{+}\) we write \(g(w)\) for the size of a smallest SLP that produces \(w\). The _worst-case approximation ratio_\(\alpha_{\mathcal{C}}(k,n)\) of \(\mathcal{C}\) is the maximal approximation ratio over all words of length \(n\) over an alphabet of size \(k\):  
\[\alpha_{\mathcal{C}}(k,n)=\max\biggl{\{}\frac{|\mathcal{C}(w)|}{g(w)}\mid w\in [1,k]^{n}\biggr{\}}.\]  
For a given SLP \(\mathbb{A}\), a word \(\gamma\) is called a _maximal string_ of \(\mathbb{A}\) if  
* \(|\gamma|\geq 2\),
* \(\gamma\) appears at least twice without overlap as a factor of the right-hand sides,
* and no strictly longer word appears at least as many times as a factor of the right-hand sides without overlap. **Example 1**. : _Let \(\mathbb{A}=(\{S,X,Y,Z\},\{a,b\},P,S)\) such that \(P\) contains_  
* \(S\to aXXXXbbYZYZ\)_,_
* \(X\to Yb\bar{Y}ZYZa\)_,_
* \(Y\to bbDZZaZ\)_, and_
* \(Z\to abb\)_._  
_The maximal strings of_ \(\mathbb{A}\) _are_ \(bb\)_,_ \(YZ\) _and_ \(bbYZYZ\)_. The factors_ \(bb\) _and_ \(YZ\) _occur four times on the right-hand sides without overlap and_ \(bbYZYZ\) _occurs twice without overlap._  
A _global grammar-based compressor_ (or simply _global algorithm_) starts on input \(w\) with the SLP \(\mathbb{A}_{0}=(\{S\},\Sigma,\{S\to w\},S)\).