On the Complexity of Optimal Grammar-Based Compression

Jan Arpe, Rüdiger Reischuk

Abstract

Given a string, the task of grammar-based compression is to find a small contextfree grammar that generates exactly that string. We investigate the relationship between grammar-based compression of strings over unbounded and bounded alphabets. Specifically, we show how to transform a grammar for a string over an unbounded alphabet into a grammar for a block coding of that string over a fixed bounded alphabet and vice versa. From these constructions, we obtain asymptotically tight relationships between the minimum grammar sizes for strings and their block codings. Furthermore, we exploit an improved bound of our construction for overlap-free block codings to show that a polynomial time algorithm for approximating the minimum grammar for binary strings within a factor of c yields a polynomial time algorithm for approximating the minimum grammar for strings over arbitrary alphabets within a factor of 24c + ∈ (for arbitrary ∈ > 0). Currently, the latter problem is known to be NP-hard to approximate within a factor of 8569/8568. Since there is some hope to prove a nonconstant lower bound, our results may provide a first step towards solving the long standing open question whether minimum grammar-based compression of binary strings is NP-complete.

OriginalspracheEnglisch
TitelData Compression Conference (DCC'06)
Seitenumfang10
Herausgeber (Verlag)IEEE
Erscheinungsdatum01.12.2006
Seiten173-182
Aufsatznummer1607252
ISBN (Print)0-7695-2545-8
DOIs
PublikationsstatusVeröffentlicht - 01.12.2006
VeranstaltungData Compression Conference 2006 - Snowbird, USA / Vereinigte Staaten
Dauer: 28.03.200630.03.2006
Konferenznummer: 77103

Fingerprint

Untersuchen Sie die Forschungsthemen von „On the Complexity of Optimal Grammar-Based Compression“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren