huffman 哈夫曼编码的实现及应用毕业论文

《huffman 哈夫曼编码的实现及应用毕业论文》由会员分享，可在线阅读，更多相关《huffman 哈夫曼编码的实现及应用毕业论文（54页珍藏版）》请在装配图网上搜索。

1、重庆理工大学毕业论文 哈夫曼编码的实现及应用毕 业 设 计（论文）题目 哈夫曼编码的实现 及应用 二级学院 数学与统计学院 专 业 信息与计算科学 班 级 学生姓名 学号 指导教师 职称 时 间 XLIX重庆理工大学毕业论文 哈夫曼编码的实现及应用目录摘要IAbstractII第一章 绪论11.1 研究目的及意义11.2 图像压缩编码技术概述21.2.1 图像压缩编码技术分类21.2.2 图像压缩编码评价21.3 哈夫曼编码简介31.4 本设计所做的主要工作4第二章 利用静态哈夫曼编码实现图像压缩52.1 静态哈夫曼编码介绍52.2 静态哈夫曼编码树的构造62.3 静态哈夫曼编码的具体编码过程

2、62.4 静态哈夫曼编码的算法实例72.3 利用静态哈夫曼编码压缩与还原图像的C语言实现92.3.1 压缩的实现92.3.2 解压缩的实现112.4 图象压缩实例12第三章 利用动态哈夫曼编码实现图像压缩153.1 动态哈夫曼编码的提出153.2 动态哈夫曼编码的原理153.3 动态哈夫曼编码的算法思想163.4 动态哈夫曼编码的编码实例183.5 利用动态哈夫曼编码压缩与还原图像的C语言实现253.5.1 数据结构253.5.2 压缩的实现263.5.3 解压缩的实现273.6 图像压缩实例283.7 静态哈夫曼编码与动态哈夫曼编码的比较29第四章 对哈夫曼编码的改进314.1 在哈夫曼编码

3、中引入堆排序314.2 模拟哈夫曼树的创建32第五章 总结345.1 总结34参考文献35附录36重庆理工大学毕业论文 哈夫曼编码的实现及应用摘要 哈夫曼编码是一种以哈夫曼树即最优二叉树为核心的编码方式，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损压缩。熵编码法是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是通过统计每一个源字符出现的概率建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这使得编码之后的字符串的平均长度是最短的，从而达到无损压缩数据的目的）。

4、论文全面分析了静态哈夫曼编码和动态哈夫曼编码算法算法，详细介绍了静态哈夫曼编码树和和动态哈夫曼编码树的构造方案，并针对这两种算法，给出了对应的C 语言代码。经运行分析发现，由于在构造静态哈夫曼树时，大量的时间消耗在从元素集合中选取两个最小的元素上。而动态哈夫曼编码算法，虽然克服了前者的缺点，但是算法复杂，而且解压缩时间长。因此，根据字符编码的单值性，对哈夫曼编码做了第二个改进，即不构造哈夫曼树，而是用一个二维数组模拟哈夫曼树的创建过程并得到各字符的编码，这一改进有效地提高了压缩比。关键词：静态哈夫曼编码，压缩，节点，哈夫曼树Abstract Huffman encoding is a huff

5、man tree that is optimal binary tree as the core, often used in data compression. In the computer information processing, Huffman coding is a consistent coding method (also known as entropy coding method ) for lossless compression of data. Entropy coding method refers to the source character (for ex

6、ample, a file of a symbol) is encoded using a special encoding table. This coding table is special because it is the statistical probability of occurrence of each source character set (high probability of occurrence of the character using a shorter encoding, on the contrary a low probability use a l

7、onger encoding, which makes the average length of the encoded string is the shortest, so as to achieve lossless compression of data). Is a comprehensive analysis of the static huffman encoding and dynamic huffman encoding algorithm algorithm detailed static huffman coding tree and the dynamic huffma

8、n tree construction program, and for the two algorithms are given corresponding C-language code. he operation analysis found that the construct static huffman tree, a large number of time consumed in the two smallest elements selected from the set of elements. Dynamic huffman coding algorithm overco

9、me the shortcomings of the former, but the complexity of the algorithm, and decompression time. Thus, according to the single value of the character encoding, huffman coding to do a second improvement, do not construct the huffman tree, but with a two-dimensional array of analog huffman tree creatio

10、n process, and each character coding, this improvement effectively improve the compression ratio. Keywords: Static huffman coding, Compression, Node, huffman tree第一章 绪论1.1 研究目的及意义 从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能

