A Space-saving Approximation Algorithm For Grammar-based Compression

摘要

A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log~*n) time to achieve O((log~*n) log n) approximation ratio to the optimum compression, where log~*n is the maximum number of logarithms satisfying log log … log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g = Ω(logn) and g = O(n/log_kn) for strings from k-letter alphabet [12].