哈夫曼编码译码功能的简单实现

许子明

摘 要：哈夫曼树是一种典型的数据结构，由哈夫曼树生成的哈夫曼编码具有不等长的特点，常被用于数据通信的二进制编码中，可以提高存储和处理文本的效率。本文提出一种建立简单的哈夫曼编码、译码系统的方法。在建立完成的哈夫曼树的基础上，生成哈夫曼编码，并对字符串进行编码，对已有的数字编码进行译码。

关键词：哈夫曼树；哈夫曼编码；编码；译码

1 哈夫曼树和哈夫曼编码简介

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree）。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值，则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树的带权路径长度。

对于字符串序列，如果对每个字符在计算机内采用固定长度的二进制位来表示，例如标准ASCII码用7位二进制码表示一个字符，这种编码形式称为固定长度编码。若对于不同的字符采用不同长度的二进制位来表示，那么这种方式称为可变长度编码。可变长度编码的特点是对出现频率不同的字符采用不同长度的编码。对频率高的字符采用短编码，对频率低的字符采用长编码的方式。这样我们就可以减少数据的存储空间，提高存储和传输的效率。而通过哈夫曼树形成的哈夫曼编码是一种有用的可变长度编码。

例：对字符集S={A，B，E，C，D，F}，权值W={3，5，9，11，12，13}建立哈夫曼树。

对应的哈夫曼编码为：A：1100，B：1101，C：00，D：01，E：111，F：10。

2 生成哈夫曼编码原理

首先建立结构体BTNode用来表示哈夫曼树中每一个结点。在结构体BTNode内，建立数组code用于存储该结点的哈夫曼编码；建立变量level记录该结点所在树的层次，初始化为0；建立字符变量cha记录该结点所表示的字符；并实例化建立结构体BTNode *lchild，*rchild表示该节点的左右孩子结点。在生成哈夫曼编码的函数中，利于队列作为辅助。首先建立类型为结构体BTNode的队列，然后使得树的根root结点进入队列。当队列不为空时，将队头元素赋给同类型变量p。然后先判断p的左孩子是否为空，若不为空，则使得p的level变量加1赋给其左孩子结点中的level变量。然后利用for循环和level变量的值进行遍历，将p中的code数组记录的数据依次赋给p的左孩子结点的code数组，继承父节点的编码，最后在编码后加上数字0，生成该孩子结点的哈夫曼编码。然后再将p的左孩子节点加入到队尾。然后类似地，再对p的右孩子结点进行判断与编码，并加入到队尾。最后再删除队头元素，然后再把新的队头元素赋给p，再进行循环操作直到队列为空。

3 编码原理

在哈夫曼编码成功后，当输入由字符集中字符组成的任意字符串时，可以利用已生成的哈夫曼编码进行编码。在编码的函数Find中有字符类参数ch传入进行比较的字符，还有结构体参数BTNode t用来指向树中的某个结点。开始时，将第一个字符与根结点作为参数传入Find函数中，然后在Find函数中将结点中存储的与字符串的字符进行比较，若相同则记录下该结点，并将返回，得到该字符的编码。若不相同，则使用Find函数递归遍历根节点的左右孩子节点，不断递归直到找到需要的字符为止。将所有字符的编码依次存储在队列中，则可以得到该字符串的编码。

4 譯码原理

当输入数字编码时，可以利用已经建成的哈夫曼树进行译码。将数字编码存入队列中，作为参数传入译码函数中。建立结构体BTNode的指针p，初始化指向根节点root。当p指向的结点不为空，且该结点的左右孩子均不为空时，取出数字编码队列中队头的元素进行比较，若为0，则p指向p的左孩子结点；若为1，则p指向p的右孩子结点。然后删除队头元素，再进行新的队头元素的比较，直到p指向哈夫曼树的叶子节点为止，然后返回该叶子节点中存储的字符。或者当数字编码遍历完之后，结束译码函数。最后将译码得到的字符串输出即可。