2013年1月11日 星期五

Huffman Coding by Matlab

在上篇文章中,我們已將機率陣列轉換成霍夫曼二元樹,詳情可參閱《這裡》。

現在要從霍夫曼二元樹,由上而下賦予霍夫曼編碼值。方法很簡單,就是從樹根開始,往左的路徑(branch)就記錄0,往右就記錄1,一直到樹葉(leaf node)為止。從樹根到樹葉,經過多少0與1就是它的霍夫曼編碼了。

接續上次的例子,輸入以下的機率陣列:





得到以下的霍夫曼二元樹:



在每個父節點的左分支紀錄0, 右分支紀錄1,得到以下的圖型:



從樹根到每個節點的路徑紀錄就是霍夫碼了,所以答案就是:

1→1
2→011
3→000
4→001
5→0100
6→0101

好了,現在要如何用Matlab來完成這件事呢?回到上次的程式碼

  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 = tree;


上面程式的輸出是一個cell, 其實就是一個二元樹,如果我們用matlab的指令celldisp就可以完整顯示輸出的結果。

>> A = [0.5  0.125 0.125 0.125 0.0625 0.0625 ];
>> mytree = ghftree(A);
>> celldisp(mytree)

mytree{1}{1}{1} =
     3

mytree{1}{1}{2} =
     4
 
mytree{1}{2}{1}{1} =
     5

mytree{1}{2}{1}{2} =
     6

mytree{1}{2}{2} =
     2

mytree{2} =
     1



若將celldisp輸出的{1}以0代替,{2}以1代替,結果就是Huffman編碼了。我們也可以自己寫一個遞迴的matlab程式來取代celldisp的輸出,程式如下:

  1. function prhcode(tree,code)
  2. if isa(tree,'cell')
  3.     prhcode(tree{1},[code '0']);
  4.     prhcode(tree{2},[code '1']);
  5. else
  6.     mystr = strcat(num2str(tree) , '=' , code);
  7.     disp(mystr);
  8. end

第2行:如果輸入值是一個cell, 表示它是父節點
第3行:往左的branch紀錄'0',並繼續往下探索子樹(subtree)
第4行:往左的branch紀錄'1',並繼續往下探索子樹(subtree)
第5行:如果輸入值不是一個cell, 表示它是葉節點
第6行:擬顯示資料的格式設定
第7行:輸出結果

現在來試試看吧!


Octave 也來試試



都可以!大功告成!

--- end ---















14 則留言:

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

    回覆刪除
  2. 版大您的文章寫得真是仔細,讓我這個初學者一目了然,謝謝!
    目前遇到些問題,是否可以請教,
    假設有一個64x64的矩陣,其中各元素包含
    15個1,
    20個2,
    17個3,
    其餘4044個均為0(64x64-15-20-17)
    需要以「無失真壓縮」方法將之壓縮,
    以huffman coding是否可以得到最小位元率?
    或是有其他「無失真壓縮」方法可以應用?
    謝謝!感激不盡

    回覆刪除
    回覆
    1. Huffman Coding 在不考量「事件」出現的先後情形下,有最好的壓縮率。但如果已經知道「事件」有某種規則的排列,Huffman 就不會是最好的方法。如果所有的1擠在一起,2,3,0也都是互相擠在一起,這樣的矩陣可以用區塊壓縮(用二元樹,或四元樹)效果比Huffman coding 更好。但0 1 2 3 是亂數排列, Huffman coding 就比較好。總之, 要看被壓縮資料的特性, 才能決定哪一種壓縮法比較好!

      刪除
  3. 謝謝你的回答!因為對這方面的知識仍在琢磨階段,
    再次請教:區塊壓縮(用二元樹,或四元樹),
    是否有明確的編碼名稱或matlab code可以參考?
    謝謝

    回覆刪除
  4. 版主您好...操作實有發現錯誤訊息, 請您指導.

    >> A = [0.5 0.125 0.125 0.125 0.0625 0.0625 ];
    mytree = ghftree(A);
    celldisp(mytree)
    mytree{1}{1}{1}=
    Error using celldisp (line 14)
    Must be a cell array.

    回覆刪除
    回覆
    1. 沒有錯啊!我又跑了一遍
      ----- 執行結果 完全正確 --------
      octave.exe:3> A = [0.5 0.125 0.125 0.125 0.0625 0.0625 ];

      octave.exe:4> mytree = ghftree(A);

      octave.exe:5> celldisp(mytree)

      mytree{1}{1}{1} =

      3

      mytree{1}{1}{2} =

      4

      mytree{1}{2}{1}{1} =

      5

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

      刪除
    3. 版主您好...不好意思, 我是用Matlab 2014a執行, 是否會不同? 另外, 說明一下我的執行環境: ghftree.m程式內容如版主所教(如下), 先執行
      A=[0.5 0.125 0.125 0.125 0.0625 0.0625];
      ghftree(A)
      沒問題.

      但後執行
      A = [0.5 0.125 0.125 0.125 0.0625 0.0625 ];
      mytree = ghftree(A);
      celldisp(mytree)
      就有錯誤訊息.
      Error using celldisp (line 14)
      Must be a cell array.
      =======================
      function HT = ghftree(p)
      tree = cell(length(p),1);
      for i=1:length(p)
      tree{i}=i;
      end
      while numel(tree)>2
      [p, pos] = sort(p,'ascend');
      p(2)=p(1)+p(2);
      p(1)=[];
      tree = tree(pos);
      tree{2}={tree{1},tree{2}};
      tree(1)=[];
      end
      HT = printtree(tree);
      function tt = printtree(tree)
      if isa(tree,'cell')
      tt = strcat('(', printtree(tree{1}),printtree(tree{2}),')');
      else
      tt = num2str(tree);
      end

      刪除
    4. 我終於搞懂您的問題了!!
      您所用的程式是錯誤的, 您應該用本網誌function HT = ghftree(p),而不是上個網誌(http://chu246.blogspot.tw/2013/01/huffman-tree-using-matlab.html)同名的程式。總之 ghftree(p)不可內含printtree(tree), printtree(tree)會將cell轉換成char, 因此不能用disp來顯示HT。

      刪除
  5. 請問要如何把輸出的mystr匯入回主程式
    而不是秀出在common windows
    因為想把輸出的Huffman code做出其他運算

    回覆刪除
    回覆
    1. 你說的mystr 是程式中的mytree嗎?
      ghftree的輸出就可以拿到其他程式去用啊!

      刪除
    2. 我是指這段程式
      function prhcode(tree,code)
      if isa(tree,'cell')
      prhcode(tree{1},[code '0']);
      prhcode(tree{2},[code '1']);
      else
      mystr = strcat(num2str(tree) , '=' , code);
      disp(mystr);
      end
      要如何把值回傳至主程式

      刪除
  6. 為什麼會跑出這個Undefined function or variable 'p'.

    回覆刪除
  7. 請問如何把function prhcode 程式裡面的mystr儲存到workspace裡面?

    回覆刪除