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(log2
n) approximation ratio without suffix tree and runs in O(n) time in the sense of randomized model.