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

《huffman 哈夫曼编码的实现及应用毕业论文.doc》由会员分享，可在线阅读，更多相关《huffman 哈夫曼编码的实现及应用毕业论文.doc（53页珍藏版）》请在三一办公上搜索。

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

2、.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 在哈夫曼编码中引入堆排序314.2 模拟哈夫曼树的创建32第五章 总结345.1 总结34参考文献35附录3

3、6摘要 哈夫曼编码是一种以哈夫曼树即最优二叉树为核心的编码方式，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损压缩。熵编码法是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是通过统计每一个源字符出现的概率建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这使得编码之后的字符串的平均长度是最短的，从而达到无损压缩数据的目的）。论文全面分析了静态哈夫曼编码和动态哈夫曼编码算法算法，详细介绍了静态哈夫曼编码树和和动态哈夫曼编码树的构造方案，并针对这两种算法，给出了对应

4、的C 语言代码。经运行分析发现，由于在构造静态哈夫曼树时，大量的时间消耗在从元素集合中选取两个最小的元素上。而动态哈夫曼编码算法，虽然克服了前者的缺点，但是算法复杂，而且解压缩时间长。因此，根据字符编码的单值性，对哈夫曼编码做了第二个改进，即不构造哈夫曼树，而是用一个二维数组模拟哈夫曼树的创建过程并得到各字符的编码，这一改进有效地提高了压缩比。关键词：静态哈夫曼编码，压缩，节点，哈夫曼树Abstract Huffman encoding is a huffman tree that is optimal binary tree as the core, often used in data c

5、ompression. 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 example, a file of a symbol) is encoded using a special encoding table.

6、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 longer encoding, which makes the average length of the encoded string i

7、s 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 huffman tree construction program, and for the two algorithms are given corr

8、esponding 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 overcome the shortcomings of the former, but the complexity of the algorithm

9、, 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 creation process, and each character coding, this improvement effectively imp

10、rove the compression ratio. Keywords: Static huffman coding, Compression, Node, huffman tree第一章 绪论1.1 研究目的及意义 从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能少的代码表示尽可能多的图像信息。 图像数字化之后，其数据量非常庞大，例如，一副640480 的彩色图像（24bit/像素），其数据量约为92

11、1.6KB。如果以30 帧/s 的速度播放，则每秒的数据量为6404802430bit=221.12Mbit，需要221 Mbit/s 的通信回路。在多媒体中，海量图像数据的存储和处理是一个难题。如不进行编码压缩处理，一张存650MB 字节的光盘仅能存放24s 左右的640 像素480 像素的图像画面15。总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。仅靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的。另一方面，图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相

12、关性。一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC 和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。因此，图像数据在传输和存储中，数据的压缩是必不可少的1.2 图像压缩编码技术概述1.2.1 图像压缩编码技术分类 图像压缩编码的方法很多，其分类视出发点不同而有差异。从图像压缩技术发展过程来看，可将图

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

14、经解码重建的图像和原始图像没有任何失真，如哈夫曼编码、行程编码、算术编码；有损压缩是指解码重建的图像与原始图像相比有失真，不能精确地复原，但视觉效果基本上相同，是实现高压缩比的编码方法，如预测编码、变换编码。1.2.2 图像压缩编码评价 图像信号在编码和传输中会产生误差，尤其是在熵压缩编码中，产生的误差应在允许的范围内。压缩方法的优劣主要由压缩比和所恢复的图像的质量两个方面来衡量。(1)图像熵 设数字图像像素灰度级集合为d1,d2,dn，其对应的概率分别为p(d1)，p(d2)，,p(dn)。按信息论中信源信息熵的定义，图像的熵定义为： (1) 图像的熵表示像素各个灰度级数据的统计平均值，给出

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

