compression - 熵与无损压缩率的关系

Question

来自 Shannon's Source Coding Theorem我们知道压缩字符串的熵受原始字符串熵的限制，如下所示:

H(X) <= L < H(X) + 1/N 

其中 H(X) 是源字符串的熵，N 是源字符串的长度，L 是压缩字符串的预期长度。

这必然意味着无损压缩是有限度的。

我想知道的是:

我们可以直接将熵与某些预期的压缩比联系起来吗？

我们可以使用熵来找到压缩比的一些上限吗？

Answer 1

香农定理是根据随机数据和概率定义的。类似地，字符串的熵仅针对随机字符串定义——熵是分布的属性，而不是字符串本身的属性。因此，我们可以非正式地将香农定理重述为:

If you randomly select a string from a given probability distribution, then the best average compression ratio we can get for the string is given by the entropy rate of the probability distribution.

给定任何随机字符串，我可以轻松编写一个压缩算法，将该字符串压缩为 1 位，但我的算法必然会增加其他一些字符串的长度。我的压缩算法的工作原理如下:

如果输入字符串等于某个预先选择的随机字符串，则输出为 1 位字符串“0”

否则，输出为“1”的 N+1 位字符串后跟输入字符串

对应的解压算法为:

如果输入为“0”，则输出为我们之前预选的随机字符串

否则，输出是除了第一个输入位

之外的所有内容。

这里的关键是我们不能写出一种算法，对于来自给定分布的所有字符串，平均以高速率压缩它们。字符串太多了。

如果我们有一个给定的字符串概率分布，我们可以计算该分布的熵率，然后根据分布随机选择一个字符串并尝试使用 对其进行压缩。任何 算法，压缩字符串的相对大小平均永远不会小于熵率。这就是香农定理所说的。