[ 知識小學堂 ] 字串演算法 : Huffman Code

前言 : 
在考慮檔案壓縮時, 每個字元都必須有一個二元編碼, 而 Huffman Code 則是最節省空間的字元編碼方式. 

建立 Huffman Tree : 
考慮以下字串 : 

a a a b b c d d d d d d e e e e e f f g g g g g g h h h h i i i

(一) 針對相異字元, 統計其出現的個數 : 
 

(二) 為每個字元建立一顆單一節點的樹, 每棵樹的根節點之關鍵值(紅色字)為其代表字元的出現個數. 
 

(三) 找出根節點關鍵值最小的兩顆樹. 

(四) 產生一個根節點, 並將找到的兩棵樹分別當作此根節點的左右子樹, 而根節點的關鍵值為左右子樹節點的合. 

(五) 重複步驟 3 與 4 , 直至全部合併為一棵樹 : 

* 注意一 : Huffman Tree 的每個葉節點代表一個相異字元, 且葉節點的個數恰等於相異字元樹.
* 佇義二 : 我們亦可以用相異字元出現的機率代替其出現個數.

 
 
 

產生 Huffman Code : 
(一) 在 Huffman Tree 中, 針對每個節點, 將連至左子樹的邊標為0, 將連至右子樹的邊標示為1. 
 

(二) 針對每個由根節點至葉節點的路徑, 將其所經過邊的標示連結起來, 並指派給對應葉節點所代表的字元, 此即 Huffman Code : 
 

壓縮檔案 : 
當產生所有字元的 Huffman Code 後, 我們可以利用 Huffman Code 來取代檔案中的所有字元.