壓縮實例

Question

從我的算法教材：

年縣賽馬帶來三個純種從來沒有誰對彼此競爭。興奮的是，你研究了他們過去的200場比賽，並將這些比賽概括爲四個結果的概率分佈：第一個（「第一名」），第二名，第三名和其他。

     Outcome  Aurora Whirlwind Phantasm 
         first  0.15  0.30   0.20 

         second  0.10  0.05   0.30 

         third  0.70  0.25   0.30 

         other  0.05  0.40   0.20 

哪匹馬是最可預測的？對這個問題的一種量化方法是考慮可壓縮性。將每匹馬的歷史記錄爲一串200個值（第一，第二，第三，其他）。然後可以使用霍夫曼算法計算編碼這些記錄字符串所需的位總數。這對於Aurora來說是290比特，對於旋風來說是380比特，對於Phantasm來說則是420（檢查它！）。 Aurora具有最短的編碼，因此在最強烈的意義上是最可預測的。

他們是如何得到Phantasm 420的？我一直得到400字節，因爲如此：

先結合，其他= 0.4，結合第二，第三= 0.6。最終以2位編碼每個位置。

有沒有我誤解霍夫曼編碼算法的東西？

教科書可在這裏：http://www.cs.berkeley.edu/~vazirani/algorithms.html（第156頁）。

Answer 1

我認爲你是對的：Phantasm的200個結果可以用400位（不是字節）表示。奧羅拉的290和旋風的380是正確的。

正確霍夫曼碼以如下方式產生：

1. 合併兩個最低可能的結果：0.2和0.2。得到0.4。
2. 合併下兩個最不可能的結果：0.3和0.3。獲得0.6。
3. 合併0.4和0.6。獲取1.0。

，如果你這樣做，而不是你會得到420位：

1. 合併兩個最可能的結果：0.2和0.2。得到0.4。
2. 合併0.4和0.3。 （錯！）得到0.7。
3. 合併0.7和0.3。獲取1.0