compression - 是否有用于 "perfect"压缩的算法？

Question

让我澄清一下，我并不是在说一种能够压缩任何给定源 Material 的算法，这是完全不可能的，我意识到这是不可能的。我想要得到的是一种算法，该算法能够将任何位的源字符串编码为由Shannon熵确定的绝对最大压缩状态。

我相信我已经听说过有关霍夫曼编码在某种意义上说是最佳的事情，所以我相信这种加密方案可能基于此，但这是我的问题:

考虑一下位串:a =“101010101010”，b =“110100011010”。

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

这只是我的理解，我可能完全不了解，但是根据我的理解，遍历源确实是随机的，长度为n的遍历源。所有n个长度的符号组的统计概率必须同等可能。

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

使用单一位作为符号的霍夫曼编码是否可以像最佳方式一样压缩位串，即使在我们以2位符号级别分析字符串时也会出现明显的模式？如果不是这样，是否可以通过在霍夫曼编码的不同“级别”(如果我在这里称呼术语为“不同”)循环，直到找到最佳压缩率，来最佳地压缩源？在某些情况下，能否通过霍夫曼编码的不同“回合”进一步提高压缩率？ (例如，首先使用5位长的符号进行霍夫曼编码，然后对4位长的符号进行霍夫曼编码？huff_4bits(huff_5bits(bitstring)))

Answer 1

正如Mark所言，由于Kolmogorov的复杂性，通常的答案是“ no ”。让我扩大一点。

压缩基本上是两个步骤:
1)型号
2)熵

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

这就是为什么“没有限制”的原因，而Kolmogorov的复杂性只是指出:您永远不能保证没有更好的方法来“建模”数据。

第二部分是可计算的:熵是找到“香农极限”的地方。
给定一组符号(通常是模型的输出符号)(它们是字母的一部分)，您可以计算最佳成本，并找到达到公认的最终压缩极限(香农极限)的方法。

如果您接受的限制，即每个符号必须使用整数位数进行编码，则霍夫曼在香农限制方面是最佳的。这是接近的，但是不完美的近似。可以使用算术编码器提供的小数位或较新的基于ANS的Finite State Entropy coder来实现更好的压缩。两者都更接近香农极限。

仅当您“单独”对待一组符号时，香农限制才适用。一旦您尝试“组合它们”或找到符号之间的任何相关性，即表示您正在“建模”。这是不可计算的Kolmogorov复杂性领域。