浅析基于哈夫曼树与哈夫曼编码的数据压缩

摘 要：哈夫曼编码作为一种最常用的不等长无损压缩编码方法，在数据压缩程序中具有非常重要的应用。本文是基于哈夫曼树与哈弗曼编码的数据压缩算法。

关键词：哈夫曼树 哈弗曼编码 数据压缩 算法

1951年，正在麻省理工学院求学的哈夫曼需要完成一份学期报告，导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。哈夫曼在研究过已有编码后发现，始终无法证明哪个编码是最有效的，因此他很快放弃了这些研究，而进行了新的探索，最后他终于突破了现有编码的算法，发现了基于有序频率二叉树编码，哈夫曼使用了一种自底向上的方法来构建二叉树，这一方法很快被证明是最有效的。

在实际应用中，我们也通常要考虑如何设计一棵二叉树，使得执行路径最短，即算法的效率最高，而这正是哈夫曼所研究的最有效二进制编码，因此最优二叉树又被称为哈夫曼树。

一、哈夫曼树的定义

哈夫曼树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。所谓结点带权路径长度，指的是从根结点到某个结点的路径长度与该结点所带的权值的乘积，而树的带权路径长度则指的是树中所有叶子结点的带权路径长度之和，通常记作：WPL=

假设有n个权值{W1，W2，……，Wn}，试构造有n个叶子结点的二叉树，每个叶子结点拥有一个权值W，则其中带权路径长度WPL最小的二叉树，称为最优二叉树或哈夫曼树。

二、哈夫曼树的建立

根据哈夫曼树的定义，哈夫曼树的构造方法如下：

1.根据给定的n个权值{W1，W2，……，Wn}构成n棵二叉树的集合F={T1，T2，……，Tn}，其中每一棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。

2.在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和。

3.从F中删去这两棵树，同时把新二叉树加入F中。

4.重复2和3，直到F中只有一棵树为止，此树便是哈夫曼树。

从哈夫曼树的构造方法，我们可以推导出构造哈夫曼树的算法实现原理：基于哈夫曼树没有度为1的结点，根据二叉树性质，可推导知一棵有n个叶子的哈夫曼树共有2n-1个结点，我们可定义大小为2n-1的一维数组存储哈夫曼树。这个数组的前n个位置存放的为已知的叶子结点，后（n-1）个位置存放的为动态生成的树内结点。在算法的大循环过程中，就是根据位置i前面的已知结点找出结点权值最小的两个结点，然后根据这两个结点构造出位置i的新的父结点，即一棵新树的根结点。

三、哈夫曼编码

哈夫曼树的一个经典应用就是哈夫曼编码。在数据传输与存储中，经常需要将不同形式的信息转换成二进制字符串，这个转换过程就是编码。在实际应用中，信息的各个字符出现频率是不一样的，有的字符出现频率高，有的字符出现频率低，为了降低所传递信息的编码长度，通常做法是用短的编码来表示高频率字符，用长的编码来表示低频率字符。哈夫曼编码就是这样一种经典编码，哈夫曼编码的优点是任一字符ci的编码不会是另一字符cj（ci≠cj）的编码的前缀，这样电文在译码时不会出现混淆。

哈夫曼编码是一种变长的编码方案，编码过程就根据不同字符的频率（相当于权值）构造出哈夫曼树，然后求叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1。

哈夫曼编码的算法实现所采用的方法是从叶子节点向上遍历到根结点，从哈夫曼树根结点开始，左孩子路径标示为0，右孩子路径标示为1，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。

四、基于哈夫曼树与哈夫曼编码的数据压缩算法

所谓数据压缩，目的在于对需要压缩的数据文件进行可逆编码，使编码的长度小于原数据的长度，通过对哈夫曼编码的研究，我们认识到只要给定字符的概率分布，哈夫曼编码算法能够计算出代码，对于给定概率分布的无前缀代码，产生的编码可以很好的达到数据压缩目标。

在哈夫曼编码算法中，编码过程是从叶子结点出发寻找从叶子到根的路径，而译码过程则是从根结点出发，按照0或1确定访问子结点的路径，直到叶结点，从而求得对应的字符。

文件由若干个字节组成，一个字节有8bits，故有28=256种字节构成形式，对应字节码为0-255。按此256种字节出现频率可构造haffman树进行重新编码，编码后每字节的新编码平均长度将

1.扫描源文件所有数据，并统计文件中每个字符出现的频率。

2.以每个字符与频率组合建立二叉树结点。

3.建立哈夫曼树。

4.将哈夫曼树信息写入输出文件，以备解压缩使用。

5.再度扫描源文件，将源文件的数据生成对应哈夫曼编码，写入到输出文件。对文件做标示，最终完成源文件的压缩。

上面这一算法是根据经典的哈夫曼编码思想引出，压缩时首先扫描源文件，根据源文件中数据出现频率生成字符频率表，据此构造哈夫曼树并生成长短不一的编码，再将哈夫曼编码写入压缩文件，对文件做出标示后完成压缩过程，解压缩时只要逆转编码过程即可。

这样的压缩算法能够以较高压缩率完成文件的压缩，不过分析算法步骤后发现，这一算法有明显缺陷，在于需要对源文件进行两次扫描，第一次扫描目的在于统计并建立频率表，以便解压缩使用，第二次扫描目的在于得到哈夫曼编码。如果源文件较大，扫描两次所引发的低效率不容忽视，同时重复扫描也增加了磁盘访问，再次降低压缩效率。

因此我们需要改进和优化基于哈夫曼编码的压缩算法，分析前述算法，我们找到效率的瓶颈在于哈夫曼树的建立方式，如果我们能够动态建立哈夫曼树，那么对于源文件的扫描就无需两遍，从而带来效率的提高。

那么应当如何构建动态变化的哈夫曼树呢？我们可以考虑从如下角度入手：即动态哈夫曼编码树的建立过程中，第i+1个字符的编码由原始数据中前i个字符所建立的哈夫曼树为依据进行。如何动态建立哈夫曼树，关键在于如何将前i个字符所建立的哈夫曼树调整为前i+1个字符所建立的哈夫曼树，这一关键问题有待进一步研究和思考。

参考文献

[1] 朱怀宏. 吴楠. 夏黎春， 利用优化哈夫曼编码进行数据压缩的探索[J]，微机发展，2002（第05期）

[2] 蔡茂蓉. 姜龙. 丁光辉. 杨文辉， 哈夫曼树的实现及其在文件压缩中的应用[J]， 现代计算机（专业版），2008（第11期）