huffmanencode.m

霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编码算法。本文用Matlab语言编程实现了霍夫曼（Huffman）编码,并有详细的word说明

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%程序功能：霍夫曼(Huffman)编码的Matlab实现%
%程序员：  王浩        学号：2005204029   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%取得信源概率矩阵,并进行合法性判断
clear;
P=input('请输入信源概率向量P=');
N=length(P);
for component=1:1:N
    if(P(component)<0)
     error('信源概率不能小于0');
 end
end
if((sum(P)-1)>0.0001)
    error('信源概率之和必须为1');
end
%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码
Q=P
Index=zeros(N-1,N);  %初始化Index  
for i=1:N-1  
   [Q,L]=sort(Q);  %将P中的元素按升序排序后，元素放到Q中，对应的索引值存到L中
   Index(i,:)=[L(1:N-i+1),zeros(1,i-1)];
   G(i,:)=Q;%缩减信源得到的最终矩阵
   %Index为N-1行、N列矩阵，用来记录每行最小两概率叠加后概率排列次序,元素不足的地方补0
   %参考doc sort
   Q=[Q(1)+Q(2),Q(3:N),1]; %将Q中概率最小的两个元素合并，元素不足的地方补1
end
%根据以上建立的Index矩阵，进行回溯，获取信源编码
for i=1:N-1
    Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码
end
%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码
Char(N-1,N)='0';%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置
Char(N-1,2*N)='1';%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置
%以下从G的倒数第二行开始向前编码
for i=2:N-1  
   Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)==1)) -(N-2):N*(find(Index(N-i+1,:)==1))); 
   %将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置
   Char(N-i,N)='0'; %然后在当前行的第一个编码位置末尾填入'0' 
   Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置 
   Char(N-i,2*N)='1';  %然后在当前行的第二个编码位置末尾填入'1'
   for j=1:i-1  
 %内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的
 %第3个位置开始的地方,最后计算到Index的首行为止
      Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)==j+1)-1)+1:N*find(Index(N-i+1,:)==j+1));  
 end  
end  

 %Char中第一行的编码结果就是所需的Huffman 编码输出，通过Index中第一行索引将编
 % 码对应到相应概率的信源符号上。
   for i=1:N  
      Result(i,1:N)=Char(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);
      %根据Index第一行索引将Char中第一行编码值还原为输入概率矩阵中的顺序填入Result
  end  
  %打印编码结果
  String='信源概率及其对应的Huffman编码如下';
  disp(String);
  disp(P);
  disp(Result);