自适应Huffman编码算法分析及研究

摘要： Huffman编码作为一种高效而简单的可变长编码常用于信源编码。但现有的Huffman编码算法存在效率不高，同时应用受到一些限制，因此，提出一种自适应Huffman编码算法，该算法与其他的Huffman编码相比效率更高，应用范围更广。

Abstract： Huffman coding， as an efficient and simple variable length coding， is used in source coding. But the existing Huffman coding algorithm efficiency is not high， but application is also limited， therefore， this paper proposes an adaptive Huffman coding algorithm， this algorithm with other Huffman encoding compared with high efficiency， wide application range.

关键词： 数据压缩；Huffman编码；自适应Huffman编码

Key words： data compression；Huffman coding；adaptive Huffman coding

中图分类号：TP39 文献标识码：A 文章编号：1006-4311（2012）35-0196-03

0 引言

如何采用有效的数据压缩技术在信息科学领域发挥着重要的作用，Huffman编码在数据压缩技术中得到了广泛的应用，笔者对Huffman编码的原理和存在的不足进行探讨，并在此基础上提出了自适应Huffman编码方法，从而解决Huffman编码的不足。

1 Huffman编码的原理和构造过程

Huffman编码是1952年由Huffman提出的一种比较常用的变长编码方法，其主导思想是根据数据符号发生的概率进行编码。在数据中出现概率越高的符号，相应的码长越短；出现概率越低的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。Huffman编码需对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的频率，由此创建Huffman树并将其有关信息保存起来，以便解压时使用；第二遍则根据所得到的Huffman树对原始数据进行编码，并将编码信息保存起来。创建Huffman树的过程如下：