11、少的代码表示尽可能多的图像信息。 图像数字化之后，其数据量非常庞大，例如，一副640480 的彩色图像（24bit/像素），其数据量约为921.6KB。如果以30 帧/s 的速度播放，则每秒的数据量为6404802430bit=221.12Mbit，需要221 Mbit/s 的通信回路。在多媒体中，海量图像数据的存储和处理是一个难题。如不进行编码压缩处理，一张存650MB 字节的光盘仅能存放24s 左右的640 像素480 像素的图像画面15。总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。仅靠增加存储器容量，提高信道带宽以及计算机的处理速度

12、等方法来解决这个问题是不现实的。另一方面，图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC 和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。因此，图像数据在传输和存储中，数据的压缩是必不可少的1.2

13、图像压缩编码技术概述1.2.1 图像压缩编码技术分类 图像压缩编码的方法很多，其分类视出发点不同而有差异。从图像压缩技术发展过程来看，可将图像压缩编码分为两代，第一代是指20世纪80年代以前的编码方法，它主要研究有关信息熵、编码方法以及数据压缩比等内容。第二代是指20 世纪80 年代以后的编码方法，它突破了信源编码理论，结合分形、模型基、神经网络、小波变换等数学工具，充分利用了人类视觉系统生理特性和图像信源的各种特性。但由于“第二代”编码技术增加了分析的难度，所以大大增加了实现的复杂性。从当前发展情况来看，它仍处于深入研究的阶段。 根据解压重建后的图像与原始图像之间是否有误差，图像压缩编码分为

14、无损（也成为无失真、无误差、信息保持、可逆压缩）编码和有损（有误差、有失真、不可逆）编码两大类。无损压缩中去掉的仅仅是图像数据中冗余的数据，经解码重建的图像和原始图像没有任何失真，如哈夫曼编码、行程编码、算术编码；有损压缩是指解码重建的图像与原始图像相比有失真，不能精确地复原，但视觉效果基本上相同，是实现高压缩比的编码方法，如预测编码、变换编码。1.2.2 图像压缩编码评价 图像信号在编码和传输中会产生误差，尤其是在熵压缩编码中，产生的误差应在允许的范围内。压缩方法的优劣主要由压缩比和所恢复的图像的质量两个方面来衡量。(1)图像熵 设数字图像像素灰度级集合为d1,d2,dn，其对应的概率分别为

15、p(d1)，p(d2)，,p(dn)。按信息论中信源信息熵的定义，图像的熵定义为： (1) 图像的熵表示像素各个灰度级数据的统计平均值，给出了对输入灰度级集合进行编码时所需的平均位数的下限。(2)平均码字长度 设ai 为数字图像中灰度级di 所对应的码字长度（二进制代码的位数），其相应出现的概率为p(di)，则该数字图像所赋予的平均码字长度为： (2)(3)编码效率 (3) 根据信息论中信源码理论，可以证明在R H 条件下，总可以设计出某种无失真编码方法。当然如果编码结果使R 远大于H，表明这种编码方法效率很低，占用比特数太多。最好的编码结果是使R 等于或接近于H。这种状态的编码方法，成为最佳

16、编码。(4)压缩比 压缩比是指编码前后平均码长之比，如果用n 表示编码前每个字符的平均码长，通常为用二进制码表示时的位数，则压缩比可表示为： (4) 一般来说，压缩比大，则说明被压缩掉的数据量多。一个编码系统要研究的问题是设法减小编码平均长度R，使编码效率尽量趋于1，而冗余度趋于0。1.3 哈夫曼编码简介 哈夫曼编码是根据可变长最佳编码定理，应用哈夫曼算法而产生的一种编码方法。它是一种无损压缩编码方法，其基本原理是出现频度较高的数据用较短的代码，出现频度较低的数据用较长的代码。这些代码都是二进制码，且码长是可变的。它的实现主要借助于哈夫曼树。哈夫曼树，又称最优二叉树，是一类带权路径最短的树。所

17、有可能的输入符号在哈夫曼树上对应为一个叶结点，叶结点的位置就是该符号的哈夫曼编码。具体来说，一个符号对应的哈夫曼编码就是从根结点开始，沿左支或右支前进，一直找到该符号所对应的叶结点为止的路径所产生的二进制编码。这种编码是一种无前缀编码，即，任一字符的编码都不会是其他字符编码的前缀，因而数据编码后在存储与传输的过程中不会产生二义性。假设原始数据中含有k 个各不相同的字符a1，a2，ak，所出现的频率分别为w1，w2，wk，则哈夫曼编码算法2如下：（1） 根据给定的n 个权值w1，w2，wn构成n 棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti（i=1，2，n）中只有一个权值为wi 的根结

