什么是哈夫曼樹?哈夫曼樹的詳細資料講解

2736519 2019-05-08 | pdf | 1.22 MB | 次下載 | 1積分

資料介紹

本文檔的主要內容詳細介紹的是什么是哈夫曼樹?哈夫曼樹的詳細資料講解。

　　在計算機數據處理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。

　　例如，在英文中，e的出現機率最高，而z的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個比特來表示，而z則可能花去25個比特（不是26）。用普通的表示方法時，每個英文字母均占用一個字節，即8個比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對于英文中各個字母出現概率的較準確的估算，就可以大幅度提高無損壓縮的比例。

　　霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+.。.+Wn*Ln），N個權值Wi（i=1，2，。..n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1，2，。..n）。可以證明霍夫曼樹的WPL是最小的。

　　讓我們先舉一個例子。判定樹：

　　在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著程序的執行效率。例如，編制一個程序，將百分制轉換成五個等級輸出。大家可能認為這個程序很簡單，并且很快就可以用下列形式編寫出來：