轉載請注明出處
http://blog.csdn.net/pony_maggie/article/details/41594015
作者:小馬
**一什么是赫夫曼樹**
赫夫曼樹是指帶權路徑最短的樹,從根結點到葉子結點所經過的結點數(不包括根結點,包括葉子結點)叫路徑,如果給葉子結點賦予權值,那么路徑和權值的乘積就是訪問該葉子結點的代價,對于一棵樹來講,使訪問所有的葉子結點的代價最小的樹,就是赫夫曼樹。
比如下面三個圖:

可以計算它們的帶權路徑長度,分別為
(a)????圖是36
(b)????圖是46
(c)????圖是 35
所以c圖是赫夫曼樹。
**二如何構造赫夫曼樹**
構造一棵赫夫曼樹的步驟其實不復雜,簡單來講就是權值大的盡量靠近根結點,而且是越大的越靠近。這樣得出的效果是權值越大的結點,可以經過相對較少的距離到達,從而使程序的效率提高。這里的所說的效率,即包括時間上也包括空間上,后面我會講到兩個應用例子,分別就是一個時間上的優化,一個空間上的優化。
赫夫曼本人給了一個基本的算法,如下:
(1) 將w1、w2、…,wn看成是有n 棵樹的集合F(每棵樹僅有一個根結點);
(2) 在這些樹中選出兩個根結點的權值最小的樹合并,作為一棵新樹的左、右子樹,且新樹的根結點權值為其左、右子樹根結點權值之和;
(3)從F中刪除選取的兩棵樹,并將新樹加入F
(4)重復(2)、(3)步,直到森林中只剩一棵樹為止,該樹即為所求得的哈夫曼樹
**三應用舉例**
了解的具體的算法之后,必須要知道它的應用場景,不然也就只能停留在理論階段了。這里給出兩個應用的例子。
比如統計一次考試中的學生成績,劃分為5個等級,60分以下為不及格,60到70之間是及格,70到80之間是中等,80到90之間是良好,90到100之間是優秀。本次考試各個階段學生所占比例如下:
| 分數 | 0-59 | 60-69 | 70-79 | 80-89 | 90-100 |
|-----|-----|-----|-----|-----|-----|
| 比例 | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 |
假設有10000個學生,然后我們用下面的代碼來實現統計:
~~~
if (a < 60) b = "不及格";
else if (a < 70) b = "及格";
else if (a < 80) b = "中等";
else if (a < 90) b = "良好";
else b = "優秀";
~~~
代碼對應的樹結構如下:

這樣一共需要比較30000多次。上面的代碼不管你的分數是多少,總要從小于60開始比較,比如一個學生的成績是85,他要被比較四次才能有結果,不幸的是, 大部分學生的成績都是在70到90之間,都要經過至少三次以上的比較才能完成。
如果我們能把這個占大多數人的分數區間放在前面,不就可以大大減少比較的次數了嗎?先按照前面章節講的步驟構造一棵赫夫曼樹,如下圖:

對應的代碼是:
~~~
if (a >= 70 && a < 80) b = "中等";
else if (a >= 80 && a < 90) b = "良好";
else if (a >= 60 && a < 70) b = "及格";
else if (a < 60) b = "不及格";
else b = "優秀";
~~~
這樣比較的次數變為22000次,大大提高效率。
再來一個應用的例子。
電報傳送時,一般要把字符轉成二進制的編碼,比如一串字符, “ABACCDA”, 四種字符,可以用二位表示一種,比如A是00, B是01, C是10, D是11,那么電報發送的就是00010010101100,對方收到電報時可以兩位一組解出來。
上面的方法沒有什么問題,但是一般傳送電報肯定希望能用最短的長度傳遞盡量多的信息,是不是還可以優化呢。當然,我們用不同長度的編碼來表示這些字符,出現次數多的字符盡可能的短,出現次數少的可以偏長一些,這樣可以構造出一個比上面更短的電報編碼。
上面的字符信息,A和C現的次數較多,分別為兩次和三次,B和D都是一次。按照上面的方法來構造一棵赫夫曼樹,如下:

規則是左0右1, 這樣,A是0, B是110, C是10, D是111, 最后的編碼是0110010101110, 一共是13個bit位,原來是14個bit位,確實變短了。
再來看看電報接收的一方收到這串編碼能不能解出來,試一下發現可以正常解析,不會產生歧義。這是因為任意一個字符的編碼都不是另一個字符的編碼前綴。這也是二叉樹本身自帶的一個功能,我們通過這種左0右1的方式得到的編碼就可以達到這種效果。
下篇講如何用代碼實現赫夫曼編碼