18、点，其左、右子树均为空；（2）在F 中选取两棵结点的权值最小的树作为左、右子树，构造一棵新的二叉树，置新二叉树的根结点的权值为其左、右子树上根结点的权值之和；（3） 在F 中删除这两棵树，同时将新得到的二叉树加入到F 中；（4） 重复步骤（2）和（3），直到F 中只含一棵树为止。这棵树便是哈夫曼 树。（5） 将哈夫曼 树的左支标0，右支标1，或者左支标1，右支标0（本文采用前一种形式）。然后将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。 哈夫曼编码有静态和动态两类。静态哈夫曼编码是以每个字符出现的概率为权值构造哈夫曼编码树，字符存在于叶子上，每个字符都有唯一的二进制序列表示，

19、压缩时，只要压入相应的哈夫曼编码即可；解压时，根据取出的哈夫曼编码，从根结点出发，编码为0时走左子树，为1时走右子树，直至叶结点。动态哈夫曼编码又称自适应哈夫曼编码，它对数据压缩依据的是动态变化的哈夫曼编码树，具体地说，对第i+1个字符的编码是根据原始数据中前i个字符所建立哈夫曼编码树进行的。1.4 本设计所做的主要工作 由上可知，不论是静态哈夫曼编码还是动态哈夫曼编码，其编码和解码过程都相对简单，而如何构造哈夫曼编码树成为问题的关键。论文分别在第2章、第3章中详细介绍了静态哈夫曼编码树和动态哈夫曼编码树的构造方案，并且通过例子演示了构造过程。之后，分别利用这两种编码算法实现了图像的压缩，并且

20、给出了相应的C语言代码。第3章最后一节对两种编码方法作了比较。 另外，由于在构造静态哈夫曼树时，大量的时间消耗在从元素集合中选取两个最小的元素上，因此，在其中引入了堆排序算法，这一改进有效地缩短了压缩时间，第4章第一节对这一改进做了介绍。在静态哈夫曼编码算法中，哈夫曼树的保存占用了大量的空间，而动态哈夫曼编码算法，虽然克服了前者的缺点，但是算法复杂，而且解压缩时间长。因此，在第4章第二节，根据字符编码的单值性，对哈夫曼编码的第二个改进做了介绍，即用一个二维数组模拟哈夫曼树的创建过程并得到字符的前缀编码，这一改进有效地提高了压缩比。第二章 利用静态哈夫曼编码实现图像压缩2.1 静态哈夫曼编码介绍

21、 哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树. 因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用. 那么,哈夫曼编码是如何来实现数据的压缩和解压缩的呢? 众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码. 以西文为例,例如我们要在计算机当中存储这样的一句话: I am a teacher . 就

22、需要15个字节,也就是120个二进制位的数据来实现. 与这种定长编码不同的是,哈夫曼编码是一种变长编码. 它根据字符出现的概率来构造平均长度最短的编码. 换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长. 当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的. 这就是哈夫曼编码实现数据压缩的基本原理.2.2 静态哈夫曼编码树的构造 哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，该算法的核心部分为哈夫曼编码树（huffman cod

23、ing tree） 一棵满二叉树。所有可能的输入符号（通常对应为字节）哈夫曼编码树上对应为一个叶节点，在叶节点的位置就是该符号的哈夫曼编码。具体来说，一个符号对应的哈夫曼编码就是从根节点开始，沿左字节点（0）或右子节点（1）前进，一直找到该符号叶节点为止的路径对应的二进制编码。在哈夫曼编码树的基础上，该算法的编码部分输入一系列的符号，根据哈夫曼树对符号进行翻译，以符号在哈夫曼树上的位置作为编码结果。解码部分反之，根据输入的哈夫曼编码，通过查询哈夫曼树翻译回原始符号，即从下到上的编码方法。同其他码词长度可变的编码一样，区别在于不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种

24、称为“编码树”（coding tree）的技术。算法步骤如下：（1） 初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2） 把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3） 重复第2步，直到形成一个符号为止（树），其概率最后等于1。（4） 从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。2.3 静态哈夫曼编码的具体编码过程 哈夫曼编码步骤：1）把信源符号xi(i=1,2, ,N) 按出现概率的值由大到小的顺序排列；2）对两个概率最小的符号分别分配以“0”和“1”，然后把这两个概率相加作为一个新的辅助符号的概率；3）将这

25、个新的辅助符号与其他符号一起重新按概率大小顺序排列；4）跳到第2 步，直到出现概率相加为1 为止；5）用线将符号连接起来，从而得到一个码树，树的N 个端点对应N 个信源符号；6）从最后一个概率为1 的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。由于哈夫曼方法构造出来的码不是惟一的，主要有两个原因：一是在两个符号概率相加给两条支路分配“0”和“1”时，这一选择是任意的；二是当两个消息的概率相等时，0，1 分配也是随意的。哈夫曼编码对不同的信源，其编码效率是不同的。7）哈夫曼编码中，没有一个码字是另一个码字的前缀。因此，每个码字

