目 录
摘 要 .................................................................................................... 3 ABSTRACT .......................................................................................... 4 第一章
绪 论 ..................................................................................... 7
1.1 研究背景 ··········································································· 7 1.2 课题的研究意义 ·································································· 7 1.3哈夫曼编码简介 ··································································· 8
第二章 哈夫曼编码相关技术的研究 ............................................. 10
2.1 压缩技术 ········································································· 10 2.2静态哈夫曼编码实现压缩 ···················································· 11
2.2.1静态哈夫曼编码介绍 .................................................................... 11 2.2.2静态哈夫曼编码树的构造 ............................................................ 11 2.2.3静态哈夫曼编码的具体编码过程 ............................................... 12 2.2.4解压缩的实现 ............................................................................... 12 2.3动态哈夫曼编码实现压缩 ···················································· 13
2.3.1动态哈夫曼编码的提出 ............................................................... 14 2.3.2动态哈夫曼编码的原理 ............................................................... 14 2.3.3 动态哈夫曼编码的算法思想 .................................................... 15 2.3.4解压缩的实现 ............................................................................... 16 2.4 静态哈夫曼编码与动态哈夫曼编码的比较 ······························ 17 2.5 对哈夫曼编码的改进 ·························································· 18
2.5.1在哈夫曼编码中引入堆排序 ....................................................... 18 2.5.2模拟哈夫曼树的创建 ................................................................... 19 2.5 本章小结 ········································································· 21
第三章 哈夫曼编码压缩软件的设计模型 ..................................... 22
3.1设计思想 ·········································································· 22 3.2算法流程图 ······································································ 23 3.2本章小结 ········································································· 26
第四章 哈夫曼编码压缩程序的详细设计 ..................................... 27
4.1.1哈夫曼树基本术语 ....................................................................... 27
4.1 压缩模块设计 ··································································· 27
4.1.2哈夫曼树的构造 ........................................................................... 27 4.1.3压缩实现过程 ............................................................................... 27 4.2 解压缩模块设计 ································································ 32 4.3 程序测试 ········································································· 32 4.4 本章小结 ········································································· 37
结束语 .................................................................................................. 38 致 谢 .................................................................................................. 39 参考文献 .............................................................................................. 40
南京邮电大学2009届本科生毕业设计（论文）
第一章 绪 论
1.1 研究背景
1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
高效编码的主要方法是尽可能地除去信源中的成分，从而减少码率传递最大的信息量。对于有记忆信源来说，首先要去除像素间的相关性，从而达到压缩编码的效率。对于无记忆信源来说，像素间没有相关性，可以利用像素灰度值出现概率的不均等性，采用某种编码方式，从而达到压缩冗余信息的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫做统计编码。
在变长编码中，对出现概率大的信号编以字长短的码字，对出现概率小的信号编以字长长的码字。如果码字长度严格按照所对应信号出现概率大小逆顺序排列，则平均码字长度一定小于其他任何信号顺序排列方法。这是变长编码中的最佳编码定理。
1.2 课题的研究意义
从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。举例来说，图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能少的代码表示尽可能多的图像信息。
图像数字化之后，其数据量非常庞大，例如，一副640×480 的彩色图像（24bit/像素），其数据量约为921.6KB。如果以30 帧/s 的速度播放，则每秒的数据量为640×480×24×30bit=221.12Mbit，需要221 Mbit/s 的通信回路。在多媒体中，海量图像数据的存储和处理是一个难题。如不进行编码压缩处理，一张存650MB 字节的光盘仅能存放24s 左右的640 像素×480 像素的图像画面。总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计
7
南京邮电大学2009届本科生毕业设计（论文）
算机的处理速度增加极大的压力。仅靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的。另一方面，图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC 和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。因此，数据在传输和存储中，数据的压缩是必不可少的。
1.3哈夫曼编码简介
哈夫曼编码是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。它是一种无损压缩编码方法，其基本原理是出现频度较高的数据用较短的代码，出现频度较低的数据用较长的代码。这些代码都是二进制码，且码长是可变的。它的实现主要借助于哈夫曼树。哈夫曼树，又称最优二叉树，是一类带权路径最短的树。所有可能的输入符号在哈夫曼树上对应为一个叶结点，叶结点的位置就是该符号的哈夫曼编码。具体来说，一个符号对应的哈夫曼编码就是从根结点开始，沿左支或右支前进，一直找到该符号所对应的叶结点为止的路径所产生的二进制编码。这种编码是一种无前缀编码，即，任一字符的编码都不会是其他字符编码的前缀，因而数据编码后在存储与传输的过程中不会产生二义性。假设原始数据中含有k 个各不相同的字符a1，a2，，，ak，所出现的频率分别为w1，w2，，，wk，则哈夫曼编码算法[2]如下：
（1）根据给定的n 个权值{w1，w2，??wn}构成n 棵二叉树的集合F={T1，T2，??，Tn}，其中每棵二叉树Ti（i=1，2，??n）中只有一个权值为wi 的根结点，其左、右子树均为空；
（2）在F 中选取两棵结点的权值最小的树作为左、右子树，构造一棵新的二叉树，置新二叉树的根结点的权值为其左、右子树上根结点的权值之和； （3）在F 中删除这两棵树，同时将新得到的二叉树加入到F 中；
（4）重复步骤（2）和（3），直到F 中只含一棵树为止。这棵树便是哈夫曼 树。
8