The smallest grammar problem
The smallest grammar problem
复制标题
DOI：
10.1109/tit.2005.850116
复制
发表时间：
2005-07-01
影响因子：
2.5
通讯作者：
Shelat, A
中科院分区：
文献类型：
--
作者：
Charikar, M;Lehman, E;Shelat, A
本文讨论了最小的语法问题：什么是最小的上下文无关的语法，正好产生一个给定的字符串西格玛？这是一个自然的问题，一个基本的对象连接到许多领域，如数据压缩，Kolmogorov复杂性，模式识别，并添加chains.Due问题的固有复杂性，我们的目标是找到一个近似算法，找到一个小的语法。输入字符串。我们把注意力集中在算法的近似比（和隐含的，最坏情况下的行为），以建立可证明的性能保证。我们的第一个结果是关于近似最小文法问题的困难性。最值得注意的是，我们表明，每一个有效的算法最小的语法问题的近似比至少8569/8568，除非P = NP。然后，我们为几个最著名的基于语法的压缩算法，包括LZ 78，BISECTION，SEQUENTAL，LONGEST MATCH，GREEDY和RE-PAIR，绑定近似比。其中，最好的上界是O（n（1/2））。最后，我们提出了两个新的算法，具有指数级更好的O（log（3）n）和O（log（n/m*））的比率，其中m* 是该输入的最小语法的大小。后一种算法突出了基于语法的压缩和LZ 77之间的联系。
This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string sigma?This is 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 complexity, 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(n(1/2)). We finish by presenting two novel algorithms with exponentially better ratios of O(log(3) 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.