A linear-time approximation algorithm for the grammar-based compression, which is an optimization problem to minimize the size of a context-free grammar deriving a given string, is presented. For each string of length n over unbounded alphabet, the algorithm guarantees O(log~2 n) approximation ratio without suffix tree and runs in O(n) time in the sense of randomized model.
展开▼