26、惟一可译。2.4 静态哈夫曼编码的算法实例 下面我们以 abcddbb 作为待编码的原始数据串为例，构造静态哈夫曼编码树。首先，我们需要统计出 a, b, c, d 四个符号分别在原始数据串中的出现频率。统计结果如表 1所示：表1 符号出现频率符号abcd频率1/73/71/72/7然后，按照前面提到的构造方法，经过表 2 的四个步骤，即可获得起基于表 1 频率统计的静态哈夫曼编码树.表2 建立哈夫曼编码树步骤13/7b1/7a1/7c2/7d初始状态，将每个符号看作一颗只有一个叶子节点的字数，按出现几率排序步骤21/7c1/7a2/72/7d3/7b将出现几率最小的a,c组成一棵树，并继续按

27、在信息中出现的几率排序步骤32/71/7a1/7c2/7d4/73/7b2/7将ac的父节点与出现几率次高的d节点组合成新的树，继续按几率进行排序步骤413/7b2/71/7a1/7c2/7d4/7组合最后两个元素完成编码树构造 到此为止，我们建立起了给定符号串的哈夫曼编码树。经过编码a:000,b:1,c:001,d:01，但若a b c d的编码分别为:0 ,10 ,101 ,11 ,我们得到的压缩数据为1010 时,那么在解压缩时就会存在两种翻译的可能,一种为bb ,另一种为ca ,为什么会出现这样的现象呢? 通过观察我们发现,字符b 的编码为10 ,而字符c 的编码为101 ,b 的编

28、码恰好是c 的编码的前两位,就造成了b 的编码添加一位就有可能成为c ,这就增加了解压缩的过程中误码的可能. 因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中,要想避免这种情况,我们就必须用一个条件来制约定长编码,这个条件就是要想成为压缩编码,变长编码就必须是前缀编码. 什么是前缀编码呢? 所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀.那么哈夫曼编码是否是前缀编码呢? 观察a 、b 、c 、d 构成的编码树,可以发现b 之所以成为c 的前缀,是因为在这棵树上,b 成为了c 的父结点,从在哈夫曼树当中,原文

29、档中的数据字符全都分布在这棵哈夫曼树的叶子位置,从而保证了哈夫曼编码当中的任何一个字符的编码都不能是另一个字符编码的前缀.也就是说哈夫曼编码是一种前缀编码,也就保证了解压缩过程当中译码的准确性.2.3 利用静态哈夫曼编码压缩与还原图像的C语言实现2.3.1 压缩的实现(1) 压缩算法思想 由于进行的是无损压缩, 所以要扫描图像的所有像素点,压缩过程分为四步:扫描统计像素出现的概率并按大小排列;建立最优二叉树;哈夫曼编码;保存编码。 经过哈夫曼编码后的图像中的不同像素分别用不同长度二进制编码表示,接下来的工作就是保存重编码后的像素,由于无损压缩中编码前后一幅图像的像素点数是相同的,如果仍然以像素

30、为单位保存图像数据就无法实现压缩功能,能够实现压缩是因为编码前后表示像素的二进制编码的位数有所变化。所以,应该对重编码后的二进制位按位存储。(2) 压缩算法流程图 为提高压缩效率，在静态哈夫曼编码算法中引入了堆排序算法，对于这一改进的详细介绍将在第四章中给出。于是，在静态哈夫曼算法的基础上，根据统计出的概率值，先建堆，再构造编码树，然后实现编码压缩。其编码过程如图2-1所示，其中编码表的生成过程如图2-2所示，对字符的编码过程如图2-3所示：开始结束打开文件生成编码表对字符编码关闭文件图2-1 静态哈夫曼压缩流程图 图2-2 编码表的生成 图2-3 对字符编码(3) 实现代码详见附录：1.静态

31、哈夫曼编码对图像压缩的实现代码2.3.2 解压缩的实现(1)解压算法思想 压缩文件的文件结构如表1 在文件头部分可利用像素与文件头的偏移量距离位置计算文件头和全表的长度, 从而得到哈夫曼编码树的起始位置。解码过程:(1)指向哈夫曼树的树根。(2)根据当前一位编码为0或1从而指向左或右儿子节点。(3)判断该节点的左,右儿子是否是空(即为0)不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值, 继续解下一个。在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。(2)解压流程图 根据静态哈夫曼算法，解压缩过程为压缩的逆过程。先读取解压缩文件头，获得原文

32、件的长度，字符的编码长度，字符的个数等信息，再构建解压缩树，依次将编码恢复成原始数据。其总体流程图如图2-4所示：图2-4 静态哈夫曼解压缩流程图(3) 实现代码详见附录：2.静态哈夫曼编码对图像解压的实现代码2.4 图象压缩实例 有一幅800600的24位位图，名称为“Example.bmp”，大小为1.35MB，如图2-5所示，按照以上算法进行压缩，图像熵约为7.259， 平均码字长度为7.292，编码效率为0.995，压缩比约为1.096，压缩后容量为1.25MB，根据第一章第二节介绍的图像压缩编码评价，以上编码是最佳编码，冗余度为0.005。所用时间为0.371s。图2-5 Examp

