A fully linear-time approximation algorithm for grammar-based compression

A linear-time approximation algorithm for the grammar-based compression is presented. This is an optimization problem to minimize the size of a context-free grammar deriving a given string. For each string of length n, the algorithm guarantees O(logng∗) approximation ratio without suffix tree construction.