有“完美”压缩的算法吗？

Question

让我澄清一下，我不是在说完美压缩，也不是说一种能够压缩任何给定源材料的算法，我意识到这是不可能的。我试图得到的是一种算法，它能够将任何源比特串编码到它的绝对最大压缩状态，这取决于它的香农熵。

我相信我听说过一些关于霍夫曼编码在某种意义上是最优的事情，所以我相信这个加密方案可能是基于此的，但这是我的问题：

考虑位串：a="101010101010"，b="110100011010"。

使用纯香农熵，当我们将位串视为0和1的简单符号时，这些位串应该具有完全相同的熵，但这种方法是有缺陷的，因为我们可以直观地看到，位串a的熵比位串b的熵小，因为它只是重复10的模式。考虑到这一点，通过计算复合符号00、10、01和11的香农熵，我们可以更好地了解源的实际熵。

这只是我的理解，我可能完全错了，但是根据我的理解，对于一个遍历源是真正随机的，对于一个长度为n的遍历源。所有n长度符号组的统计概率必须是相等的。

我想比标题中的问题更具体一些，我有三个主要问题：

使用单个位作为符号的哈夫曼编码是否会将位字符串压缩为最佳状态，即使我们在2位符号级别分析字符串时会出现明显的模式？如果没有，可以通过在哈夫曼编码的不同“级别”（抱歉，如果我在这里破坏术语）之间循环来优化压缩源，直到找到最佳压缩率吗？在某些情况下，经历不同的哈夫曼编码“循环”会进一步提高压缩率吗？（例如，首先对5位长的符号进行哈夫曼编码，然后对4位长的符号进行哈夫曼编码？huff\u 4bits（huff\u 5bits（bitstring）））




Answer 1

没有。可以证明，甚至没有一种算法来确定一个完美的压缩机的性能。见科尔莫戈罗夫复杂性。

哈夫曼编码（或算术编码）本身并不能达到最佳压缩。需要使用其他技术来利用数据中的高阶冗余。

Answer 2

正如马克所说，由于Kolmogorov的复杂性，一般的答案是“不”。让我稍微扩展一下。

压缩基本上分为两个步骤：1）模型2）熵

该模型的作用是“猜测”接下来的字节或字段。模型可以有任何形式，其有效性没有限制。一个简单的例子是随机数生成器函数：从外部角度来看，它看起来像噪声，因此无法压缩。但是如果你知道生成函数，一个无限长的序列可以压缩成一个小的代码集，生成函数。

这就是为什么“没有限制”，Kolmogorov complexity只是说：你永远不能保证没有更好的方法来“建模”数据。

第二部分是可计算的：熵是找到“香农极限”的地方。给定一组符号（通常是模型的输出符号），它们是字母表的一部分，您可以计算最优成本，并找到一种方法来达到经验证的最终压缩极限，即香农极限。

如果您接受每个符号必须使用整数位数进行编码的限制，那么哈夫曼对于香农极限是最优的。这是接近但不完美的近似。更好的压缩可以通过使用分数位来实现，分数位是算术编码器所提供的，或者是最近基于ANS的有限状态熵编码器。两者都更接近香农极限。

香农极限仅适用于“单独”处理一组符号的情况。一旦你试图“组合它们”，或找到符号之间的任何相关性，你就是在“建模”。这是Kolmogorov复杂性的领域，这是不可计算的。