33、le.bmp其运行界面如图2-6所示：图2-6 利用静态哈夫曼编码压缩图像Example.bmp 的运行界面还原之后如图2-7 所示，大小仍为1.35MB，无失真，所用时间为0.621s，其运行界面如图2-8 所示：图2-7 解压缩后的图像图2-8 利用静态哈夫曼编码解压缩图像Example.bmp 的运行界面第三章 利用动态哈夫曼编码实现图像压缩3.1 动态哈夫曼编码的提出 由上一章可知，静态哈夫曼编码需要对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的概率，利用得到的概率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用，第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编

34、码信息存储起来，便于传输。如果将这种方法用于网络通信中，两遍扫描势必会引起较大的延时，如果用于压缩中，额外的磁盘访问将会降低该算法的压缩速度。尤其是对于短小的符号流来说，加上哈夫曼编码树的编码结果之后，它在尺寸上可能更大，这使静态哈夫曼编码的应用受到限制。另外，静态编码树的构造方案不能对符号流的局部统计规律变化做出反应，因为它从始至终都使用完全不变的编码树。因此，有人提出了自适应哈夫曼编码方案，即动态哈夫曼编码。这种方案不需事先构造哈夫曼编码树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方案对符号的统计也是动态进行的。这样就在一定程度上解决了静态哈夫曼编码树的不足。严格的说，动态哈夫

35、曼 编码不仅涉及到编码树的构造问题，还与编码、解码过程相关。由于其实用性有了一定的提高，因而应用领域也更加广泛。3.2 动态哈夫曼编码的原理 动态哈夫曼编码不需要事先构造哈夫曼树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方式对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。 在构造动态哈夫曼编码数的过程中，需要遵循两条重要的原则： （1）权重值大的节点，节点编号也较大。 （2）父节点的节点编号总大于子节点的节点编号。 以上两点成为兄弟属性。在每次调整权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时

36、，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点的权重值加一。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性依然得到满足。最后由于节点的权重发生变化，必须递归的对节点的父节点进行加一操作。 初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预知各种符号的出现频率。为了对所有符号一致对待，编码书的初始状态只包含一个叶节点，包含符号NYT（Not Yet Transmitted,尚未传送），权重值为0.NYT是一个逸出码（escape code），不同于任何一个将要传送的符号。但有一个尚未包含在编码树种的符号需要被编码

37、时，系统就输出NYT编码，然后跟着符号的原始表达。当解码器出一个NYT之后，它就知道下面的内容暂时不再是哈夫曼编码，而是一个从未在编码数据流中出现过的原始符号。这样任何符号都可以在增加到编码树之前进行传送。 在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号的两个节点，然后将旧的NYT节点由这个子树代替，由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1.因此，下一步将试图对其父节点执行权重值“加一操作”。动态哈夫曼编码的方式与今天哈夫曼编码一致，每次符号编码完成后，也对包含符号的节点权值进行加一操

38、作。 将一个新的符号插入编码树或者输出摸一个已编码符号后，相应的符号的出现次数增加1，继而编码树种各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。3.3 动态哈夫曼编码的算法思想（1）初始化编码树，即建立一棵只有一个空叶结点的哈夫曼树，该结点的符号为NYT（尚未传送），权值始终为0；（2）每读进一个字符，首先检查该字符是否已经在编码树中，如果是，就以静态哈夫曼编码中相同的方式对其进行编码，然后更新编码树；如果不是，先对空叶结点进行编码，再生成一棵子树，其右分支结点为刚读入的字符，其左分支结点为一个新的空叶结点，然后用这棵子树代替原来的空叶结点；（3）将前i

39、 个字符的哈夫曼树调整成一棵i+1 个字符的哈夫曼树，首先，以叶结点ai 为初始的当前结点，重复地将当前结点与具有同样权值的编号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止；其次，将根到叶结点ai 路径上的所有结点的权值加1，该树就变成了前i+1 个字符的哈夫曼树，并且该二叉树仍是最优二叉树。该算法流程图如图3-1 所示：图3-2 动态哈夫曼编码算法对一个输入符号进行编码并更新编码树的流程图3.4 动态哈夫曼编码的编码实例 下面我们仍以第二章中给出的数据串abcddbb为例，演示动态哈夫曼编码树的构造过程，如表3-1所示。表3-1 数据串abcddbb的动态哈夫曼

