王俊平　李加彦

摘要：在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。本文从哈夫曼编码的基本原理展开论述，对其具体应用进行分析，对哈夫曼编码中的一些问题进行有益探讨。

关键词：数据结构 数据压缩 编码

0 引言

随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。

1 哈夫曼编码的原理

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法(又称“熵编码法”)，用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的)。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位(不是26)。用普通的表示方法时，每个英文字母均占用一个字节(byte)，即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码(最优前缀码就是平均码长最小的前缀码)。哈夫曼编码的构造很容易，只要构造好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。

2 哈夫曼编码的构造过程

通常我们把数据压缩的过程称为编码，解压缩的过程为解码。电报通信是传送文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。举例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。哈夫曼树就是根据此原理设计出来的一种存储结构。

在电报通讯中，电文是以二进制的0、1序列传送的。在发送端需要将电文中的字符序列转换成二进制0、1序列(即编码)，在接收端又需要把接受的0、1序列转换成对应的字符序列(即译码)。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子对应的自已的编码，就可以完成正确的编码译码工作。

最简单的二进制编码方式是等长编码。例如，假定电文中只使用A、B、C、D、E、F这六种字符，若进行等长编码，它们分别需要3位二进制字符，可依次编码为000、001、010、011、100、101。由常识可知，电文中的每个字符的出现频率一般是不同的。假定在一份电文中，这6个字符的出现频率分别为4、2、6、8、3、2，则电文被编码后的总长度L为:L=3×(4+2+6+8+3+2)=75。

现在讨论能缩短传送电文的总长度，从而缩短传送时间这样一个务实的问题。我们应该想到，若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。

采用不等长编码要避免译码的二义性。假设用0表示字符D，用01表示字符C，则当接收到编码串...01...，并译到编码0时，是立即译出对应的D，还是接着与下一个编码1一起译为对应的字符C，这就产生了二义性。因此，若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是另一个字符的编码的前缀。这种编码叫做前缀编码。显然等长编码是前缀编码。

因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一颗哈夫曼树，此构造过程称为哈夫曼编码。此过程的实现分为在步：①哈夫曼树的建立；②哈夫曼编码的生成；③编码文件的译码。

为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送电文的最短长度，可将每个字符出现频率作为字符结点的权值赋予给结点上，求出此树的最小带权路径长度就等于求出了传送电文的最短长度。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此，求传送电文的最短长度问题就转化为求由字符集中的所有字符作为叶子结点，由字符的出现频率作为其权值所产生的哈夫曼树的问题。

3 总结

随着计算机硬件系统的发展，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如在银行查询存款、通过互联网查看新闻、远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。哈夫曼编码将会在各个领域发挥重要的作用，同时基于哈夫曼编码的研究也将逐步完善。

参考文献：

[1]陈媛.《算法与数据结构》2005年4月第1版清华大学出版社.

[2]严蔚敏，吴伟民.数据结构.(C语言版).1997年4月第1版清华大学出版社.

[3]王学军，方建文.数据结构.2007年8月第1版中国计划出版社.