Resumen
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 ??((log??)8·(loglog??)3)
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?
1.34847194
?
for the worst-case approximation ratio of Greedy, and that RePair and LongestMatch have a worst-case approximation ratio of log2(3)
log
2
(
3
)
.