40、编码树的构造过程步骤10NYT(51)初始状态，仅有唯一的NYT结点，NYT 结点的权重为0。步骤21(51)1a(50)0NYT(51)输入符号：a输出编码：a使用包含新NYT结点和字符a结点的子树，替换旧的NYT结点。步骤31a(50)2(51)0NYT(47)1b(48)1(49)输入符号：b输出编码：0b使用包含新NYT结点和字符b结点的子树，替换旧的NYT 结点。对51号结点（根结点）执行权值“加一操作”。步骤42(51)1(49)1a(50)1c(46)0NYT(45)1(47)1b(48)输入符号：c输出编码：00c使用包含新NYT结点和字符c结点的子树，替换旧的NYT 结点。要

41、对49号结点执行权值“加一操作”，但49号结点不具有所在块中的最大结点编号，因此需要先与50号结点进行交换位置操作。步骤51(47)0NYT(45)1c(46)1b(48)2(50)1a(49)3(51)新的50号结点权值加一。对51号结点执行权值“加一操作”。步骤63(51)2(50)1(45)1(47)1a(49)1b(48)1c(46)0NYT(43)1a(44)输入符号：d输出编码：100d使用包含新NYT结点和字符d结点的子树，替换旧的NYT 结点。将要对47号结点执行权值“加一操作”，但47号结点不具有所在块中的最大结点编号，因此需要先与49号结点进行交换位置操作。步骤74(51)

42、2(50)2(49)1(45)1c(46)1a(47)1b(48)0NYT(43)1d(44)新的49号结点权值加一。对51号结点执行权值“加一操作”。步骤84(51)2(50)2(49)1(45)1c(46)1a(47)1b(48)0NYT(43)1d(44)输入符号：d输出编码：001将要对44号结点执行权重值“加一操作”，但44号结点不具有所在的块中的最大结点编号，因此需要先与48号结点进行交换位置操作。步骤95(51)3(50)2(49)1(45)1c(46)1a(47)2b(48)0NYT(43)1d(44)新的48号结点权值加一。对50号结点执行权值“加一操作”。对51号结点执行权

43、值“加一操作”。步骤105(51)3(50)2(49)1(45)1c(46)1a(47)2d(48)0NYT(43)1b(44)输入符号：b输出编码：001将要对44号结点执行权重值“加一操作”，但44号结点不具有所在的块中的最大结点编号，因此需要先与47号结点进行交换位置操作。步骤116(51)3(50)2(47)1(45)1c(46)1b(49)2d(48)0NYT(43)1a(44)新的47号结点权值加一。对50号结点执行权值“加一操作”。对51号结点执行权值“加一操作”。步骤125(51)3(50)2(47)1(45)1c(46)1b(49)2d(48)0NYT(43)1a(44)输入

44、符号：b输出编码：10将要对47号结点执行权值“加一操作”，但47号结点不具有所在块中的最大结点编号，因此需要先与49号结点进行交换位置操作。步骤131a(44)0NYT(43)1c(46)2d(48)3b(49)2(47)1(45)4(50)7(51)新的49号结点权值加一。对51号结点执行权值“加一操作”。 通过观察以上步骤，容易发现动态哈夫曼编码的几个特征：(1) 在步骤13 得到的编码树与静态哈夫曼编码树基本相同，除了NYT节点和符号a节点组成的子树替代了静态哈夫曼编码树中的符号a 的叶节点之外；(2) 在每一次输入新的符号之前，编码树都处于完整可用的正常状态；(3) 同一个输入符号，

45、可能产生多种不同的输出。例如三次输入的符号b，产生的输出分别为0b、001 和10；(4) 同样的输出结果，可能由不同的输入产生。例如第二次输入的符号d 与第二次输入的符号b，都产生了001 作为输出结果。这些特征首先说明了动态哈夫曼编码树与静态哈夫曼编码树等同，完全符合哈夫曼树的定义。同时，由于每一个输入符号都对编码树产生了影响，因此解码过程无法从哈夫曼编码数据流的某一个中间位置开始进行，而必须从头至尾逐bit 处理。由于动态哈夫曼编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的NYT 节点的编码树作为初始状态，然后根据哈夫曼编码数据流，对符号进行还

46、原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，哈夫曼树都处于与进行编码时使用的哈夫曼树完全相同的状态，保证了解码的正确性。3.5 利用动态哈夫曼编码压缩与还原图像的C语言实现3.5.1 数据结构typedef struct tree int leafSYMBOL_COUNT ;int next_free_node;struct node unsigned int weight;int parent;int child_is_leaf;int child; nodesNODE_TABLE_COUNT ; TREE; 其中leafSYMBOL_COUNT 指明每

