赫夫曼编码的原理及改进算法

魏莉

（山西广播电视大学 山西省太原市 030027）

1 引言

在信息大爆炸的今天，压缩技术对于节约存储空间，减少传输时间，节省宝贵的流量，特别有价值。压缩技术的起源可追溯到1948年，美国数学家、信息论的创始人克劳德·香农（Claude Shannon）将热力学的熵引入到信息论中，称为香农信息熵。信息熵编码法是一种无损数据压缩的方法，常见的熵编码技术有赫夫曼编码和算术编码。无损压缩是一种可逆的压缩，它保留了原始的信息，解压可完全恢复原始的信息，不会丢失任何信息。香农和计算机先驱罗伯特·法诺（Robert Fano）于1948年提出香农-法诺编码（Shannon-Fano coding），它是一种基于信息符号集及概率而构建前缀码的技术，用于数据压缩领域。香农通过算术证明了肯定有更好的压缩技术存在，法诺的学生实现了优化压缩的问题。这个学生就是美国数学家大卫·赫夫曼（David A.Huffman），赫夫曼编码是他1952年在麻省理工读书期间发表的论文中提出的，该方法实用高效，并沿用至今[1]。

2 赫夫曼编码

2.1 赫夫曼编码原理

赫夫曼编码是一种可变字长编码（Variable Length Coding,VLC），该方法完全依据字符出现概率来构造异字头的平均长度最短的码字[2,3]。Huffman 编码是一种特殊的最优前缀代码，通常用于无损数据压缩。赫夫曼编码的输出可以看作是编码源符号的变长编码表。该算法从源符号的每个概率(权重)中得出，概率大的符号通常用更少的位表示。赫夫曼编码通过创建最优二叉树(赫夫曼树)来实现，约定左、右分支，分别代表0 和1。

比如有一段文字内容为“钉钉板板钉钉铁钉钉铁板铁板钉铁钉”要网络传输给别人，显然用二进制的字符0、1 来表示。这段文字可以用两位的二进制数据表示即可，00 代表“钉”，10 代表“铁”，01 代表“板”，这样传输的数据编码后为000001010000100000100 11001001000，总长32，对方接收时可以按照2 位一分来译码。 “钉”、“铁”和“板”的出现频率是不相同的，分别为0.5、0.25 和0.25。依据赫夫曼编码的思想，设计“钉”、“铁”和“板”的编码分别为0、10 和11，赫夫曼编码是前缀编码，译码时不会出现二义性。再次编码，001111001000101110110100，共24 个字符。也就是说，数据被压缩了，节约了四分之一的存储和传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。

赫夫曼编码算法流程如图1所示。

第一步：概率统计。赫夫曼编码就是变长编码，发送概率大的编码短，发送概率小的编码长。设定需要编码的字符集为{d1，d2，…dn}，各个字符在电文中出现的次数或频率集合为{w1，w2，…wn}，以d1，d2，…dn作为叶子结点，以w1，w2，…wn作为相应叶子结点的权值来构造一棵赫夫曼树。

图1：赫夫曼编码算法流程图

第二步：构造赫夫曼树。构造赫夫曼树的算法是一种贪心算法。贪心算法是指求解问题的时候，总是选择当前看来最好的。构造赫夫曼树的时候，贪心的地方在于总是选取当前权值最小的两个结点来进行合并生成新结点。根据给定的n 个权值{w1, w2,……wn}，构造n 棵只有根结点的二叉树。在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即赫夫曼树。选择权值最小的两个结点，合并生成父结点，权值为左右子树之和。然后将父结点加入到集合中，继续选择权值最小的两个结点。重复下去。这是个递归的过程。

第三步：压缩编码，赫夫曼树构造完成后标记左支代表0，右支代表1。对每个叶子结点，将从叶子结点到根结点所经过的所有路径分支的0 和1 的组合序列变为该结点对应的字符的编码，这就是赫夫曼编码。

第四步：解码输出，是压缩编码的逆过程，无损压缩的优点在于无信息丢失恢复原貌。

2.2 赫夫曼编码的实现

