961全部内容連結
文章目錄
- 哈夫曼（Huffman）樹的定義
- 哈夫曼樹的構造
- 哈夫曼樹的代碼實作
- 哈夫曼樹的應用
-
- 哈夫曼編碼
哈夫曼（Huffman）樹的定義
對于樹的每個"葉節點"，都賦予一個權值w。如圖
用它的權值乘以它的深度減1（從根節點到該節點所經過的邊數），稱為該節點的帶權路徑長度。 整個樹的每個葉節點的帶權路徑長度之和，稱為樹的帶權路徑長度，公式如下：
W P L = ∑ i = 1 n w i l i ( w i 為 第 i 個 節 點 的 權 值 , l i 為 其 路 徑 長 度 ) WPL = \sum_{i=1}^n w_i l_i ~~~~(w_i為第i個節點的權值,l_i為其路徑長度) WPL=i=1∑nwili (wi為第i個節點的權值,li為其路徑長度)
WPL（Weighted Path Length of Tree）。對于同一批節點，帶全路徑長度最小的樹稱為哈夫曼樹，也叫最優二叉樹。
該圖中，樹的帶權路徑長度分别為：
圖 1 ： W P L = 1 × 2 + 3 × 2 + 4 × 2 + 5 × 2 = 26 圖 2 ： W P L = 1 × 3 + 3 × 3 + 4 × 2 + 5 × 1 = 25 圖 3 ： W P L = 5 × 1 + 3 × 3 + 1 × 3 + 4 × 2 = 25 \begin{aligned} & 圖1：WPL = 1 \times 2 + 3\times2 + 4 \times 2 + 5 \times 2 = 26\\ & 圖2：WPL = 1 \times 3 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 25 \\ & 圖3：WPL = 5 \times 1 + 3 \times 3 + 1 \times 3 + 4 \times 2 =25 \end{aligned} 圖1：WPL=1×2+3×2+4×2+5×2=26圖2：WPL=1×3+3×3+4×2+5×1=25圖3：WPL=5×1+3×3+1×3+4×2=25
其中，圖2和圖3的帶權路徑長度最小的樹，即哈夫曼樹。也就是說，哈夫曼樹不唯一。
哈夫曼樹的構造
- 先将要構造哈夫曼樹的節點放入一個集合
- 每次從集合中挑出兩個權值最小的節點，組成新的樹。左右順序無所謂
- 将新的樹加入集合，并删除原來的那兩個節點
- 重複2,3動作，直到集合中隻剩下一棵樹。則這棵樹就是哈夫曼樹
哈夫曼樹的代碼實作
todo，非重點，後期補充
哈夫曼樹的應用
哈夫曼編碼
哈夫曼編碼主要用于資料壓縮。
考慮如下場景，目前需要傳輸一段文本，其中隻包含A,B,C,D，其中他們出現的頻率不一樣：分别為 A(10)，B(8)，C(80)，D(2)。如果按照ascii碼（一個字母1個位元組，也就是8個bit）進行對ABCD進行編碼，不用說，肯定需要很大的空間。如果簡化一下，對A,B,C,D進行如下編碼：
A: 00
B: 01
C: 10
D: 11
這種編碼每個字母的二進制位是一緻的，稱為固定長度編碼，此時如果傳遞資料的話，需要200個bit位，計算方式如下：
10 ∗ 2 + 8 ∗ 2 + 80 ∗ 2 + 2 ∗ 2 = 200 10 * 2 + 8*2 + 80 * 2 + 2 * 2= 200 10∗2+8∗2+80∗2+2∗2=200
如果将上述編碼使用樹進行表示，則如下圖所示：
其中左邊的邊代表0，右邊的邊代表1。葉節點的權值就是該節點出現的頻率。則該樹的WPL就是要傳輸的bit長度。
此時，為了減少傳輸長度，就可以通過構造哈夫曼樹，來将資料壓縮到最小。構造後結果如下：
此時，各個字母的編碼情況如下：
A: 10
B: 111
C: 0
D: 110
這種每個資料的編碼長度不一緻，就成為可變長度編碼。此時，需要傳輸的資料長度為：
W P L = 80 ∗ 1 + 10 ∗ 2 + 2 ∗ 3 + 8 ∗ 3 = 130 WPL = 80*1 + 10 * 2 + 2 * 3 + 8 * 3 = 130 WPL=80∗1+10∗2+2∗3+8∗3=130
這樣資料就得到了壓縮。
注意：
一個編碼不能是另一個編碼的字首，否則接受方就沒法識别了。如果對應到哈夫曼樹上，也就是說隻有葉節點能存儲資料，分支節點不可以存在資料。