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

Question

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

Answer 1

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

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

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

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

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

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

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