Huffman编码：MATLAB实现与原理

Huffman编码是一种熵编码，其基本思想为对在码元序列中出现频率大的码元给予一个比较短的编码，对出现频率小的码元给予一个比较长的编码。

1、编码过程

编码时，从最小概率的两个符号开始，选其中一个支路为0，另一支路为1。（0和1是选择可互换。当然，编码结果0和1也会相应互换）

再将已编码的两支路的概率合并，并重新排队。

继续从最小概率的两个符号开始，选其中一个支路为0，另一支路为1。

一直循环生成码树直到概率归一。

Huffman编码流程示意图

当两支路概率合并后重新排列时，可能出现几个支路概率相等的情况，使得最终的排序方法也不唯一。因而Huffman编码也是不唯一的，其中码长方差最小的一组，称为最优Huffman码。

2、解码过程

Huffman是需要传输码表的，解码就非常简单了，只需要对照码表翻译。

3、MATLAB编程实现

MATLAB 是自带Huffman编码函数的，无需自行实现：

clc;clear;

symbols = 1:6;%信源符号数

p = [0.4 0.2 0.1 0.15 0.05 0.1];%信源概率分布

x = randsrc(1,1200,[symbols;p]);%依照概率与符号生成1200个符号序列

x_bit = reshape((de2bi(x))',1,3*1200); %转换为二进制信息流

[dict, avglen] = huffmandict(symbols,p);%生成Huffman表并算出平均字长

x_Huffman = huffmanenco(x,dict);%进行Huffman编码

x_1 = huffmandeco(x_Huffman,dict);%进行Huffman解码

Entropy_X = sum(-p.*log2(p));%信源熵

n = Entropy_X/avglen;

disp(['信源Huffman编码平均码长为：',num2str(avglen)])

disp(['信源Huffman编码的编码效率为：',num2str(n*100),'%'])

（以上代码采用的是通信序列，需要对图像进行压缩只需要把序列更换为灰度矩阵数据即可）

自编函数：

%1、获取Huffman编码码表

[table,l] = Huffman_table(p);

%2、编码

x_H = Huffman_enco( x,table );

%3、解码

x_2 = Huffman_deco( x_H,table );

Entropy_X = sum(-p.*log2(p));%信源熵

n = Entropy_X/l;

disp(['(自编函数)信源Huffman编码平均码长为：',num2str(l)])

disp(['（自遍函数）信源Huffman编码的编码效率为：',num2str(n*100),'%'])

function [h,l] = Huffman_table( p )

%Huffman编码码表建立，输入概率向量p;输出编码后的码表和平均码长。

n=length(p);   

q=p;   

m=zeros(n-1,n);   

for i=1:n-1   

   [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)='0';   

c(n-1,2*n)='1';   

for i=2:n-1   

   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)='0';   

   c(n-i,n+1:2*n-1)=c(n-i,1:n-1);   

   c(n-i,2*n)='1';   

   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);   

end

function [data_H] = Huffman_enco( data,table )

%Huffman编码,输入信息流data，码表table;输出编码后的二进制码。

data_H = [];

for i=1:length(data)

     data_H = [data_H table(data(i),:)];

end

data_H = str2num(data_H);

end

function [data_2] = Huffman_deco( data,table )

%Huffman解码,输入信息流data，码表table;输出解码后的二进制码。

x=zeros(1,length(data));

for i=1:length(data)

    for j=1:length(table)

        if data(i)==str2num(table(j,:))

            x(i)=j;

        end

    end

end

data_2 = reshape((de2bi(x))',1,3*1200); %转换为二进制信息流

end