A Space-Saving Approximation Algorithm for Grammar-Based Compression

Hiroshi SAKAMOTO  Shirou MARUYAMA  Takuya KIDA  Shinichi SHIMOZONO 

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

Full Text: PDF(665.9KB)

Summary: 
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].