WPL 和哈夫曼樹
哈夫曼樹,又稱最優二叉樹,是一棵帶權值路徑長度(WPL,Weighted Path Length of Tree)最短的樹,權值較大的節點離根更近。
首先介紹一下什麼是 WPL,其定義是
樹的所有葉結點的帶權路徑長度之和,稱為樹的帶權路徑長度
,公式為 WPL = W1 L1 + W2 L2 + W3 L3 + ... + Wn Ln。
下面是個最簡單且最直覺的案例,通過實際案例能夠更清晰的表示 WPL 和哈夫曼樹。
百分制的成績轉換成五分制的成績,僞代碼如下:
if (score < 60) grade = 1;
else if (score < 70) grade = 2;
else if (score < 80) grade = 3;
else if (score < 90) grade = 4;
else grade = 5;
通過這個規則,可以生成一棵判定樹,如下:
score < 60
/ \
grade = 1 score < 70
/ \
grade = 2 score < 80
/ \
grade = 3 score < 90
/ \
grade = 4 grade = 5
根據判定樹可以看出:對于 60 分以下的分數,隻需要一次就能夠給出結果;對于 60~70 分的成績,需要判斷 2 次給出結果;對于 70~80 的成績則需要判斷 3 次,依次類推。
那麼問題來了,絕大多數成績處于 80~90 分,隻有少數成績處于 60 分以下及 90 分以上,那判斷的次數是不是有點多呢?其中這個"絕大多數"和"少數"就是一個權值的概念了。
比如成績分布如下:
| 成績 | 0~59 | 60~70 | 70~80 | 80~90 | 90~100 |
| 比例 | 0.05 | 0.15 | 0.30 | 0.40 | 0.10 |
那麼判斷次數等于: WPL = 0.05 1 + 0.15 2 + 0.30 3 + 0.40 4 + 0.10 * 5 = 3.35
這裡産生一個想法:假如把 80~90 的判斷拿到最前面,不就能夠減少大部分成績的計算路徑了嗎?
修改後的判定樹應該是這樣的
score < 80
/ \
score < 70 score < 90
/ \ / \
score < 60 grade = 3 grade = 4 grade = 5
/ \
grade = 1 grade = 2
其判斷次數等于:WPL = 0.40 2 + 0.30 2 + 0.10 2 + 0.15 3 + 0.05 * 3 = 2.2
通過上面的案例,就能夠得出結論,哈夫曼樹能夠根據節點的查找頻率來構造更有效的搜尋樹,是 WPL 最小的樹。
哈夫曼樹的構造可以了解為将權值最小的兩棵二叉樹合并,這個樹的權值等于 2 個子樹的和。
關于如何選取兩個權值最小的二叉樹,可以使用最小堆實作,複雜度是 O(N log N)。
比如權值:{1,2,3,4,5},可以得出:
15 // 輸出 15
/ \
6 9 // 取出 4,5 ;輸出 9,得出 {6,9}
/ \ / \
3 3 4 5 // 取出 3,3 ;輸出 6,得出 {6,4,5}
/ \
1 2 // 取出 1,2 ;輸出 3,得出 {3,3,4,5}
計算以下 WPL = 2 3 + 2 4 + 2 5 + 3 1 + 3 * 2 = 33
哈夫曼樹的特點:
- 沒有度為 1 的節點(即不存在隻有一個子節點的節點)
- n 個葉子節點的哈夫曼樹,總節點數為 2n-1
- n0:葉節點總數
- n1:隻有一個子節點的節點總數
- n2:有兩個子節點的節點總數
- 那麼 n2 = n0 - 1
- 由于沒有度為 1 的節點,是以其總節點數為 n + n - 1 = 2n-1
- 哈夫曼樹任意非葉節點的左右子樹交換後仍是哈夫曼樹
- 對同一權值{W1,W2,W3,...,Wn},允許存在不同構造的兩顆哈夫曼樹
哈夫曼編碼
哈夫曼編碼用于資料存儲中做壓縮,如下案例:
給定一段包含 50 個字元的字元串,由 {a,b,c,d,e,f}構成,且每個字元出現次數不同,會有如下幾種存儲方式。
- 等長 ASCII 編碼,存儲長度為 50 * 8 = 400 位
- 等長 3 位編碼,存儲長度為 50 * 3 = 150 位
- 不等長編碼,出現頻率高的字元編碼短些,出現頻率低的字元編碼長些。
第三種便可以使用哈夫曼樹來實作,假如給定:
| 字元 | a | b | c | d | e | f |
| 次數 | 18 | 4 | 16 | 1 | 1 | 10 |
構成哈夫曼樹:
50
0/ \1
a(18) 32
0/ \1
c(16) 16
0/ \1
6 f(10)
0/ \1
2 b(4)
0/ \1
d(1) e(1)
是以:a:0; b:1101; c:10; d:11000; e:11001; f:111 。
長度為:1 18 + 4 4 + 16 2 + 1 5 + 1 5 + 10 3 = 106 字元。
emmm... 大概就是這麼個東西。好了,筆記寫完了,繼續學習...