这是一个理论问题，所以预计这里的许多细节在实践中甚至在理论上都无法计算。
假设我有一个字符串 s我想压缩。结果应该是一个自解压二进制文件(可以是 x86 汇编程序，但也可以是其他一些假设的图灵完备低级语言)，它输出 s .
现在，我们可以轻松地遍历所有可能的此类二进制文件和程序，按大小排序。让 B_s成为输出 s 的这些二进制文件的子列表(当然 B_s 是不可计算的)。
由于每组正整数都必须有最小值，因此必须有一个最小的程序b_min_s在 B_s .
对于什么语言(即字符串集)，我们知道b_min_s 的大小。 ?也许只是一个估计。 (我可以构建一些简单的例子，我什至可以计算 B_s 和 b_min_s ，但我对更有趣的语言感兴趣。)
最佳答案
Claude Shannon在他 1951 年的论文 Prediction and Entropy of Printed English 中估计英语的信息密度在每个字符 0.6 到 1.3 位之间。 (PDF，1.6 MB。Bell Sys. Tech. J (3) p. 50-64)。
关于compression - 理论上可能的最大压缩率是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3261685/