DagSemProc.08261.4.pdf
- Filesize: 359 kB
- 14 pages
Document
A Space-Saving Approximation Algorithm for Grammar-Based Compression
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 8261
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2008-11-20
Cite As Get BibTex
Hiroshi Sakamoto. A Space-Saving Approximation Algorithm for Grammar-Based Compression. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/DagSemProc.08261.4
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].
Subject Classification
Keywords
- Grammar based compression
- space efficient approximation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads