huffman.m

读入一段数据

% Source Coding -- Problem 2.1 Huffman coding

clear all;

ascii=zeros(1,64);          % vector to store ASCII code of each symbol
count=zeros(1,64);          % vector to store the times of each symbol
pro=zeros(1,64);            % vector to store the probality of each symbol

for i=1:64
    for j=1:64
        huff(i,j)=' ';      % matrix to store the Huffman codes, each row refers to one symbol
    end
end

huff_length=zeros(1,64);    % vector to store the length of the Huffman code for each symbol
refer=zeros(1,64);          % vector to store the pointer of each symbol

for i=32:95
    ascii(i-31)=i;          % calculate the ASCII codes
end

text= fileread('huff.txt'); % read in the text
l = length(text);           % length of the text



% Calculate the times of each symbol in the text

for m = 1:l 
    count(text(m)-31)=count(text(m)-31)+1;
end



% Calculate the probability of each symbole in the text

for m= 1:64 
    pro(m)=count(m)/l;
end



% Calculate the entropy of the source text.

HA = 0;                     % entropy
ns = 0;                     % number of different symbols in the text 
for m= 1:64
    if count(m) > 0
        HA=HA-pro(m).*log2(pro(m));
        ns = ns+1;
    end   
end



% Huffman encoding

temp=pro;                   % to temporarily store the probablities

for i=1:ns-1
    [a,b]=min2(temp);       % to get indexes of the two symbols with lowest occuring probabilites
    
    temp(a)=temp(a)+temp(b);% to store the sum of these two probabilities in the first one
    temp(b)=0;              % and to clear the second one
    refer(b)=a;             % with a pointer referring to the first one
    
    for k=1:64
        if refer(k)==b
            refer(k)=a;     %to check the former pointers and modify them to refer to the new one
        end
    end
    
    huff(a,i)='0';          % the first one can get one bit more for encoding
    huff_length(a)=huff_length(a)+1;
    
    for k=1:64
        if refer(k)==a
            huff(k,i)='1';  % the second one can also get one bit more for encoding
            huff_length(k)=huff_length(k)+1;
        end
    end
    
end



% Get the length of a codeword for the space character ' ' and for letter 'M'

lsp=huff_length(' '-31);
lm=huff_length('M'-31);



% Calculate the expected length of the obtained code

la=0;
for i=1:64
    item = pro(i).*huff_length(i);
    la = la + item;
end



sprintf('The entropy of the source is %g', HA)
sprintf('The length of a codeword for the space character is %g', lsp)
sprintf('The length of a codeword for letter M is %g', lm)
sprintf('The expected length of the obtained code is %g', la)