霍夫曼编码

gtxe

异前置码满足香农第一定理，Huffman编码是目前最流行的一种异前置码。在Huffman编码中，将较长的码字分配给较小可能的信源输出,而将较短的码字分配给较大可能的信源输出。与传统的等长编码方式相比，Huffman编码大幅度提高了压缩的效率，减少了数据的冗余度，可以达到无损压缩的目的。下面给出Huffman编码的基本步骤：

i)       将消息xk按概率降序排列k=1,2,…,Nn；

ii)     为概率最小的两条消息各自分配一个码元；

iii)   将概率最小的两条消息合并成一条新消息，用两者概率之和作为新消息的概率；

iv)    重复以上步骤，直到合并出新消息的概率为1时为止；分配给消息xk的全部码元作为该消息的码字ck。

下面通过英文字母的例子来实现n次扩展离散信源Huffman编码与译码。将英文的26个字母和一个空格共27个符号作为原始信源，查阅资料，找到其通常的概率大小，对原信源、2次扩展信源进行Huffman编码，求得其平均码长和相应的码字，计算效率并进行相互比较。

3.简单例子

下面先以一个简单的例子为例，详细分析本程序实现的过程。给出六个符号的符号集，其概率分布如下：

将此概率分布存入一个数组p，首先判断此概率分布中有无负概率，若有负概率显然给出的概率分布有错。然后判断概率之后之和是否为1，如不为1则不具有完备性，输入仍然不对。其判断代码为：

if length(find(p<0))~=0

error('不是正确的概率分布，存在负概率')

end

if abs(sum(p)-1)>10e-8

error('不是正确的概率分布，概率分布不具有完备性')

end

建立一个n-1行n列的m矩阵（本例是5x6矩阵），专门用于存放每次对概率按从小到大排列后对应元素在上一轮所处的位置，这个m矩阵是后续进行编码时‘0’和‘1’存放位置的参照。m矩阵得生成共需要进行5轮，第一轮对原概率分布进行升序，新概率分布是0.05、0.09、0.1、0.21、0.25、0.3，此时m的第一行为3、4、1、5、6、2。表示0.05上一轮位于第三个位置、0.09上一轮位于第四个位置、以此类推……然后对第一个和第二个概率进行合并形成新的概率分布，并且此时合并后这个元素是位于第一位的。新的概率分布个数少了一个，便在最后添加一个1。此时变为0.14、0.1、0.21、0.25、0.3、1。然后进行第二轮的升序排列变为0.1、0.14、0.21、0.25、0.3、1，此时m的第二行为2、1、3、4、5、0。这儿大家可以发现，上一轮因为合并了的两个元素位于第一个位置，所以在进行编码的时候大家就根据此m矩阵下一行元素1所对应的码字直接赋给上一行前面两个元素作为他们码字的前缀，然后下一行元素2对应的码字赋给上一行第三的列的元素作为它的码字，下一行元素3对应的码字赋给上一行第四的列的元素作为它的码字……这便是后续编码的核心过程。n-1轮循环之后m矩阵最终如下：

表1.m矩阵

3	4	1	5	6	2
2	1	3	4	5	0
2	1	3	4	0	0
2	3	1	0	0	0
2	1	0	0	0	0

代码核心如下：

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

下面便根据m矩阵进行编码，大家按大概率为1小概率为0的原则进行码字分配。先生成一个n-1行n列、并且每个元素的长度为n位的空白矩阵c，并在最后一行第一列最后一位赋0，第二列最后一位赋1，这就相当于Huffman树合并到最后就剩两个概率的时候，并且前一个是小概率为其分码字0，后一个是大概率为其分码字1。

然后查询m矩阵最后一行数字1所在位置，其在最后一行的第二列，于是将此元素的码字作为倒数第二行前两个元素的码字的前缀，并为倒数第二行前两个元素的后面分别添加码字‘0’和‘1’。然后查询m矩阵最后一行数字2所在位置，其在第一列，将其对应码字直接赋给上一行的第三列。

接着查询m矩阵倒数第二行，先查数字1所在位置，在第三列，其对应码字是0，将0赋给上一行前两列作为它们的码字前缀，并在后面分别添加码字‘0’和‘1’。然后查当前行数字2所在位置，直接赋给上一行第三列，查当前行数字3所在位置，赋予上一行第四列…….

如此继续循环，直到遍历到第一行，整个流程如图所示：

最上面一行便是原始概率分布从小到大所对应的码字，编码最重要部分便完成。该部分的核心代码如下：

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)));%下一行元素1对应码字赋给上一行第一列做前缀

c(n-i,n)='0';上一行第一列补充码字‘0’

c(n-i,n+1:2*n-1)=c(n-i,1:n-1);%下一行元素1对应码字赋给上一行第二列做前缀

c(n-i,2*n)='1';%上一行第二列补充码字‘1’

for j=1:i-1%将下一行的码字一次赋予上一行

   c(n-i,(j+1)*n+1j+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

为了让码字与输入的概率一一对应，需要查询m矩阵第一行让对应符号与码字一一相对应，并借助此循环计算各个码字的长度。核心代码如下：

for i=1:n

h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);%符号与码字一一对应

     l1(i)=length(find(abs(h(i,:))~=32));%计算各码字长度

end

最后计算平均码长和信源熵以及编码效率：

l=sum(p.*ll);

hx=sum(p.*(-log2(p)));

xl=hx/l;