A Space-Saving Approximation Algorithm for Grammar-Based Compression

Hiroshi SAKAMOTO  Shirou MARUYAMA  Takuya KIDA  Shinichi SHIMOZONO  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.158-165
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.158
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
grammar-based compression,  approximation algorithm,  minimum CFG problem,  

Full Text: PDF(667.1KB)
>>Buy this Article

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=Ω(log n) and for strings from k-letter alphabet [12].