從零開始學演算法--哈夫曼樹

• 2021 年 10 月 10 日
• 筆記

哈夫曼樹通常用於壓縮， 先看下哈夫曼樹的由來

 看上面這段程式碼， 結合右圖中各個分數段的比例。 現在假設一共有100個學生， 那麼一共要執行多少次判斷的邏輯呢？

顯然 5 + 15*2 + 40*3 + 30*4 +10*5 = 325次

那麼是否可以優化呢？----當然也是可以的， 我們如果把分數佔比大的判斷往前放， 總的判斷次數就可以減小

如 if (a<80){

}else if(a<90){

}else if (a<70){

}else if (a<100){

}else{
}

那麼總的判斷執行次數就變成了 40 + 30*2 + 15*3 + 10*4 + 5*5 = 210次， 當然，這是一段偽程式碼， 只是體現性能上的提升

現在我們把上面兩段程式碼分別轉換成樹

 這裡引入一個概念叫做樹的路徑

哈夫曼大叔說，從樹中一個節點到另一個節點之間的分支，構成兩個節點之間的路徑，路徑上的分支數目稱為路徑長度。

樹的路徑長度就是樹根到每一個節點的路徑長度之和

 如圖， 二叉樹a的路徑長度為20， 二叉樹b的路徑長度為16

上圖中5，15，40...這些稱為節點的權值

節點的帶權路徑長度  為節點的路徑長度與該節點權值的乘積， 如二叉樹a中， 節點D的帶權路徑長度為4*30 = 120

樹的帶權路徑長度  為樹中所有葉子節點的帶權路徑之和， 如二叉樹a的帶權路徑長度為： 1*5 + 2*15 + 3*40 +4*30 +4*10 = 315

二叉樹b的帶權路徑長度為：3*5+3*15+2*40+2*30+2*10 = 220

對於一棵有n個葉子節點的二叉樹， 我們可以隨意組合出很多種， 其中帶權路徑長度最小的二叉樹稱為哈夫曼樹

那麼下一步，如何構造一棵哈夫曼樹呢？

1）先把有權值的葉子節點按照權值從小到大的順序排成一個有序序列

A5  E10 B15 D30 C40

2）取最小的兩個葉子作為節點N1的子節點, 注意較小的為左兒子，新節點的權值為兩個子節點的權值之和

 3）用N1替換A和E，插入有序序列中， 保持從小到大排序，即N15  B15 D30 C40

4)  重複步驟2）， 將N1和B作為新節點N2的子節點，較小的為左兒子，新節點的權值為兩個子節點的權值之和

 5)用N2替換N1和B，插入有序序列中， 保持從小到大排序，即N30 D30 C40

6）重複步驟2），將N2和D作為新節點N3的子節點

 7）用N3替換N2和D， 插入有序序列中， 保持從小到大排序，即C40 N60 

 8）因為只剩最後兩個元素， 因此C40和N60成為新節點T的子節點，T即為根節點

 上圖即構造了一棵哈夫曼樹， 

 它的帶權路徑長度為 1*40 + 2*30 + 3*15 +4*5 +4*10 = 205

小結： 構建哈夫曼樹的一般過程：

首先把葉子節點排成排成有序序列，

然後取最小的兩個構建樹葉， 用他們的和值構建他們的父節點，

把父節點放到序列中，再重複上面的步驟

接下來我們看看程式碼實現：

（有點累了，明天再寫）

哈夫曼編碼：

哈夫曼編碼的目的是數據壓縮

比如ABCDEF的二進位表示如下

此時假設我們要存儲ABCDE， 則電腦存儲的是000001010011100 共15個字元

 那麼我們在哈夫曼樹中，將節點的左路徑權值用0替換，右路徑用1替換，則得到下圖

 那麼A=1000   B=101   C=0   D=11  E=1001

 此時存儲ABCDE，則電腦存儲10001010111001共15個字元

好像沒什麼大變化是吧？😄

這是因為我們沒有引入權值，我們知道哈夫曼樹是基於權值來構建的， 回到本文最開始的例子

假設一共100個數字， A出現5次，B出現15次，C出現40次，D出現30次， E出現10次， 那麼按照正常編碼， 電腦存儲這100個ABCDE共計需要100*3 = 300個字元

但是如果用哈夫曼編碼， 則只需要存儲 4*5 + 3*15 +1*40 + 2*30 + 4*10 = 205 個字元

節約了31.6%的存儲空間