有沒有數學證明霍夫曼編碼是最有效的無損壓縮算法？

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最佳樹。