定义赫夫曼树结点的结构体类型HTNode，结构体中包括结点权值（weight）、双亲（parent）、左孩子（lch）和右孩子（rch）结点。下面是对赫夫曼算法的代码实现，用C 语言对非递归遍历赫夫曼树求解赫夫曼编码，降低了空间和时间复杂度。定义每个结点赫夫曼编码的结构类型Hcode，用字符型数组cd[ ]存放赫夫曼编码。

3 赫夫曼算法的改进

赫夫曼编码是一种对源字符进行可变成长编码，变长编码表通过源字符出现概率得到的，赫夫曼编码的主要思想就是概率高的用短编码，概率小的用长编码。赫夫曼编码的方法就是对赫夫曼树按左0 右1 对Huffman 树的所有分支编号。使用赫夫曼编码有其局限性，每个字符的编码长度必须为整数，源字符集的概率分布若不是2-n的形式，则无法达到熵极限，并且输入字符数受限于字符编码表。

3.1 范式赫夫曼编码

赫夫曼编码是一种高效的数据压缩技术，也存在其不足之处，在数据传输过程中，编码器需要保存或传输赫夫曼编码树，存储空间开销大。1973年牛顿·范勒（Newton Faller）提出一种降低赫夫曼树存储空间的技术，称为范式赫夫曼编码[4]。目前很多流行的压缩方法如GZIB、PNG、JPEG、MPEG 等都是基于此技术。

范式赫夫曼编码的核心思想是在某种约定的情况下，解码器能动态地通过很少的数据便能重构出赫夫曼编码树，不需要任何附加的空间存储数据。一种约定是数字序列属性（numerical sequence property），要求相同长度的字符是连续整数的二进制形式。例如，假设码字长度为3 的最小值为010，那么其他长度为3 的字符必为001、100、110 等。另一个约定：为了降低空间开销，长度为i 第一个字符f(i)能从长度为i-1 的最后一个字符得出，即f(i)= 2(f(i-1)+1)。经过上述的两种约定，解码器即可恢复整棵赫夫曼编码树的结构。

3.2 适应性赫夫曼编码

适应性赫夫曼编码（Adaptive Huffman coding）又称动态赫夫曼编码，是基于静态的赫夫曼编码的技术[5]。静态的赫夫曼编码最大的缺点就是需要事先扫描原始数据，对各字符出现的概率进行统计，利用概率结果创建赫夫曼树，然后再扫描原始数据对其进行编码，并保存编码信息。在网络通信中，这将会引起较大延时，增加空间开销，降低数据压缩的速度。很多情况数据是动态产生，实时变化的，比如车载GPS 定位、气象卫星云图等。

适应性赫夫曼编码不需要事先统计概率构造赫夫曼树，而是随着编码的进行，逐步构造赫夫曼树，对符号的统计是动态进行的。在编码过程中，同一个符号的编码可能发现改变，编码长度也可能变化。初始化编码树的时候，只需要单遍扫描数据，编码树的初始状态只包含一个叶子结点，包含符合NYT（Not Yet Transmitted,尚未传送）。当一个尚未包含在编码树种的符号需要被编码时，系统就输出NYT 编码，然后跟着符号的原始表达。当解码器解码到NYT 之后，可知以下的内容不是赫夫曼编码。

3.3 赫夫曼编码与其他算法结合

波兰计算机科学家Jarek Duda 于2014年提出不对称数字系统（Asymmetric numeral systems,ANS）[6]，是结合了赫夫曼编码速度和算术编码压缩率的一种无损压缩编码，其理论基础源于信息熵理论。熵越高，信息越多，一个事件所包含的信息量和它的概率的倒数呈正相关，平均1 比特信息要1 比特消息存储。该方法同赫夫曼编码相同之处是也依靠概率分布的来实现信息的保存，编码速度与赫夫曼编码同样快，但是压缩率高。

4 结语

赫夫曼编码被广泛应用于数据文件压缩，压缩率通常在20%至90%之间，当源数据各符号出现的概率很不平均的时候，赫夫曼编码的压缩效果更明显。本文结合实例分析了赫夫曼算法的原理，给出了一种改进的非递归的算法实现，降低了算法的时间和时间复杂度；并且介绍了几种基于赫夫曼编码的改进算法，分析了各种算法的原理。目前数据压缩算法众多并在不断改进，很多问题可以根据实际情况结合不同压缩算法，以到达数据准确、高效和安全的传输。