2013年1月10日 星期四

Huffman Tree using Matlab

先來複習一下霍夫曼樹(Huffman Tree)是如何產生的。假設有六個數字,分別是 0.5, 0.125, 0.125, 0.125, 0.0625, 0.0625。這六個數字其實代表機率,而且相加等於壹。產生霍夫曼樹的演算法簡單講起來就是:
初始值:每個節點(NODE)的值就是剛才的六個機率值,所以共有六個節點

第一步:排序
第二步:將最小值的兩個節點合併成成一個,合併後的節點值就是合併前兩個節點值相加。
重複以上第一步及第二步,直到剩下一個節點為止。最後一個節點的值就是原節點值的總合,也就是壹。


在第二步中,合併兩節點(假設叫節點A與節點B)產生的新節點(假設是節點C),新節點就是原兩節點的父節點;相對地,原兩節點就是子節點。也就是說C是A與B共同的父節點,至於A與B當然是C的子節點。霍夫曼樹就是經由以上的排序及合併步驟產生的二元樹。

以實例圖解上述步驟:

初始狀態:有6個節點


step1: 排序
step2: 合併


step1: 排序

step2: 合併


step1: 排序
step2: 合併


step1: 排序

step2: 合併



step1: 排序


step2: 合併


重複五次的排序及合併動作,最後得到了霍夫曼二元樹。

為了簡化表示,我們以(A B) 代表節點A與節點B共同的父節點。所以最後的霍夫曼二元樹就是 (((3 4)((5 6) 2))1)

現在我們要用Matlab來完成這樣的要求,輸入 [0.5 0.125 0.125 0.125 0.0625 0.0625],輸出結果為 (((3 4)((5 6) 2))1)

我們可以利用Matlab的cell來完成樹狀結構的要求,cell裡面可以有cell,這種巢狀結構適合樹狀結構的需求。

程式如下:
  1. function HT = ghftree(p)
  2. tree = cell(length(p),1);       %產生與陣列p相同長度的cell
  3. for i=1:length(p)
  4.     tree{i}=i;                           %每個節點的代號初始值依序為1,2,3...
  5. end
  6. while numel(tree)>2       
  7.     [p, pos] = sort(p,'ascend'); %從小排到大
  8.     p(2)=p(1)+p(2);                %將最小及次小的值相加,存到次小位置
  9.     p(1)=[];                              %刪除最小值的元素,因此陣列p的個數少一個
  10.     tree = tree(pos);              %節點依照p值大小排序
  11.     tree{2}={tree{1},tree{2}}; %最小及次小的節點合併,存至次小節點內
  12.     tree(1)=[];                          %刪除最小的節點
  13. end
  14. HT = printtree(tree);
  15. function tt = printtree(tree)      %將樹結構(cell)印出來
  16. if isa(tree,'cell')    %如果是一個cell,就印左括號,左樹,右樹,右括號
  17.     tt = strcat('(', printtree(tree{1}),printtree(tree{2}),')');
  18. else
  19.     tt = num2str(tree);%如果不是cell,就印內含的值(把數字轉換成字串)
  20. end


以上程式中,輸入的p是一個一維矩陣,tree一開始的長度與p相同。在while 迴圈內,p與tree的長度一直遞減,但tree減少的元素"塞進"其它元素內,形成樹狀結構。
第12行中,tree(1)=[]; 不可寫成 tree{1}=[]; 後者的意思是將tree第一個元素清空,不是刪除。
第14行是一個遞迴到程式,將tree以左括號、左樹、右樹、右括號的方式,遞迴印出。
第19行:因為tree的初始值在第4行設定為數字,所以需要轉換成字串形態印出來。

實際執行看看吧!


答案正確!

--- end ---









7 則留言:

  1. 回覆
    1. 相加之後相同的值應該移到最後面

      刪除
    2. 不曉得妳說的是不是 第八行:p(2)=p(1)+p(2);
      相加之後放在第2個,第1個會被刪除,所以第2個變成了第1個。重點是後面的步驟還要再排序,所以不需要移到特定的位置!

      刪除
  2. 請問要如何製造二元樹 matlab~QQ

    回覆刪除
  3. 不好意思 我是MATLAB新手
    請問一下ghftree()是要自己設嗎?謝謝

    回覆刪除