16、 (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 的根结点，其左、右子树均为空；（2）在F 中选取两棵结点的权值最小的树作为左、右子树，构造一棵新的二叉树，置新二叉树的根结点的权值为其左、右子树上

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

19、编码又称自适应哈夫曼编码，它对数据压缩依据的是动态变化的哈夫曼编码树，具体地说，对第i+1个字符的编码是根据原始数据中前i个字符所建立哈夫曼编码树进行的。1.4 本设计所做的主要工作 由上可知，不论是静态哈夫曼编码还是动态哈夫曼编码，其编码和解码过程都相对简单，而如何构造哈夫曼编码树成为问题的关键。论文分别在第2章、第3章中详细介绍了静态哈夫曼编码树和动态哈夫曼编码树的构造方案，并且通过例子演示了构造过程。之后，分别利用这两种编码算法实现了图像的压缩，并且给出了相应的C语言代码。第3章最后一节对两种编码方法作了比较。 另外，由于在构造静态哈夫曼树时，大量的时间消耗在从元素集合中选取两个最小的元

20、素上，因此，在其中引入了堆排序算法，这一改进有效地缩短了压缩时间，第4章第一节对这一改进做了介绍。在静态哈夫曼编码算法中，哈夫曼树的保存占用了大量的空间，而动态哈夫曼编码算法，虽然克服了前者的缺点，但是算法复杂，而且解压缩时间长。因此，在第4章第二节，根据字符编码的单值性，对哈夫曼编码的第二个改进做了介绍，即用一个二维数组模拟哈夫曼树的创建过程并得到字符的前缀编码，这一改进有效地提高了压缩比。第二章 利用静态哈夫曼编码实现图像压缩2.1 静态哈夫曼编码介绍 哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树

21、命名为哈夫曼树. 因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用. 那么,哈夫曼编码是如何来实现数据的压缩和解压缩的呢? 众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码. 以西文为例,例如我们要在计算机当中存储这样的一句话: I am a teacher . 就需要15个字节,也就是120个二进制位的数据来实现. 与这种定长编码不同的是,哈夫曼编码是一种变长编码. 它根据字符出现的概率来构造平均长度

22、最短的编码. 换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长. 当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的. 这就是哈夫曼编码实现数据压缩的基本原理.2.2 静态哈夫曼编码树的构造 哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，该算法的核心部分为哈夫曼编码树（huffman coding tree） 一棵满二叉树。所有可能的输入符号（通常对应为字节）哈夫曼编码树上对应为一个叶节点，在叶节点的位置就是该符号的哈夫曼编码。

23、具体来说，一个符号对应的哈夫曼编码就是从根节点开始，沿左字节点（0）或右子节点（1）前进，一直找到该符号叶节点为止的路径对应的二进制编码。在哈夫曼编码树的基础上，该算法的编码部分输入一系列的符号，根据哈夫曼树对符号进行翻译，以符号在哈夫曼树上的位置作为编码结果。解码部分反之，根据输入的哈夫曼编码，通过查询哈夫曼树翻译回原始符号，即从下到上的编码方法。同其他码词长度可变的编码一样，区别在于不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1） 初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2） 把概率

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

25、树的N 个端点对应N 个信源符号；6）从最后一个概率为1 的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。由于哈夫曼方法构造出来的码不是惟一的，主要有两个原因：一是在两个符号概率相加给两条支路分配“0”和“1”时，这一选择是任意的；二是当两个消息的概率相等时，0，1 分配也是随意的。哈夫曼编码对不同的信源，其编码效率是不同的。7）哈夫曼编码中，没有一个码字是另一个码字的前缀。因此，每个码字惟一可译。2.4 静态哈夫曼编码的算法实例 下面我们以 abcddbb 作为待编码的原始数据串为例，构造静态哈夫曼编码树。首先，我们需要统计

26、出 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组成一棵树，并继续按在信息中出现的几率排序步骤32/71/7a1/7c2/7d4/73/7b2/7将ac的父节点与出现几率次高的d节点组合成新的树，继续按几率进

27、行排序步骤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 的编码恰好是c 的编码的前两位,就造成了b 的编码添加一位就有可能成为c ,这就增加了解压缩的过程中误码的可能. 因为定长编码已经用相同的位数这

28、个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中,要想避免这种情况,我们就必须用一个条件来制约定长编码,这个条件就是要想成为压缩编码,变长编码就必须是前缀编码. 什么是前缀编码呢? 所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀.那么哈夫曼编码是否是前缀编码呢? 观察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.静态哈夫曼编码对图像压缩的实现代码2.3.2 解压缩的实现(1)解压算法思想 压缩文件的文件结构如表1 在文件头部分可利用像素与文件头的偏移量距

31、离位置计算文件头和全表的长度, 从而得到哈夫曼编码树的起始位置。解码过程:(1)指向哈夫曼树的树根。(2)根据当前一位编码为0或1从而指向左或右儿子节点。(3)判断该节点的左,右儿子是否是空(即为0)不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值, 继续解下一个。在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。(2)解压流程图 根据静态哈夫曼算法，解压缩过程为压缩的逆过程。先读取解压缩文件头，获得原文件的长度，字符的编码长度，字符的个数等信息，再构建解压缩树，依次将编码恢复成原始数据。其总体流程图如图2-4所示：图2-4 静态哈夫曼解压缩

32、流程图(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 Example.bmp其运行界面如图2-6所示：图2-6 利用静态哈夫曼编码压缩图像Example.bmp 的运行界面还原之后如图2-7 所示，大小仍

33、为1.35MB，无失真，所用时间为0.621s，其运行界面如图2-8 所示：图2-7 解压缩后的图像图2-8 利用静态哈夫曼编码解压缩图像Example.bmp 的运行界面第三章 利用动态哈夫曼编码实现图像压缩3.1 动态哈夫曼编码的提出 由上一章可知，静态哈夫曼编码需要对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的概率，利用得到的概率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用，第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于传输。如果将这种方法用于网络通信中，两遍扫描势必会引起较大的延时，如果用于压缩中，额外的磁盘访问将会降低该算法的压缩速度

34、。尤其是对于短小的符号流来说，加上哈夫曼编码树的编码结果之后，它在尺寸上可能更大，这使静态哈夫曼编码的应用受到限制。另外，静态编码树的构造方案不能对符号流的局部统计规律变化做出反应，因为它从始至终都使用完全不变的编码树。因此，有人提出了自适应哈夫曼编码方案，即动态哈夫曼编码。这种方案不需事先构造哈夫曼编码树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方案对符号的统计也是动态进行的。这样就在一定程度上解决了静态哈夫曼编码树的不足。严格的说，动态哈夫曼 编码不仅涉及到编码树的构造问题，还与编码、解码过程相关。由于其实用性有了一定的提高，因而应用领域也更加广泛。3.2 动态哈夫曼编码的原理

35、 动态哈夫曼编码不需要事先构造哈夫曼树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方式对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。 在构造动态哈夫曼编码数的过程中，需要遵循两条重要的原则： （1）权重值大的节点，节点编号也较大。 （2）父节点的节点编号总大于子节点的节点编号。 以上两点成为兄弟属性。在每次调整权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点的权重值加一。这样，由于该节点的节点编号已经处于原来所属块中的

36、最大值，因此权重值加一之后兄弟属性依然得到满足。最后由于节点的权重发生变化，必须递归的对节点的父节点进行加一操作。 初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预知各种符号的出现频率。为了对所有符号一致对待，编码书的初始状态只包含一个叶节点，包含符号NYT（Not Yet Transmitted,尚未传送），权重值为0.NYT是一个逸出码（escape code），不同于任何一个将要传送的符号。但有一个尚未包含在编码树种的符号需要被编码时，系统就输出NYT编码，然后跟着符号的原始表达。当解码器出一个NYT之后，它就知道下面的内容暂时不再是哈夫曼编码，而是一个从未在编码数据流

37、中出现过的原始符号。这样任何符号都可以在增加到编码树之前进行传送。 在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号的两个节点，然后将旧的NYT节点由这个子树代替，由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1.因此，下一步将试图对其父节点执行权重值“加一操作”。动态哈夫曼编码的方式与今天哈夫曼编码一致，每次符号编码完成后，也对包含符号的节点权值进行加一操作。 将一个新的符号插入编码树或者输出摸一个已编码符号后，相应的符号的出现次数增加1，继而编码树种各种符号的出现频率发生了改变，不一定符合兄

38、弟属性，按照上述方法进行调整，使其符合要求。3.3 动态哈夫曼编码的算法思想（1）初始化编码树，即建立一棵只有一个空叶结点的哈夫曼树，该结点的符号为NYT（尚未传送），权值始终为0；（2）每读进一个字符，首先检查该字符是否已经在编码树中，如果是，就以静态哈夫曼编码中相同的方式对其进行编码，然后更新编码树；如果不是，先对空叶结点进行编码，再生成一棵子树，其右分支结点为刚读入的字符，其左分支结点为一个新的空叶结点，然后用这棵子树代替原来的空叶结点；（3）将前i 个字符的哈夫曼树调整成一棵i+1 个字符的哈夫曼树，首先，以叶结点ai 为初始的当前结点，重复地将当前结点与具有同样权值的编号最大的结点进

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

40、入符号：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 结点。要对49号结点执行权值“加一操作”，但49号结点不具有所在块中的最大结点编号，因此需要先与50号结点进行交换位置操作。步骤51(47)0NYT

41、(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)2(50)2(49)1(45)1c(46)1a(47)1b(48)0NYT(43)1d(44)新的49号结点权值加一。对51号结点执行权值“

42、加一操作”。步骤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号结点执行权值“加一操作”。步骤105(51)3(50)2(49)1(45)1c(46)1a(47)2d(48)0NYT(43)1b(44)输入符号：b

43、输出编码：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)输入符号：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