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

Question

我的朋友告诉我它存在但我永远找不到它，不确定他是否在撒谎，但我对证明的工作原理非常感兴趣。（是的，我是从硅谷电视节目中发现霍夫曼编码的人之一，抱歉）

Answer 1

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

Answer 2

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

它证明了中间定理并得出：

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

Answer 3

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

这是一个高级视图。无损压缩算法提供了将要压缩的可能文档到压缩文档的可逆映射。文档可以被视为比特串。有 2^n 个可能具有 n 位的文档。有 2^n 个可能的 n 位压缩文档。因此，pidgin-hole 原则表明，对于每个存储效率更高的文档，其他一些可能的文档必须存储效率较低。

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

假设您从一组以不同概率独立出现的符号组成随机文档集。霍夫曼编码产生最有效的压缩算法。

现在假设你拿一组可能用英语写的随机句子？霍夫曼编码仅限于查看原始字母频率。它没有利用某些字母组合非常频繁出现的事实。可以使用的其他编码现在将更好地工作。

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

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