首页 > 学术百科

霍夫曼编码论文

桂林理工大学

----信息科学与工程学院

《数据压缩技术报告》

专业年级： 08级电子信息工程

青铜工艺学号： ----

姓名： ----

指导教师： -----

2011年12月 25日

霍夫曼编码论文

摘要：在现代社会，通信的发展，使得现代社会更加丰富多彩，我们可以随时随地在任何地方了解到世界各地的信息，而这又必须依赖信息的传递。在信息化高度发达的当今社会，我

们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性和保密性和无损性，而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压就时相当有必要的，我们用C++对霍夫曼编码给出简单的算法以实现对文件的压缩和解压。

关键词：霍夫曼编码，压缩，解压，C++

一、霍夫曼编码介绍：

霍夫曼编码(Huffman Coding)是一种熵编码编码压缩方式，霍夫曼编码是可变字长编码(VLC)的一种。霍夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

霍夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后,按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字

霍夫曼编码(Huffman Coding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平

均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，查最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。

二、霍夫曼编码原理：

哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)。那么符号序列S0

S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成00000111100000111001001001110010100000

0001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成0111100011100111011010000000

10010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。我们给出的编码能够保证这一点。

下面给出具体的Huffman编码算法。

(1) 首先统计出每个符号出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。

(2)从左到右把上述频率按从小到大的顺序排列。

(3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。

(4)重复(3)，直到最后得到和为1的根节点。

(5)将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。

上面的例子用Huffman编码的过程如图9.1所示，其中圆圈中的数字是新节点产生的顺序。可见，我们上面给出的编码就是这么得到的。

三、霍夫曼编码步骤：

（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

以下这个简单例子说明了这一过程。

1)．字母A,B,C,D,E已被编码，相应的出现概率如下：

p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11

2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的哈夫曼编码可能由相同的数据产生。

3)．各节点相应的概率如下：

p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13

D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。

如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。

4)．剩下节点的概率如下：

p(AD)=0.29, p(B)=0.51, p(CE)=0.20

AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。

5)．剩下两个节点相应的概率如下：

p(ADCE)=0.49, p(B)=0.51

它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。

6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：

w(A)=001, w(B)=1, w(C)=011, 重烷基苯w班主任工作量(D)=000, w(E)=010

四、霍夫曼编码应用：

假设有一个包含100000个字符的数据文件要压缩存储。各字符在该文件中的出现频度见表1。仅有6种不同字符出现过，字符a出现了45000次。

字符	a	b	c	d	e	f
频度(千次)	45	13	12	16	9	5

可以用很多种方式来表示这样一个压缩文件。理所当然，我们第一个想到的编码方式是固定长度编码：共有6个字符，由于2的3次幂为8，则每个字符可以用3比特的二进制编码来表示：

字符	a	b	c	d	e	f
频度(千次)	45	13	12	16	9	5
固定长度编码	000	001	010	011	可贵的沉默教学设计100	101

这样的编码方式在解压缩的时候不会出现问题：由于每个字符都是用3比特的二进制编码表示，在解析压缩文件时，将每3比特当作一个字符来解析，那么不会发生串码的问题。

金蝉脱壳教学设计采用这种方式的压缩文件其大小是：（45+13+12+16+9+5）*3*1000 = 300000比特。这是最优的压缩方式吗？还有没有别的办法压缩得更小？我们换个思路，对频度高的字符赋予短编码，对频度低的字符赋予较长一些的编码，那么压缩出来的文件的大小有可能小于300000比特。这就是可变长度编码方式。可变长度编码方式既要满足压缩文件长度尽量小的条件，也要克服由“可变长度”所代码的困难：例如a用001表示，b用000表示，当a和b紧接在一起时的编码串为：001000，此时就要求其他字符不能用010，1000，100表示，否则将无法在这串编码中识别出正确的字符。

如果采用霍夫曼编码的话，上述的困难就迎刃而解：

双极电凝镊