程式扎記: [ 知識小學堂 ] 字串演算法 : Huffman Code

標籤

2011年2月15日 星期二

[ 知識小學堂 ] 字串演算法 : 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 來取代檔案中的所有字元.

13 則留言:

  1. 謝謝提供淺顯易懂的解說,我照著圖解說明手寫一次就了解要點了!其他地方的說明都沒有這裡好懂。

    回覆刪除
  2. 請問一下,作出來只會有一種結果嗎?

    回覆刪除
  3. 不一定說, 有可能你的某些字元具有一樣的出現次數且這些字元的數量大於2, 這樣在挑最小的兩個 node 時, 你可能的組合就不只一種,當然最後生成的碼也是有可能不一樣...

    回覆刪除
  4. 作者已經移除這則留言。

    回覆刪除
  5. 不好意思 請問一下關於要再分另一顆二元樹是要依據什麼下去分的呢??
    就是b c f 和 a i這兩棵樹
    會何這時不是a這點又繼續擺在b c f這顆樹裡呢??

    謝謝 因為一直不知道怎麼分成不只一顆二元樹結果最後分出來變得很奇怪

    回覆刪除
    回覆
    1. 抱歉這麼回你, 先說聲新年快樂. 你的問題關鍵在每個哪出來合併的兩個 node. 合併完的 tree 還要放回原來的 node list. 所以當 bcf 合併完後的 tree=5 放回去後按照規則三. 下去取出來最小的兩個 node 會是 a(3) 和 i(3)並合併成 ai(6). 如此合併下去直到 node list 只剩下一個 node. 不知道這樣說明你清楚嗎?

      刪除
    2. 原本也有這問題,但看完上面說明後已解惑

      刪除
  6. 請問9和11合併的時候,為什麼不是11放在左邊?

    回覆刪除
    回覆
    1. 放在左邊/右邊會影響編碼結果, 但部會影響編碼長度, 所以 9 跟 11 合併時哪個在左邊都可以.

      刪除
  7. 作者已經移除這則留言。

    回覆刪除

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!