Document Open Access Logo

A Space-Saving Approximation Algorithm for Grammar-Based Compression

Author Hiroshi Sakamoto

PDF

File

Thumbnail PDF
PDF
DagSemProc.08261.4.pdf
  • Filesize: 359 kB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Grammar based compression
  • space efficient approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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

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

Author Details

Hiroshi Sakamoto
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact