huffman.m

信源编码中的哈夫曼编码

%Huffman 编码的MATLAB 程序：
%作者：谢东 于2007年12月
clc;clear;
N=input('N=');%输入信源符号的个数
s=0;l=0;H=0;
for i=1:N
    fprintf('第%d个',i);
    p(i)=input('p=');%输入信源符号概率分布矢量,p(i)<1
    if p(i)<=0
      error('不符合概率分布')
    end
    s=s+p(i)
    H=H+(- p(i)*log2(p(i)));%计算信源信息熵
end
if (s<=0.999999||s>=1.000001)
   error('不符合概率分布')
end
tic;
for i=1:N-1 %按概率分布大小对信源排序
    for j=i+1:N
        if p(i)<p(j)
           m=p(j);
           p(j)=p(i);
           p(i)=m;
        end
    end
end
Q=p;
m=zeros(N-1,N);
for i=1:N-1   %循环缩减对概率值排序，画出由每个信源符号概率到1.0 处的路径，
    [Q,l]=sort(Q);
    m(i,:)=[l(1:N-i+1),zeros(1,i-1)]; 
    Q=[Q(1)+Q(2),Q(3:N),1];
end
for i=1:N-1
    c(i,:)=blanks(N*N); 
end
   c(N-1,N)='1';
   c(N-1,2*N)='0';
for i=2:N-1    %对字符数组c码字赋值过程，记下沿路径的“1”和“0”；
    c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));
    c(N-i,N)='1';
    c(N-i,N+1:2*N-1)=c(N-i,1:N-1);
    c(N-i,2*N)='0';
    for j=1:i-1
        c(N-i,(j+1)*N+1:(j+2)*N)=c(N-i+1,N*(find(m(N-i+1,:)==j+1)-1)+1:N*find(m(N-i+1,:)==j+1));
    end
end
for i=1:N 
    h(i,1:N)=c(1,N*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*N);%码字赋值
    ll(i)=length(find(abs(h(i,:))~=32)); %各码字码长
end
l=sum(p.*ll); %计算平均码长
n=H/l; %计算编码效率
fprintf('按照输入顺序排列的码字:\n');
disp(h) %按照输入顺序排列的码字
fprintf('平均码长:\n');
disp(l) %输出平均码长
fprintf('编码效率:\n');
disp(n) %输出编码效率
fprintf('计算耗时time= %f\n',toc);