Lan*_*don 4 compression information-theory
从Shannon的源编码定理我们知道压缩字符串的熵受原始字符串的熵限制,如下所示:
H(X) <= L < H(X) + 1/N
其中H(X)是源字符串的熵,N是源字符串的长度,L是压缩字符串的预期长度.
这必然意味着无损压缩存在限制.
我想知道的是:
我们可以直接将熵与某些预期的压缩比相关联吗？
我们可以使用熵来找到压缩比的上限吗？
香农定理是根据随机数据和概率定义的.类似地,字符串的熵仅为随机字符串定义 - 熵是分布的属性,而不是字符串本身.因此,我们可以非正式地重申香农定理:
如果您从给定的概率分布中随机选择一个字符串,那么我们可以为字符串获得的最佳平均压缩率由概率分布的熵率给出.
给定任意随机字符串,我可以轻松编写压缩算法,将该字符串压缩为1位,但我的算法必然会增加其他字符串的长度.我的压缩算法的工作原理如下:
相应的解压缩算法是:
这里的关键是,我们不能写出一个算法,从给定的分配所有字符串,压缩它们都在平均率很高.有太多的字符串.
如果我们有一个给定的字符串概率分布,我们可以计算分布的熵率,然后如果根据分布随机选择一个字符串并尝试使用任何算法压缩它,压缩字符串的相对大小将在,平均值,绝不低于熵率.这就是香农定理所说的.
在不知道源字符串长度的情况下，您无法直接将熵与压缩比相关联，但是您可以通过求解 L 的最小可能值来了解最大压缩比的理论限制。您可以使用此限制作为度量压缩算法的效率，尽管不好的指标并不意味着已经发现甚至存在更好的算法。
所以，是的。您可以使用熵来查找理论上的最大无损压缩比，但是不行，您不能使用它来确定任何给定压缩算法的预期压缩比。