Compression and ranking
Compression and ranking
复制标题
DOI：
10.1145/22145.22194
复制
发表时间：
1985-12
期刊：
影响因子：
--
通讯作者：
A. Goldberg;M. Sipser
中科院分区：
文献类型：
--
作者：
A. Goldberg;M. Sipser
经典数据压缩问题的复杂性理论方法是定义机器在一定复杂性类中的语言压缩的概念，并在此定义下研究可压缩的语言类。可以有效地(例如，通过概率多项式时间机器)压缩的语言特别令人感兴趣。我们定义了语言可压缩性的概念，并证明了足够稀疏的“容易”语言(如多项式时间)可以被有效地压缩。我们还定义了排序的概念(这是一种最优压缩)，并证明了一些“非常容易”的语言(例如，明确的上下文无关语言)可以有效地排序。我们展示的语言不能被有效地压缩或排名。可压缩性的概念与柯尔莫戈洛夫的复杂性和随机性密切相关。我们讨论了这种关系和我们结果的复杂性理论含义。
A complexity-theoretic approach to the classical data compression problem is to define a notion of language compression by a machine in a certain complexity class, and to study language classes compressible under the above definition. Languages that can be compressed efficiently (e.g. by a probabilistic polynomial time machine) are of special interest. We define the notion of language compressibility, and show that sufficiently sparse “easy” languages (e.g. polynomial time) can be compressed efficiently. We also define a notion of ranking (which is an optimal compression) and show that some “very easy” languages (e.g. unambiguous context-free languages) can be ranked efficiently. We exhibit languages which cannot be compressed or ranked efficiently. The notion of compressibility is closely related to Kolmogorov complexity and randomness. We discuss this relationship and the complexity-theoretic implications of our results.