Huffman编码用MTLAB的实现及编码注释

一、实验内容

1、用Matlab实现Huffman编码算法程序；

2、要求程序输出显示所有的码字以及编码效率；

        3、设计简单的输入界面（可以是简单的文字提示信息），程序运行时提示用 户输入代表信源符号概率的向量；要对用户输入的概率向量进行合法性检查。

二、实验原理

1、二进制Huffman编码的基本原理及算法

(1) 把信源符号集中的所有符号按概率从大到小排队。

(2) 取概率最小的两个符号作为两片叶子合并（缩减）到一个 节点。

(3) 视此节点为新符号，其概率等于被合并（缩减）的两个概率之和，参与概率排队。

(4) 重复(2)(3)两步骤，直至全部符号都被合并（缩减）到根。 

(5) 从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个码字的编码和码长。

2、程序设计的原理

 (1)程序的输入：以一维数组的形式输入要进行huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。

（2）huffman编码具体实现原理：

      1>在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。

2>新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码：

      将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根 节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则）

      然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，

     最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。

3>计算信源熵和平均码长，其比值即为编码密码效率。

n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，

      最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。

P=input('please input a nuber:'); %提示输入界面  if(find(P<0))        disp('The probabilities in huffman can not less than 0!');          P=input('please input a number:')   end   if  abs(sum(P))>1      disp('The sum of the probabilities in huffman can more than 1!');      P=input('please input a number:')   end  [w,k]=Huffman(P); disp('码字'); disp(w) disp('码长'); disp(k)

调用函数：

function [a,b]=Huffman(P)P=sort(P)A=P;B=[];i=1;LL=length(P);L=LL;B(1,:)=P;while(L>2)      i=i+1;      B(i,1)=A(1)+A(2);      C(i-1)=B(i,1);  for j=2:(L-1)     B(i,j)=A(j+1);  end L=L-1; B(i,1:L)=sort(B(i,1:L)); A=B(i,1:L);endK=zeros(i,LL);K(i,1:2)=1;for ll=1:i    for n=1:LLW(ll,n)={'0'};    endendW(i,1)={'1'}; for m=(i-1):-1:1    BB=B(m,1)+B(m,2);     BBB=find(B(m+1,:)==BB);     BBB=BBB(1);             W(m,1:2)=W(m+1,BBB);        K(m,1:2)=K(m+1,BBB);          W(m,1)=strcat(W(m,1),'1');        W(m,2)=strcat(W(m,2),'0');        K(m,1:2)=K(m,1:2)+1;        uu=zeros(1,LL);        uu(1)=BBB;        y=1;         for n=3:(LL+1-m)              fd3=find(B(m,n)==B(m+1,:));              for pp=1:length(fd3)                  kk=isempty(find(uu==fd3(pp)));                 if(kk==1)                     y=y+1;                                        fd3=fd3(pp);                     uu(y)=fd3;                     break;                 end              end                  W(m,n)=W(m+1,fd3);                  K(m,n)=K(m+1,fd3);           endenda=W(1,:);b=K(1,:);

结果显示：

please input a nuber:[0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04]P =    0.0400    0.0500    0.0600    0.0700    0.1000    0.1000    0.1800    0.4000码字    '00011'    '00010'    '0101'    '0100'    '0000'    '011'    '001'    '1'码长     5     5     4     4     4     3     3     1