Huffman编解码算法及matlab实现

霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编码算法。其编码思想是将较长的编码码字分配给较小概率的信源输出符号，而将较短的编码码字分配给较大概率的信源输出。文章详细描述了Huffman编解码的算法和matlab实现，程序已经过验证，可以直接使用

function [hl]=huffman（P）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%程序功能：霍夫曼（Huffman）编码的Matlab实现%
%h为返回的编码矩阵，l为信源的平均码长 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
N=length（P）;
Q=P;
Index=zeros（N-1N）;  %初始化Index  
for i=1:N-1  
   [QL]=sort（Q）;  %将P中的元素按升序排序后，元素放到Q中，对应的索引值存到L中
   Index（i:）=[L（1:N-i+1）zeros（1i-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-1N）=‘0‘;%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置
Char（N-12*N）=‘1‘;%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置
%以下从G的倒数第二行开始向前编码
for i=2:N-1  
   Char（N-i1:N-1）=Char（N-i+1N*（find（Index（N-i+1:）==1）） -（N-2）:N*（find（Index（N-i+1:）==1）））; 
   %将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置
   Char（N-iN）=‘0‘; %然后在当前行的第一个编码位置末尾填入‘0‘ 
   Char（N-iN+1:2*N-1）=Char（N-i1:N-1）; %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置 
   Char（N-i2*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+1N*（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  
      h（i1:N）=Char（1N*（find（Index（1:）==i）-1）+1:find（Index（1:）==i）*N）;
      %根据Index第一行索引将Char中第一行编码值还原为输入概率矩阵中的顺序填入Result
      ll（i）=length（find（abs（h（i:））~=32））; 
   end 
  l=sum（P.*ll）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         14  2010-11-19 17:23  huffman编解码\abc.txt

     文件       2106  2010-11-19 19:05  huffman编解码\huffman.m

     文件      53760  2010-11-19 19:48  huffman编解码\Huffman编解码.doc

     文件       1779  2010-11-19 18:24  huffman编解码\main.m

     文件        653  2010-11-26 23:48  huffman编解码\沈笑笑.txt

     文件        283  2010-11-19 19:49  huffman编解码\说明.txt

     目录          0  2011-11-22 11:38  huffman编解码

----------- ---------  ---------- -----  ----

                58595                    7