A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression
Hiroshi Sakamoto · Institutional Repositories DataBase (IRDB) · 2003
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. Given a string of length n, the algorithm guarantees O(log n) approximation ratio and using the data structures of doubly-linked list, hash table, and priority queue, it runs in O(n) time even if the size of alphabet is unbounded.