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

Question

我的朋友告诉我它存在,但我找不到它,不确定他是否在撒谎,但我对证明如何运作非常感兴趣.(是的,我是那些从硅谷电视节目中发现霍夫曼编码的人之一,抱歉)

Answer 1

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

这是一个高级视图。无损压缩算法提供了可能要压缩的文档到压缩文档的可逆映射。文档可以被视为位串。有 2^n 个可能的 n 位文档。有 2^n 种可能的 n 位压缩文档。因此，洋泾浜漏洞原理表明，对于每个存储效率较高的文档，其他一些可能的文档必须存储效率较低。

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

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

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

现在假设您获取了可以用相机生成的一组文档。这看起来一点也不像文本，不同的编码方法会效果更好。

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

Answer 2

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