①根据源数据符号出现的概率，求出各个符号出现的权值｛W1，W2，…Wn｝构成n棵二叉树的集合F={T1，T2…Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子数为空。

②在F中选取两棵根结点的权值最小的树作为左右子树构造一新的二叉树，设置新二叉树的根结点的权值为左、右子树上根结点权值之和。

③在F中删除所选取的两棵子树，同时将构成得到新二叉树加入到F中。

④重复②、③直到F中只包含一个二叉树为止，这棵树便是Huffman树。

以abcddbb为例作为待编码的原始数据符号。首先，统计出a、b、c、d四个字符在原始数据中出现的概率（权重），结果如表1所示。

根据上述Huffman树构造过程，对“abcddbb”原始数据构造的Huffman树的过程如图1～4所示。

从Huffman编码的根结点出发，经右子树、左子树、左子树三步，到达包含字符a的叶结点，获得a字符的二进制编码：100。从根结点出发，经过左子树前进一步，就到达包含字符b的叶结点，获得b字符的二进制编码为：0，类似可得到c字符的二进制编码为：101，d字符的二进制编码为11，abcddbb的编码结果为：1000101111100。

这种Huffman编码算法进行编码时，必须进行两次扫描，第一次扫描统计字符出现的概率（权重），并据此进行构造Huffman树；第二次扫描是按Huffman树的字符进行编码。在存储和传输Huffman编码时，必须先存储和传输Huffman树，在实际应用系统中它有很大的局限性，特别在诸如通信等实时传输、处理的系统中，更不允许这种两次处理过程。因此，为改进该编码算法，提出了自适应Huffman编码方案。

2 自适应Huffman编码原理和构造过程

在叙述自适应Huffman编码之前，必须给每个结点引入两个新属性：结点编号和所属块。结点编号是一个全局唯一值，不同的结点拥有不同的点编号，而所属块是指具有相同权重的一组结点。其中结点编号需要具有以下特征：

①权重越大的结点，结点编号越大。②父结点的编号总是大于子结点的编号。以上两点成为兄弟属性。

自适应Huffman编码的过程主要包括Huffman树初始和Huffman树更新。

①Huffman树的初始化。初始化Huffman树时，由于对字符流进行一次扫描，因此，不能预先知道各字符的概率，为了对所有字符一致对待，Huffman树的初始状态只包含一个叶子结点，该叶子结点的符号为NYT（Not Yet Transmitted，尚未传送），权重为0。NYT是一个逸出码，不同任何一个将要传送的符号。当有一个尚未包含在编号树中的符号需要编码时，系统就输出NYT编码，然后跟着字符的原始表达式；在解码是，当解码器读出NYT时，就知道下面的内容暂不是Huffman编码，而是一个从未在编码数据流中出现过的原始符号。包含NYT结点另一个作用，就是作为新符号插入点。在需要插入一个新符号时，总是先构造一棵新子树，子树包含NYT符号和新符号两个结点，然后将旧NYT的结点由该子树替代。

②Huffman树的更新。Huffman树的更新过程如下：

1）增加输入字符所在叶结点的权重加1。

2）检查Huffman树是否仍满足兄弟特性，若是则保持Huffman树的结构不变，执行4），否则执行3）。

3）当不满足兄弟特性时，要调整Huffman树的结构，具体操作是：与序号高于、权重小于该结点的结点交换字符及权重。若有多个结点满足此条件，则与最右边的结点进行交换；若欲交换的结点是非叶结点，则应将该结点及后代作为一个整体进行交换。

4）根据调整后的Huffman树，按结点指针依次调整各结点的父结点权重。

仍以abcddbb为例作为待编码的原始数据符号为例，结点编号从51向下生成，整个自适应Huffman编码的过程如下：

①初始状态，仅有唯一的NYT结点，该结点点的权重为0，如图5所示。

②包含新NYT结点和字符a结点的子树替换旧的NYT结点，并使51号结点权重加1，输入符号a的编码为1，如图6所示。

③包含新NYT结点和字符b结点的子树替换旧的NYT结点，输入符号b的编码为01，并使51号结点执行权重加1，如图7所示。

④包含新NYT结点和字符c结点的子树替换旧的NYT结点，将要对49号结点权重加1，但49号结点不具有所在块中的最大编号，因此需要先于50号结点进行交换位置操作，如图8所示。

⑤新的50号结点权重加1，51号结点权重加1，如图9所示。

⑥包含新NYT结点和字符d结点的子树替换旧的NYT结点，输入符号d的编码为1001，将要对47号结点权重加1，但47号结点不具有所在块中的最大编号，因此需要先于49号结点进行交换位置操作，如图10所示。

⑦新的49号结点权重加1，51号结点权重加1，如图11所示。

⑧输入符号d的编码为001，将要对对44号结点权重加1，但44号结点不具有所在块中的最大编号，因此需要先于48号结点进行交换位置操作，如图12所示。

⑨新的48号结点权重加1，50号结点权重加1，51号结点权重加1，如图13所示。

⑩输入符号b的编码为001，将要对对44号结点权重加1，但44号结点不具有所在块中的最大编号，因此需要先于47号结点进行交换位置操作，如图14所示。

{11}新的47号结点权重加1，50号结点权重加1，51号结点权重加1，如图15所示。

{12}输入符号b的编码为10，将要对对47号结点权重加1，但47号结点不具有所在块中的最大编号，因此需要先于49号结点进行交换位置操作，如图16所示。

{13}新的49号结点权重加1，51号结点权重加1，如图17所示。

自适应Huffman编码算法，很大程度上压缩了数据在网络中的冗余信息，减少网络传输的信息量，从而能进一步提高通信和网络传输数据的效率。

参考文献：

[1]严蔚敏，吴伟民．数据结构（C语言版）[M]．清华大学出版社，2007．

[2]李伟生，李域，王涛.一种不用建造Huffman树的高效Huffman编码算法[J]．中国图像图形学报，2005，10（3）：382-387．

[3]韩俊英，韩虎．Huffman算法的分析与改进[J]．兰州铁道学院学报（自然科学版），2003，22（3）：120-121．

[4]张风林，刘思峰．一个改进的Huffman数据压缩算法[J]．计算机工程与应用，2007，43（2）：73-74．

[5]文国知．基于C语言的自适应Huffman编码算法分析与实现研究[J]．武汉工业学院学报，2011，30（2）：53-57．