Huffman编码代码(Huffman_OK.m)

clc
clear all

%取得信源概率矩阵,并进行合法性判断 
clear; 
P=input('请输入信源概率向量P='); %[0.2 0.19 0.18 0.17 0.15 0.10 0.01]
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)='1';%G中的N-1行即最后一行第一个元素赋为1，存到Char中N-1行的N列位置 
Char(N-1,2*N)='0';%G中的N-1行即最后一行第二个元素赋为0，存到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)='1'; %然后在当前行的第一个编码位置末尾填入'1'  
   Char(N-i,N 1:2*N-1)=Char(N-i,1:N-1); %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置  
   Char(N-i,2*N)='0';  %然后在当前行的第二个编码位置末尾填入'0' 
   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);