基于二叉排序树的哈夫曼编码

王防修，周 康

(武汉工业学院数学与计算机学院，湖北武汉430023)

数据量大的信息会给存储器的存储容量、通信信道的带宽，以及计算机的处理速度增加极大的负担。单纯靠增加存储器容量，提高信道容量以及计算机的处理速度等方法来解决这个问题并不是很现实，这时就需要考虑压缩［1］。压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字［2］，而对于不常见的数据则用较长的码字表示，从而使得信息总的码长变短，这样就实现了压缩。

哈夫曼编码［3］作为一种无损［4］数据压缩编码在计算机信息压缩中有着广泛的应用。然而，目前的哈夫曼编码方法一般都是通过对构造好的哈夫曼树进行自底向上的方式实现编码的。该方式不仅与常规思维的从根节点向叶子节点的编码方式相违背;而且在算法的复杂度上，如果定义叶子节点所在层为第1层，其父节点为第2层，依此类推，则处在第n层的节点要被扫描n-1次，所以在程序的运行过程中存在着大量的指针移动，其时间复杂度为O(n2)［5］。

针对以上问题，提出一种新的哈夫曼编码的方式，它不仅可实现从树的根节点向叶子节点的编码，而且程序在运行过程中不需要大量的指针移动。

1 哈夫曼编码的原理

哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据。

1.1 构造哈夫曼树

根据给定的叶子数目及其权重构造哈夫曼树的方法，称为哈夫曼算法，其基本思想如下。

(1)根据给定的 n 个权重{w1，w2，…，wn}构成n棵二叉树的森林 F={T1，T2，…，Tn}，其中每裸二叉树T1中都只有一个权重为w1的根结点，其左右子树均空。

(2)在森林F中选出两棵根结点权重最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权重之和作为新树根的权重。

