huff.m

哈夫曼树

function huff(str)  
if ~exist('str','var') %var is a keyword defined by exist function
    %str=['aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccccccdddddddddddddddddeeeeeeeeeeeeeeeffffffffffg'];
    %str=['aaabbbbcccccccdddddddddd'];
    str=['cccccccccccccccdddddddddddddddddeeeoooooeeeeeeeeeeeeffffffffaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbcccffg'];
    %str=['ccaaabbbbbbcdddccccddddddd'];
end
n=length(str);  
list=[];p=[];
% count characters
for i=1:n
    k=find(list==str(i)); %"find" finds the offset of some character in the array   
    if(length(k)==0)
        list=[list;str(i)];
        p=[p;1];
    else
        p(k)=p(k)+1;
    end
end
disp( 'character count (list):')
for i=1:length(p)
    disp([list(i) ': ' num2str(p(i))]);
end
% p contains the numbers of the characters in str
% "list" is the characters, the sequence of the list is according to the
% sequence of occurrence in "str"
tempp=p/sum(p);
%---------------------
% sort p
pp=-p; [pp t]=sort(pp); p=-pp; %pp是降序实际排序结果，t是pp中的某个元素在原来数组中的位置。
%[p t]=sort(p,'descend');实现按降序排列
l(1:length(list))=list(t);
disp( 'after sort:')
m=length(p);
for i=1:m
    disp([l(i) ': ' num2str(p(i))]);
end
% make tree
len=length(t);
tr=zeros(len,1);%len行，1列的0
tr(t)=1:len; %tr是list按降序排列后的脚标
disp( 'start to build the haffman tree:')
p=p/sum(p); % p is a vector with the probability 
listp=p;
disp('% tr is a pointer vector which means the relationship between p and list');
disp('% It is the leaf of huffman tree');
disp(tr'); 
disp('% p is a vector with the probability');
disp(p');
ltr=length(tr);% augment with the growing of the huffman tree
lp=length(p);% decrease with the growing of huffman tree
roolp=3;
while lp>1
    %if(length(list)-lp+1 <= 9)
      %subplot(roolp,roolp,length(list)-lp+1);
      figure(length(list)-lp+1);
      drawhufftree(tr,list,tempp);
    %end
    % merge p(lp) and p(lp-1);
    p(lp-1)=p(lp-1)+p(lp);
    p=p(1:lp-1);
    % tr(ltr+1) is a new node of the huffman tree
    % tr(find(tr==lp)) and tr(find(tr==lp-1)) is its two children
    ltr=length(tr);
    tr(find(tr==lp))=ltr+1;
    tr(find(tr==lp-1))=ltr+1;
    tr(ltr+1)=lp-1;
    tempp(ltr+1)=p(lp-1); % record the probability of this node
    % sort p again after merging;
    pp=-p; [pp t]=sort(pp); p=-pp;
    %[p,t]=sort(p,'descend');
    lp=length(p);
 % tempp(1:lp-1)=p(1:lp-1); % update the order of probability to display
    % update the pointer of tr then
    temp=tr;
    for j=1:lp
        tr(find(temp==t(j)))=j;
    end
    %show the middle result
    disp('tr:(huffman tree)');
    disp(tr');
    disp('tempp:(probability on the tree)');
    disp(tempp');
    disp('p:(probability)');
    disp(p');
    disp('t:(sort of p)');
    disp(t');
end
 tr(length(tr))=0; % the root of huffman tree
 %draw the result
 figure(length(list)-lp+1);
 drawhufftree(tr,list,tempp);
end
% :) hope you love it