是否有数学证明霍夫曼编码是最有效的无损压缩算法？
Is there mathematical proof that Huffman coding is the most efficient lossless compression algorithm?
我的朋友告诉我它存在，但我永远找不到它，不确定他是否在撒谎，但我对证明的工作原理非常感兴趣。 （是的，我是那些从硅谷电视节目中发现霍夫曼编码的人之一，抱歉）
这不是最有效的无损压缩方法。算术编码一开始就胜过它。由于它不是最有效的，因此没有证据证明它是最有效的。我相信这是 optimal 代码，但每个符号使用整数位时，也许这就是你朋友所说的证明。
Proof of Optimality of Huffman Codes, CSC373 Spring 2009.
它证明了中间定理并得出：
Theorem 3 The algorithm HUF(A,f) computes an optimal tree for frequencies f
and alphabet A.
答案是，不是，问题不成立。 :-)
这是高级视图。无损压缩算法提供了可能要压缩的文档到压缩文档的可逆映射。文档可以被视为位串。有 n 位的 2^n 个可能的文档。有 2^n 个可能的 n 位压缩文档。因此，pidgin-hole 原则说，对于每个存储效率更高的文档，其他一些可能的文档必须存储效率较低。
那么压缩是如何实现的呢？这是可能的，因为虽然所有文档都是 可能 ，但它们的可能性并不相同。因此，一个好的压缩算法将非常有效地存储可能的文档，并且低效地存储不太可能的文档。但接下来的问题是什么文件是有效的。答案是 "It depends." 而压缩算法的好坏也取决于答案。
假设你拿了一组随机文档，这些文档由一组以不同概率独立出现的符号组成。霍夫曼编码产生最有效的压缩算法。
现在假设你随机取一组很可能用英语写的句子？霍夫曼编码仅限于查看原始字母频率。它没有利用某些字母组合出现得非常频繁这一事实。可以使用的其他编码现在可以更好地工作。
现在假设您拍摄了您的相机可以拍摄的一组文件。这看起来一点也不像文本，不同的编码方法会更好。
所以有些情况下霍夫曼是最好的。不是的情况。这个问题是不适定的，因为它取决于 "What documents are likely?"
我的朋友告诉我它存在，但我永远找不到它，不确定他是否在撒谎，但我对证明的工作原理非常感兴趣。 （是的，我是那些从硅谷电视节目中发现霍夫曼编码的人之一，抱歉）
这不是最有效的无损压缩方法。算术编码一开始就胜过它。由于它不是最有效的，因此没有证据证明它是最有效的。我相信这是 optimal 代码，但每个符号使用整数位时，也许这就是你朋友所说的证明。
Proof of Optimality of Huffman Codes, CSC373 Spring 2009.
它证明了中间定理并得出：
Theorem 3 The algorithm
HUF(A,f)computes an optimal tree for frequenciesfand alphabetA.
答案是，不是，问题不成立。 :-)
这是高级视图。无损压缩算法提供了可能要压缩的文档到压缩文档的可逆映射。文档可以被视为位串。有 n 位的 2^n 个可能的文档。有 2^n 个可能的 n 位压缩文档。因此，pidgin-hole 原则说，对于每个存储效率更高的文档，其他一些可能的文档必须存储效率较低。
那么压缩是如何实现的呢？这是可能的，因为虽然所有文档都是 可能 ，但它们的可能性并不相同。因此，一个好的压缩算法将非常有效地存储可能的文档，并且低效地存储不太可能的文档。但接下来的问题是什么文件是有效的。答案是 "It depends." 而压缩算法的好坏也取决于答案。
假设你拿了一组随机文档，这些文档由一组以不同概率独立出现的符号组成。霍夫曼编码产生最有效的压缩算法。
现在假设你随机取一组很可能用英语写的句子？霍夫曼编码仅限于查看原始字母频率。它没有利用某些字母组合出现得非常频繁这一事实。可以使用的其他编码现在可以更好地工作。
现在假设您拍摄了您的相机可以拍摄的一组文件。这看起来一点也不像文本，不同的编码方法会更好。
所以有些情况下霍夫曼是最好的。不是的情况。这个问题是不适定的，因为它取决于 "What documents are likely?"