Search

A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of a smallest grammar for this word. The worst-case approximation ratio of a grammar-based compressor for a given word length is the largest approximation ratio over all input words of that length. In this work, we study the worst-case approximation ratio of the algorithms Greedy, RePair and LongestMatch on unary strings, i.e., strings that only make use of a single symbol. Our main contribution is to show the improved upper bound of O ((log n) 8 · (log log n) 3) for the worst-case approximation ratio of Greedy. In addition, we also show the lower bound of 1.34847194 ⋯ for the worst-case approximation ratio of Greedy, and that RePair and LongestMatch have a worst-case approximation ratio of log 2 (3) . [ABSTRACT FROM AUTHOR]