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 來取代檔案中的所有字元.

16 則留言:

  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. 原本也有這問題,但看完上面說明後已解惑

      刪除
    3. 我找好多網頁就是想問這個問題!感謝說明

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

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

      刪除
    2. 你好 這個教學是從左樹建到右樹 那我想請問一下 國家考試的題目解答 都是從右子樹建到左子樹 我知道編碼會不同 但長度會一樣 那到底哪個是正確的呢??

      刪除
    3. 很好的問題, 但你抓到重點, "長度一樣". 那為什麼你要使用 "Huffman Code"? 簡單來說:
      * 越常出現的字元使用越短的編碼.
      * 越不常出現的字元使用相對長的編碼

      如此整個來看編碼所需要的長度便會壓縮且不失真. 因此回到你的問題, 這是一個建立字元與編碼的對應表, 當長度一樣, 你還會在意是左樹到右樹, 還是右樹到左樹?
      不過如果是國家考試, 相信應該會給提示或範例以確保答案一致, 或是改答案是看你的過程而不是最終答案.
      Again, 如果有疑問, 可以問問給答案的單位搂.

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

    回覆刪除

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...