47、个字符在哈夫曼树中叶子结点的位置，它被初始化为-1；next_free_node 指明首次出现的字符插入哈夫曼树中的位置；weight 指明每个结点的权值；parent 指明该结点的父结点位置；child_is_leaf 指明该结点是否是叶子结点，若是则置child_is_leaf = 0；若不是则置child_is_leaf = 1；child指明该结点是叶结点，则叶子上存放字符的值，否则指明该结点左孩子的位置，其右孩子的位置是child+1；NODE_TABLE_COUNT =( SYMBOL_COUNT * 2 ) - 1。结点符号有258 种可能的取值, 0到255 表示真实的字节值，

48、256指文件结束标志，257表示空叶结点，用NYT(not yettransmitted)表示，它有两重含义：其一在编码流中代表其后跟随的8 bit 不再是编码，而是一个新的符号；其二内存中的NYT 结点代表新结点的插入位置。故定义END_OF_STREAM的值为256，定义NYT的值为257，定义SYMBOL_COUNT的值为258。3.5.2 压缩的实现(1) 压缩算法流程图 首先，初始化哈夫曼树，然后，对每一个字符进行两种操作：编码，更新哈夫曼树，当遇到符号END_OF_STREAM时，结束。具体实现过程如图3-3所示：图3-3 动态哈夫曼压缩流程图(2) 代码实现详见附录：3动态哈夫曼

49、编码对图像压缩的实现代码3.5.3 解压缩的实现(1) 解压流程图 首先，初始化哈夫曼树，然后，对每一个字符进行两种操作：解码，更新哈夫曼树，直到符号END_OF_STREAM。具体实现过程如图3-4所示：图3-4 动态哈夫曼解压缩流程图(2) 实现代码详见附录：4动态哈夫曼编码对图像解压的实现代码3.6 图像压缩实例对于第二章压缩的图像，利用上述算法压缩后，大小为999KB，所用时间为0.77s，压缩比为4.11。运行界面如图3-5所示：图3-5 利用动态哈夫曼编码压缩图像Example.bmp的运行界面还原之后大小仍为1.35MB，无失真，所用时间为0.871s，运行界面如图3-6所示：图

50、3-6 利用动态哈夫曼编码解压缩图像Example.bmp的运行界面3.7 静态哈夫曼编码与动态哈夫曼编码的比较 如前所述,静态哈夫曼编码的缺点在于需对原始数据进行两遍扫描。第一遍扫描统计字符出现频率并建树，第二遍扫描根据所建哈夫曼树进行编码。由此，在压缩时，将会降低压缩速度。同时，为保存哈夫曼树以供解压时用，也将浪费一部分存储空间。由于静态建树，其压缩率也有所下降。动态哈夫曼 编码对数据的压缩是依据动态变化的哈夫曼编码树，亦即对第i+1个字符的编码是由原始数据中前i个字符所建立的哈夫曼树确定。压缩和解压子程序具有相同的初始化树，每处理完一个字符，压缩和解压缩使用相同的算法 更新哈夫曼树，不必

51、为解压而保存哈夫曼树的有关信息，从而大大提高了压缩率。但是，由于动态哈夫曼编码算法在解压时采用与压缩时相同的方法建树，增加了解压时间，从而降低了还原速度。而静态哈夫曼编码由于对哈夫曼树进行保存，还原时不必重新建树,节省了还原时间。 下面给出静态哈夫曼编码和动态哈夫曼编码在图像压缩中的比较，如表3-2所示。表3-2 静态哈夫曼编码和动态哈夫曼编码在图像压缩中的比较文件名采用的编码算法压缩前的大小压缩后的大小压缩比压缩时间解压缩时间Example1.bmp(16 色位图)动态哈夫曼234KB40 KB5.850.091s0.06s静态哈夫曼234KB68.6KB3.45 0.05s0.04sExa

52、mple2.bmp(24 位位图)动态哈夫曼1.37MB999kB1.400.77s0.871s静态哈夫曼1.37MB 1.25MB1.0950.97s0.86s 由上表可以看出，当图像容量小时，虽然利用动态哈夫曼 编码算法压缩图像，不用保存哈夫曼 树，从而大大提高了压缩比，但是针对图像的特点，大量的时间消耗在了更新编码树上，这样却延长了压缩时间和解压缩时间；当图像容量大时，一定程度上提高了压缩比，而且缩短了压缩时间，但又延长了解压缩时间。所以在第4 章中将对哈夫曼 编码进行改进，使得这种无损压缩方法更加实用。第四章 对哈夫曼编码的改进4.1 在哈夫曼编码中引入堆排序 堆排序算法（HEAPSO

53、RT）由1991 年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德(Robert WFloyd)和威廉姆斯(JWilliams)在1964 年共同发明。堆排序是一树形选择排序，堆顶元素是堆中的最大(或最小)元素，且堆的每一条路径上的元素都是有序的。堆排序正是利用了堆顶元素最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字变得简单。 堆排序中的堆分为大顶堆和小顶堆，其中大顶堆指根结点(亦称为堆顶)的关键字是堆里所有关键字中最大者的堆。小顶堆指根结点(亦称为堆顶)的关键字是堆里所有关键字中最小者的堆。当排序元素不再变化时，利用堆排序可一次求出所需序列。这时，堆排序的时

