COMPRESSION AND RANKING

被引：27

作者：

GOLDBERG, AV

SIPSER, M

机构：

[1] UNIV CALIF BERKELEY, DIV COMP SCI, BERKELEY, CA 94720 USA

[2] MIT, DEPT MATH, CAMBRIDGE, MA 02139 USA

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 03期

关键词：

DATA COMPRESSION; KOLMOGOROV COMPLEXITY; COMPUTATIONAL COMPLEXITY;

D O I：

10.1137/0220034

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A complexity-theoretic approach to the classical data compression problem is presented. A notion of language compressibility is defined, and it is shown that essentially all strings in a sufficiently sparse "easy" (e.g., polynomial-time) language can be compressed efficiently. A notion of ranking as a form of optimal compression is also defined, and it is shown that some "very easy" languages (e.g., unambiguous context-free languages) can be ranked efficiently. Languages that cannot be compressed or ranked efficiently under various complexity-theoretic assumptions are exhibited. The notion of compressibility is closely related to Kolmogorov complexity and randomness. This relationship and the complexity-theoretic implications of our results are discussed.

引用

页码：524 / 536

页数：13

共 13 条

[1] ALLENDER EW, 1985, THESIS COMP SCI DEP
[2] BERTONI A, 1987, LECT NOTES COMPUT SC, V247, P169
[3] Blum M., 1982, 23rd Annual Symposium on Foundations of Computer Science, P112, DOI 10.1109/SFCS.1982.72
[4] Blum Manuel, COMMUNICATION
[5] ELIAS P, UNPUB
[6] Feller W., 1971, INTRO PROBABILITY TH
[7] Kolmogorov A.N., 1965, PROBLEMY PEREDACHI I, V1, P3
[8] ARITHMETIC CODING
RISSANEN, J
LANGDON, GG
[J]. IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1979, 23 (02) : 149 - 162
[9] GENERALIZED KRAFT INEQUALITY AND ARITHMETIC CODING
RISSANEN, JJ
[J]. IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1976, 20 (03) : 198 - 203
[10] Sipser M., 1983, P 15 ANN ACM S THEOR, P330

← 1 2 →