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 ---