54、间复杂度恒为O(nlog(n),不会像其他排序那样有出入，而且空间复杂度为V(n),是最低的。 在哈夫曼编码算法中，为了从R1.n中选出两个频率最小的元素，需要进行两趟循环，每次进行n-1 次比较。事实上，在第二趟的n-1 次比较中，有许多比较可能已经在第一趟循环中做过，但由于前一趟比较时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。而堆排序可通过树形结构保存部分比较结果，可减少比较次数，从而缩短了压缩时间。 在哈夫曼编码算法中引入堆排序思想后，与静态哈夫曼编码、动态哈夫曼编码的比较如表4-1 所示：表4-1 引入堆排序后的哈夫曼编码与静、动态哈夫曼编码的比较文件名采用的编码算

55、法压缩前的大小压缩后的大小压缩时间Example1.bmp(16 位色位图)静态哈夫曼编码234KB68.6KB0.05s动态哈夫曼编码234KB40 KB0.09s加入堆排序后的哈夫曼编码234KB68.6KB0.03sExample2.bmp(24 位位图)静态哈夫曼编码1.37MB1.25MB0.97s动态哈夫曼编码1.37MB999kB0.77s加入堆排序后的哈夫曼编码1.37MB1.25MB0.371s4.2 模拟哈夫曼树的创建 在静态哈夫曼编码算法中，必须保存统计出的结果以便解码时构造相同的哈夫曼树，或者直接保存哈夫曼树本身，这要占用大量的空间，也就意味着压缩效率的下降。在动态哈夫

56、曼编码算法中，虽然克服了前者的缺点，但是算法复杂，而且解压缩耗费时间长，若用于通信，就会引起较大的延时。实际上，我们进行压缩时，所关心的是字符编码的单值性，基于这种压缩思想，没有必要构造哈夫曼树，用一个二维数组就可以模拟哈夫曼树的创建过程并得到各字符的编码。实现思想如下： 先统计每个编码长度Ni (二叉树上的Ni 层) 上对应数据的数目，再分别对Ni 层上的符号以递增顺序分配编码。最底层编码从0 开始， 第Ni 层第一个编码为下一层最后一个编码的左边Ni 位数+ 1 。 例如，有一幅图片Picture.bmp，包含七种颜色，分别为A，B，C，D，E，F，G，其出现概率分别为0.25，0.20，

57、0.18，0.13，0.10，0.09，0.05。按照哈夫曼算法，所得哈夫曼树如图4-1所示：图4-1 Picture.bmp的哈夫曼编码树 根据上述实现思想，字符F，G，C，D，E，A，B的编码分别为0000，0001，0010，0011，010，011，10，11。显然，这组编码不能通过哈夫曼树来建立，但与各个字符的哈夫曼编码相比，其编码长度并没有改变，而且每个字符的编码也不是其他字符编码的前缀，同样可以实现压缩，且不会产生二义性。另外，通过计算图像熵和平均编码长度，由最佳编码定理知，该编码仍为最佳编码。因此，压缩信息中无须保存哈夫曼树，只须保存按层遍历二叉树所得的符号，以及每层编码的个数

58、即可。这就使得在整个压缩、解压缩过程中所需空间比哈夫曼编码少得多，从而提高了压缩比。第五章 总结5.1 总结 哈夫曼编码是数据压缩领域中最著名的编码方式之一。它通过出现概率的不等性，构造变长编码，达到减少文件大小的目的。目前广泛应用的许多其他高效的数据压缩算法（如算术编码，可预测编码等）也是在哈夫曼编码的基础上发展起来的。所以，研究哈夫曼编码，对于深入理解数据结构、程序设计等学科中的相关课题是十分有益的。特别是对动态哈夫曼编码的探索以及对整个哈夫曼算法的改进，尽可能使程序稳定、快速、高效地运行，充分体现了对软件时空需求进行优化和权衡的思想。 本设计从分析静态哈夫曼编码开始，逐步过度到动态哈夫曼编码的实现，最后通过对两者的比较，又对哈夫曼算法提出了一些可行的改进。但也存在一些不足，如动态哈夫曼编码的C 语言实现还不够精练，选取的图像材料说服力不强等。并且在压缩时间和压缩比上不能做到十全十美，总要舍弃一头顾一头的感觉，三者之间的平衡点不知道怎么去找，而且就现有问题自己弄得有点焦头烂额，如果有时间的话以后再对这方面的问题进行详细的研究，算法的改进，我觉得是可以找到一个能兼顾三者优点的