(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。

这棵树便是哈夫曼树。

1.2 哈夫曼编码

利用哈夫曼树构造的用于通信的二进制前缀编码称为哈夫曼编码。简单的说，哈夫曼编码就是把一些字母或其它符号表示成二进制的方法。这种方法最开始主要是用于电报报文的编码，常用的英文字母例如E，T应该如何编码，不常用的应该如何编码，这样编下来使报文最短。设在报文中出现的字符集为{c1，c2，…，cn}，这些字符在电文中出现的频度为{w1，w2，…，wn}。以这些 wi为权重，构造哈夫曼树，使树中每个外结点对应一个字符，而每个分支结点的左分支表示编码0，右分支表示编码1.令Pi表示从根结点到叶子结点ci的唯一路径，则取路径Pi上0或1的编排作为表示ci的编码，即哈夫曼编码。

哈夫曼编码是一种变长的编码。在编码中，若各码字长度严格按照码字所对应字符出现频度的大小的逆序排列，则编码的平均长度是最小的。这里码字即为字符经哈夫曼编码后得到的编码，其长度是因符号出现的频度而不同，所以说哈夫曼编码是变长的编码。

2 自顶向下的哈夫曼编码算法

本算法采用二叉排序树搜素的方式，从根节点到某个叶子节点进行一次扫描，即可得到该节点的哈夫曼编码。

2.1 数据结构设计

在本结构体中，除了包含节点的被编码的信息域及权重［6］之外，还包含该节点所对应的排序码key，指向其左右孩子节点的指针left和right。具体如下：

typedef struct node*bintree;

struct node

{

char data;

int weight，key;

bintree parent，left，right;

};

2.2 算法描述

本算法从哈夫曼的根节点出发，通过利用二叉排序树，按照二叉排序树搜索叶子节点的方法对树中每个叶子节点进行编码。算法执行过程如下。

(1)根据字符集{c1，c2，…，cn}和相应的权重集{w1，w2，…，wn}建立哈夫曼树。

(2)对建立的哈夫曼树进行中序遍历，得到中序序列P1P2…P2n-1，其中Pi表示第i个节点的指针。

(3)对中序序列P1P2…P2n-1进行顺序编号，使得第i个节点的key值为i。

(4)通过搜索叶子节点的key值得到相应节点的哈夫曼编码，具体操作如下。

a.输入要编码的字符ch，找到该字符 ch所对应的排序码x。

b.从根节点开始，如果x小于根节点中的key，表明应沿根节点的左孩子搜索x，在编码0的同时将当前指针转移到左孩子节点;如果x大于根节点中的key，表明应沿根节点的右孩子搜索x，在编码1的同时将当前指针转移到右孩子节点;x不可能等于根节点中的key，因为要编码的节点只可能是叶子节点。

c.从当前节点开始，如果x小于当前节点中的key，表明应沿当前节点的左孩子搜索x，在编码0的同时将当前指针转移到左孩子节点;如果x大于当前节点中的key，表明应沿当前节点的右孩子搜索x，在编码1的同时将当前指针转移到右孩子节点;当x等于当前节点中的key，则表明字符ch的编码过程结束。

d.重复步骤c，直到x被找到为止，此时x所在的节点一定是叶子节点。从根节点到该叶子节点整个扫描过程中所形成的0，1序列就是字符ch所对应的哈夫曼编码。

编码过程如图1所示。

图1 编码过程描述示例

图1(a)表示一棵已经建好但还未进行编码的二叉树。图1(b)表示一棵编码前中序遍历后的哈夫曼树，通过中序遍历可使哈夫曼树中的每个节点的排序码都得到相应的值。从排序码的角度来看，此时的哈夫曼树就是一棵严格二叉排序树。接下来的三个图表示对字符G进行编码的过程。由于字符G的排序码为5，而5大于根节点的排序码2，故沿着根节点的左孩子进行搜索，从而得到图1(c)的编码过程。由于5小于6，故得到如图1(d)的编码结果。同理，由于5大于4，从而得到如图1(e)的编码结果。由产生的0，1序列可知字符的哈夫曼编码为101。用类似的办法，很容易得到字符B，F，E的哈夫曼编码分别为0，100，00。需要特别指出的是：需要编码的字符一定处在二叉树的叶子节点。

3 哈夫曼编码的算法实现(C语言)

3.1 通过非递归中序遍历哈夫曼树给树中每个节点赋予排序码

void inorder(bintree root，bintree*s)

{bintree p，stack［500］，stack1［500］;

int top=-1，top1=-1，top2=-1，i;

p=root;

do

{while(p!=NULL)

{top++;

stack［top］=p;//节点如栈

p=p-＞left;

}

if(top! =-1)

{p=stack［top］;//节点弹栈

top--;

top1++;

stack1［top1］=p;

p=p-＞right;

}

}while(top! =-1||p!=NULL);

for(i=0;i＜=top1;i++)

{stack1［i］- ＞ key=i+1;//给节点赋予排序码

if(stack1［i］- ＞ left==NULL＆＆stack1［i］- ＞right==NULL)

{top2++;

s［top2］=stack1［i］;

}

}

}

通过中序遍历，可使哈夫曼树从排序码的角度看是一棵严格二叉排序树，这是本文的核心部分。

3.2 编码的核心源代码

void huffman_code(bintree root，int x)

{bintree p，q;

char bm［100］;//存储二进制编码序列

int top=-1，i;

q=NULL;

p=root;//从根节点开始

while(p!=NULL)

{

if(x＜p- ＞key)

{top++;

bm［top］= ＇0＇;//沿左子树编码

p=p-＞left;//沿左子树搜索

}

else if(x＞p-＞key)

{top++;

bm［top］= ＇1＇;//沿右子树编码

p=p-＞right;//沿右子树搜索

}

else break;

}

bm［top+1］= ＇＇;//字符串结束符

puts(bm);//输出编码结果

}

以上程序代码可以根据字符的排序码得到该字符对应的哈夫曼编码。读者很容易通过调用这两个程序模块来实现哈夫码编码。至于哈夫曼的建立，由于很多参考书上都有，这里就不做进一步说明了。

4 软件测试

现有某个信息所含的五种字符的出现次数分别为：a-16，b-7，c-6，d-6，e-5.现要求对这五种字符进行哈夫曼编码。通过调用上文叙述的算法计算，很容易这五种字符的编码表：

a-0，b-100，c-101，d-110，e-111

显然，该信息编码后的码长为1*16+3*(7+6+6+5)=88位。如果用ASCII码表示该信息需要8*40=320位，哈夫曼编码确实实现了压缩。

5 结束语

哈夫曼编码是已经被证明的一种有效的紧致码［7］。在诸如文本、图象、视频压缩及通讯、密码等信息压缩编码标准中，哈夫曼编码被广泛使用［8］。本文为构造哈夫曼编码提供了一种新的生成算法，该算法巧妙地使用二叉排序树，使得算法浅显易懂，非常适合人们对哈夫曼编码原理的理解。

［1］ Vitter JS.Dynamic Huffman Coding［J］.ACM Transactions on Mathematical Software，1989，15(2)：158-167.

［2］ 朱怀宏，吴楠.利用优化哈夫曼编码进行数据压缩的探索［J］.计算机技术与发展，2002，12(5)：1-5.

［3］ Huffman DA.A method for the construction of minimum redundancy codes［J］.Proceeding of the IRE，1952，40(9)：1098-1101.

［4］ 黄伟.图象压缩中的几种编码方法［J］.计算机应用研究，2003，20(8)：67-72.

［5］ 刘帮涛，罗敏.改进的哈夫蔓树和哈夫曼编码构造算法［J］.福建电脑，2008(9)：77-91.

［6］ Larmore LL，Hirschberg DS.A Fast Algorithm for Optimal Length-Limited Huffman Codes［J］.Joural of the Association for Computing Machinery，1990，37(3)：464-473.

［7］ 扬继华，严国萍。基于嵌入式Linux系统的JPEG压缩算法实现［J］.计算机技术与发展，2005，15(3)：7-10.

［8］ 李伟生，王涛.一种不用构造Huffman树的高效Huffman编码算法［J］.中国图象图形学报，2005，10(3)：382-387.