現在要從霍夫曼二元樹,由上而下賦予霍夫曼編碼值。方法很簡單,就是從樹根開始,往左的路徑(branch)就記錄0,往右就記錄1,一直到樹葉(leaf node)為止。從樹根到樹葉,經過多少0與1就是它的霍夫曼編碼了。
接續上次的例子,輸入以下的機率陣列:
得到以下的霍夫曼二元樹:
在每個父節點的左分支紀錄0, 右分支紀錄1,得到以下的圖型:
從樹根到每個節點的路徑紀錄就是霍夫碼了,所以答案就是:
1→1
2→011
3→000
4→001
5→0100
6→0101
好了,現在要如何用Matlab來完成這件事呢?回到上次的程式碼
- function HT = ghftree(p)
- tree = cell(length(p),1); %產生與陣列p相同長度的cell
- for i=1:length(p)
- tree{i}=i; %每個節點的初始值依序為1,2,3...
- end
- while numel(tree)>2
- [p, pos] = sort(p,'ascend'); %從小排到大
- p(2)=p(1)+p(2); %將最小及次小的值相加,存到次小位置
- p(1)=[]; %刪除最小的值,因此陣列p個數少一個
- tree = tree(pos); %節點依照p值大小排序
- tree{2}={tree{1},tree{2}}; %最小及次小的節點合併,存至次小節點內
- tree(1)=[]; %刪除最小的節點
- end
- 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的輸出,程式如下:
- 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
第2行:如果輸入值是一個cell, 表示它是父節點
第3行:往左的branch紀錄'0',並繼續往下探索子樹(subtree)
第4行:往左的branch紀錄'1',並繼續往下探索子樹(subtree)
第5行:如果輸入值不是一個cell, 表示它是葉節點
第6行:擬顯示資料的格式設定
第7行:輸出結果
現在來試試看吧!
Octave 也來試試
都可以!大功告成!
--- end ---
作者已經移除這則留言。
回覆刪除版大您的文章寫得真是仔細,讓我這個初學者一目了然,謝謝!
回覆刪除目前遇到些問題,是否可以請教,
假設有一個64x64的矩陣,其中各元素包含
15個1,
20個2,
17個3,
其餘4044個均為0(64x64-15-20-17)
需要以「無失真壓縮」方法將之壓縮,
以huffman coding是否可以得到最小位元率?
或是有其他「無失真壓縮」方法可以應用?
謝謝!感激不盡
Huffman Coding 在不考量「事件」出現的先後情形下,有最好的壓縮率。但如果已經知道「事件」有某種規則的排列,Huffman 就不會是最好的方法。如果所有的1擠在一起,2,3,0也都是互相擠在一起,這樣的矩陣可以用區塊壓縮(用二元樹,或四元樹)效果比Huffman coding 更好。但0 1 2 3 是亂數排列, Huffman coding 就比較好。總之, 要看被壓縮資料的特性, 才能決定哪一種壓縮法比較好!
刪除謝謝你的回答!因為對這方面的知識仍在琢磨階段,
回覆刪除再次請教:區塊壓縮(用二元樹,或四元樹),
是否有明確的編碼名稱或matlab code可以參考?
謝謝
版主您好...操作實有發現錯誤訊息, 請您指導.
回覆刪除>> 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.
沒有錯啊!我又跑了一遍
刪除----- 執行結果 完全正確 --------
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
作者已經移除這則留言。
刪除版主您好...不好意思, 我是用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
我終於搞懂您的問題了!!
刪除您所用的程式是錯誤的, 您應該用本網誌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。
請問要如何把輸出的mystr匯入回主程式
回覆刪除而不是秀出在common windows
因為想把輸出的Huffman code做出其他運算
你說的mystr 是程式中的mytree嗎?
刪除ghftree的輸出就可以拿到其他程式去用啊!
我是指這段程式
刪除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
要如何把值回傳至主程式
為什麼會跑出這個Undefined function or variable 'p'.
回覆刪除請問如何把function prhcode 程式裡面的mystr儲存到workspace裡面?
回覆刪除