有数学证据证明哈夫曼编码是最有效的无损压缩算法吗？

Question

我的朋友告诉我，它是存在的，但我永远找不到它，不知道他是否在撒谎，但我非常感兴趣的是，如何证明。(是的，我是那些从硅谷电视节目中发现赫夫曼编码的人之一，对不起)

Answer 1

答案是，它不是，而且问题是不恰当的。:-)

这里是一个高层次的视图。无损压缩算法提供了可能被压缩的文档到压缩文档的可逆映射。文档可以被看作是位串。有2^n个可能有n位的文档。有2^n个可能具有n位的压缩文档。因此，pidgin-孔原理指出，对于每一个存储效率更高的文档，其他一些可能的文档的存储效率必须较低。

那么压缩是如何可能的呢？这是可能的，因为虽然所有的文档都是可能的，但它们的可能性并不相等。因此，一个好的压缩算法将非常有效地存储可能的文档，而不太可能的文档存储效率很低。但问题是什么文件是有效的。答案是，“视情况而定。”压缩算法有多好，答案也将取决于。

假设您使用由一组符号组成的随机文档集，这些符号以不同的概率独立出现。Huffman编码产生了最有效的压缩算法。

现在假设你采用了一组随机的句子，这些句子很可能是用英语写的？赫夫曼编码仅限于查看原始字母频率。它没有利用这样一个事实，即某些字母组合经常出现。其他可以使用它的编码现在可以更好地工作了。

现在假设你拿了一组可以由你的相机产生的文件。这看起来一点也不像文本，不同的编码方法会更好地工作。

因此，在某些情况下，赫夫曼是最好的。如果情况并非如此，那么这个问题就不合适了，因为它取决于“可能有哪些文件？”

Answer 2

它不是最有效的无损压缩方法。算术编码在一开始就胜过它。由于它不是最有效的，因此没有证据证明它是有效的。我相信当使用每个符号的整数位数时，这是最优代码，也许这就是你的朋友所说的证据。

Answer 3

霍夫曼码最优性的证明，CSC373,2009年春季。

证明了中间定理，得出：

定理3算法HUF(A,f)计算频率、f和字母表A__的最佳树。