哈夫曼樹
出自 MBA智库百科(https://wiki.mbalib.com/)
哈夫曼樹(Huffman Tree)
目錄 |
哈夫曼樹是指給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小的最優樹理論。
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為w1、w2、…、wn，則哈夫曼樹的構造規則為：
1、將w1、w2、…、wn，看成是有n 棵樹的森林(每棵樹僅有一個結點)；
2、在森林中選出兩個根結點的權值最小的樹合併，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
3、從森林中刪除選取的兩棵樹，並將新樹加入森林；
4、重覆2、3步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
1、哈夫曼編碼
在數據通信中，需要將傳送的文字轉換成二進位的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的報文為“AFTER DATA EAR ARE ART AREA”，這裡用到的字元集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進位編碼方式是等長編碼，固定採用3位二進位，可分別用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收報文時再按照三位一分進行解碼。顯然編碼的長度取決報文中不同字元的個數。若報文中可能出現26個不同字元，則固定編碼長度為5。然而，傳送報文時總是希望總長度儘可能短。在實際應用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高於X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。
為使不等長編碼為首碼編碼(即要求一個字元的編碼不能是另一個字元編碼的首碼)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，於是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進位的首碼編碼，既滿足首碼編碼的條件，又保證報文編碼總長最短。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(28 = 256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--232-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。
2、哈夫曼解碼
在通信中，若將字元用哈夫曼編碼形式發送出去，對方接收到編碼後，將編碼還原成字元的過程，稱為哈夫曼解碼。
1、路徑和路徑長度
在一棵樹中，從一個結點往下可以達到結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。
2、結點的權及帶權路徑長度
若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
3、樹的帶權路徑長度
樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。
4、哈夫曼樹也可以是k叉的，只是在構造k叉哈夫曼樹時需要先進行一些調整。構造哈夫曼樹的思想是每次選k個權重最小的元素來合成一個新的元素，該元素權重為k個元素權重之和。但是當k大於2時，按照這個步驟做下去可能到最後剩下的元素少於k個。解決這個問題的辦法是假設已經有了一棵哈夫曼樹(且為一棵滿k叉樹)，則可以計算出其葉節點數目為(k-1)nk+1,式子中的nk表示子節點數目為k的節點數目。於是對給定的n個權值構造k叉哈夫曼樹時,可以先考慮增加一些權值為0的葉子節點，使得葉子節點總數為(k-1)nk+1這種形式,然後再按照哈夫曼樹的方法進行構造即可。
