Sakamoto, Hiroshi
A Space-Saving Approximation Algorithm for Grammar-Based Compression
Abstract
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 · · · 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 k-letter alphabet [12].
BibTeX - Entry
@InProceedings{sakamoto:DSP:2008:1693,
author = {Hiroshi Sakamoto},
title = {A Space-Saving Approximation Algorithm for Grammar-Based Compression},
booktitle = {Structure-Based 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 = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1693},
annote = {Keywords: Grammar based compression, space efficient approximation}
}
|
Keywords: |
|
Grammar based compression, space efficient approximation |
|
Seminar: |
|
08261 - Structure-Based Compression of Complex Massive Data
|
|
Issue date: |
|
2008 |
|
Date of publication: |
|
20.11.2008 |
20.11.2008
