The smallest grammar problem

Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, Abhi Shelat

Research output: Contribution to journalArticlepeer-review


This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string σ? This i s a natural question about a fundamental object connected to many fields such as data compression, Kolmogorov complexity, pattern identification, and addition chains. Due to the problem's inherent comp lexity, our objective is to find an approximation algorithm which finds a small grammar for the input string. We focus attention on the approximation ratio of the algorithm (and implicitly, the worst case behavior) to establish provable performance guarantees and to address shortcomings in the classical measure of redundancy in the literature. Our first results are concern the hardness of approximating the smallest grammar problem. Most notably, we show that every efficient algorithm for the smallest grammar problem has approximation ratio at least 8569/8568 unless P = NP. We then bound approximation ratios for several of the best known grammar-based compression algorithms, including LZ78, BISECTION, SEQUENTIAL, LONGEST MATCH, GREEDY, and RE-PAIR. Among these, the best upper bound we show is O(n1/2). We finish by presenting two novel algorithms with exponentially better ratios of O(log3 n) and O(log(n/m*)), where m* is the size of the smallest grammar for that input. The latter algorithm highlights a connection between grammar-based compression and LZ77.

Original languageEnglish (US)
Pages (from-to)2554-2576
Number of pages23
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2005
Externally publishedYes


  • Approximation algorithm
  • Data compression
  • Hardness of approximation
  • LZ77
  • LZ78
  • Longest Match
  • Multilevel pattern matching (Mpm)
  • Re-Pair
  • Sequitur
  • Smallest grammar problem

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'The smallest grammar problem'. Together they form a unique fingerprint.

Cite this