哈夫曼編碼原理

參考：

• 百度百科
• 哈夫曼（huffman）樹和哈夫曼編碼
• 關于哈夫曼樹編碼

1. 簡介

定義

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是Huffman于1952年提出的一種編碼方式，是一種可變字長編碼(VLC)。該方法完全依據字元出現機率進行構造的平均長度最短的編碼，是以也稱之為最佳編碼。

應用

得益于哈夫曼編碼可以得到一個平均長度最短的碼文，是以應用場景很多，在此列舉三個：

• apache負載均衡的按權重請求政策的底層算法
• 路由器的路由算法
• zip檔案的其中一種壓縮算法

2. 編碼原理

哈夫曼編碼大緻分為三步：

① 統計字元出現頻率；

② 根據頻率構造一顆哈夫曼樹，這也是一顆最優二叉樹。

③ 對哈夫曼樹進行01編碼，得到最後的碼文。

最優二叉樹的定義：給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹。

假設一條文本内容(100 bytes)如下：

AAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCDDDEEEEEEEEEEEFFFFFFFFFFFFFFGGGGGGGHHHHHHHH
           

步驟一：統計字元出現頻率

字元	頻數（便于觀察，頻數當作頻率）
A	5
B	29
C	23
D	3
E	11
F	14
G	7
H	8

步驟二：構造哈夫曼樹

赫夫曼編碼的具體方法：先按出現的機率大小排隊，把兩個最小的機率相加，作為新的機率 和剩餘的機率重新排隊，再把最小的兩個機率相加，再重新排隊，直到最後變成1。

構造過程如下圖：

步驟三：進行01編碼

根據最終得到的哈夫曼樹，向左為0，向右為1，可得到每個字元的編碼如下表：

字元	頻數（便于觀察，頻數當作頻率）	編碼
A	5	00001
B	29	01
C	23	11
D	3	00000
E	11	101
F	14	001
G	7	0001
H	8	100

最終得到碼文為：

0000100001000010000100001010101010101010101010101010101010101010101010101010101010111111111111111111111111111111111111111111111110000000000000001011011011011011011011011011011010010010010010010010010010010010010010010010001000100010001000100010001100100100100100100100100
           

最後，我們比較一下編碼前後的長度：

編碼前：100 bytes
編碼後：25+58+46+15+33+42+28+24=271/8 = 33.875 bytes
           

實際上，對于同一組頻數(也稱頻率或權值)，存在不同構的哈夫曼樹，例如任意非葉結點的左右子樹交換後仍是該組頻數的哈夫曼樹，但最終編碼長度是相同的。同時，哈夫曼編碼也是一種非字首碼，要求任一字元的編碼都不能是另一字元編碼的字首。

未完待續：哈夫曼編碼算法實作