霍夫曼（Huffman）編碼原理

霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統計編碼。屬于無損壓縮編碼。

霍夫曼編碼的碼長是變化的，對于出現頻率高的信息，編碼的長度較短；而對于出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。

步驟進行：

l）將信號源的符號按照出現概率遞減的順序排列。

2）將兩個最小出現概率進行合并相加，得到的結果作為新符號的出現概率。

3）重復進行步驟1和2直到概率相加的結果等于1為止。

4）在合并運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。

5）記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。

例：

設信號源為 s＝｛s1, s2, s3, s4, s5｝

對應的概率為p＝｛0.25，0.22，0.20, 0.18，0.15｝。

根據字符出現的概率來構造平均長度最短的異字頭碼字。

霍未曼編碼通常采用兩次掃描的辦法，第一次掃描得到統計結果，第二次掃描進行編碼。

霍夫曼編碼具有一些明顯的特點：

1) 編出來的碼都是異字頭碼，保證了碼的唯一可譯性。

2) 由于編碼長度可變。因此譯碼時間較長，使得霍夫曼編碼的壓縮與還原相當費時。

3) 編碼長度不統一，硬件實現有難度。

4) 對不同信號源的編碼效率不同，當信號源的符號概率為2的負冪次方時，達到100％的編碼效率；若信號源符號的概率相等，則編碼效率最低。

5) 由于"0"與"1"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。