10

让我澄清一下，我不是在谈论能够压缩任何给定源材料的算法意义上的完美压缩，我意识到这是不可能的。我想要得到的是一种算法，它能够将任何源比特串编码为其绝对最大压缩状态，由它的香农熵确定。

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

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

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

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

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

使用单个位作为符号的霍夫曼编码是否会像优化的那样压缩位串，即使我们在 2 位符号级别分析字符串时会出现明显的模式？如果没有，是否可以通过循环遍历霍夫曼编码的不同“级别”（对不起，如果我在这里扼杀术语）来最佳地压缩源，直到找到最佳压缩率？在某些情况下，通过不同的“轮次”霍夫曼编码可以进一步提高压缩率吗？（首先对 5 位长的符号进行霍夫曼编码，然后对 4 位长的符号进行霍夫曼编码？huff_4bits(huff_5bits(bitstring))）

4

2 回答 2

10

正如 Mark 所说，由于 Kolmogorov 的复杂性，一般的答案是“不”。让我对此进行一些扩展。

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

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

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

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

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

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

于 2014-02-05T09:37:13.433 回答
6

不。可以证明，甚至没有一种算法可以确定完美压缩机的性能。请参阅Kolmogorov 复杂性。

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

于 2014-01-20T03:38:16.547 回答