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

Question

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

Answer 1

答案是，它不是，问题是不适当的。 :-)

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

那么如何压缩？这是可能的，因为虽然所有文件都是可能，但它们的可能性并不相同。所以一个好的压缩算法将非常有效地存储可能的文档，而不太可能的文档效率不高。但问题是文件是否有效。答案是，“这取决于”。而压缩算法的好坏的答案也将取决于。

假设您从一组独立出现的不同概率出发的随机文件集合。霍夫曼编码产生最有效的可能的压缩算法。

现在假设你采用了可能用英文书写的一组随机句子？霍夫曼编码仅限于查看原始字母频率。它不会使用某些字母组合很频繁出现的事实。其他可以使用的编码现在可以更好地工作。

现在假设您拍摄可能由您的相机产生的一组文档。这看起来不像文本，不同的编码方法会更好。

所以有些情况下霍夫曼是最好的。不是的情况。这个问题是不适当的，因为它取决于“什么文件可能？”

Answer 2

这不是最有效的无损压缩方法。算术编码首先击败它。由于它不是最高效的，所以没有证据证明它是。但是，我认为这是optimal代码，但每个符号使用的位数是整数，或许这就是您的朋友所谈论的证明。

Answer 3

Proof of Optimality of Huffman Codes, CSC373 Spring 2009。

它证明中间定理和在到达时：

定理3算法HUF(A,f)计算用于频率f 和字母A最佳树。