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

Question

根据香农的源编码定理，我们知道压缩字符串的熵受原始字符串熵的限制，如下所示：

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

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

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

我想知道的是：

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

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

Answer 1

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

如果你从给定的概率分布中随机选择一个字符串，那么我们可以得到的字符串的最佳平均压缩比由概率分布的熵率给出。

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

1. 如果输入字符串等于某个预先选择的随机字符串，则输出为 1 位字符串“0”
2. 否则，输出为“1”的N+1位字符串，后跟输入字符串

对应的解压算法为：

1. 如果输入为“0”，则输出为我们之前预选的随机字符串
2. 否则，输出是除了第一个输入位之外的所有内容

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

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

Answer 2

是的。英语的熵率通常被引用为每个字符 1.5 位（给予或接受）。典型的编码每个字符使用 8 位。因此，最大压缩文本应该是原始大小的 1.5/8 (~19%)。简奥斯汀的《傲慢与偏见》纯文本版本的实际结果：orig = 701K，bzip2 = 178K，约占 25%。

Answer 3

在不知道源字符串长度的情况下，您无法直接将熵与压缩比联系起来，但您可以通过求解 L 的最小可能值来查看最大压缩比的理论限制。您可以将此限制用作衡量压缩算法的效率，尽管一个糟糕的指标并不意味着已经发现甚至存在更好的算法。

所以，是的。您可以使用熵来找到理论上的最大无损压缩比，但是不，您不能使用它来确定任何给定压缩算法的预期压缩比。

Answer 4

是的！我认为本文将为您指明正确的方向。

ETA看起来您需要成为 IEEE 成员才能阅读实际论文。如果有人可以找到公开可用的资源（或在这里解释数学），那当然会好得多！