Sakamoto, Hiroshi
A SpaceSaving Approximation Algorithm for GrammarBased Compression
Abstract
A spaceefficient approximation algorithm for the grammarbased compression
problem, which requests for a given string to find a smallest
contextfree 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 · · · logn > 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
g=O(n/log_k n) for strings from a kletter alphabet [12].
BibTeX  Entry
@InProceedings{sakamoto:DSP:2008:1693,
author = {Hiroshi Sakamoto},
title = {A SpaceSaving Approximation Algorithm for GrammarBased Compression},
booktitle = {StructureBased Compression of Complex Massive Data },
year = {2008},
editor = {Stefan B{\"o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
number = {08261},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1693},
annote = {Keywords: Grammar based compression, space efficient approximation}
}
2008
Keywords: 

Grammar based compression, space efficient approximation 
Seminar: 

08261  StructureBased Compression of Complex Massive Data

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 