南京邮电大学2009届本科生毕业设计（论文）

压缩文件的文件结构如表1 在文件头部分可利用像素与文件头的偏移量距离位置计算文件头和全表的长度, 从而得到哈夫曼编码树的起始位置。解码过程:

(1)指向哈夫曼树的树根。

(2)根据当前一位编码为0或1从而指向左或右儿子节点。

(3)判断该节点的左,右儿子是否是空(即为0)不是则向后扫描一个编码,执行上一步,如是则完成一个解码,该叶子节点的数组下标即为像素值, 继续解下一个。在解码过程中需要把按位存储的编码读取出来,这个过程就是按位读取。

(2)解压流程图

根据静态哈夫曼算法，解压缩过程为压缩的逆过程。先读取解压缩文件头，获

得原文件的长度，字符的编码长度，字符的个数等信息，再构建解压缩树，依次将编码恢复成原始数据。其总体流程图如图2-1所示：

图2-1 静态哈夫曼解压缩流程图

2.3动态哈夫曼编码实现压缩

13

南京邮电大学2009届本科生毕业设计（论文）

2.3.1动态哈夫曼编码的提出

由上一章可知，静态哈夫曼编码需要对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的概率，利用得到的概率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用，第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于传输。如果将这种方法用于网络通信中，两遍扫描势必会引起较大的延时，如果用于压缩中，额外的磁盘访问将会降低该算法的压缩速度。尤其是对于短小的符号流来说，加上哈夫曼编码树的编码结果之后，它在尺寸上可能更大，这使静态哈夫曼编码的应用受到限制。另外，静态编码树的构造方案不能对符号流的局部统计规律变化做出反应，因为它从始至终都使用完全不变的编码树。因此，有人提出了自适应哈夫曼编码方案，即动态哈夫曼编码。这种方案不需事先构造哈夫曼编码树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方案对符号的统计也是动态进行的。这样就在一定程度上解决了静态哈夫曼编码树的不足。严格的说，动态哈夫曼 编码不仅涉及到编码树的构造问题，还与编码、解码过程相关。由于其实用性有了一定的提高，因而应用领域也更加广泛。

2.3.2动态哈夫曼编码的原理

动态哈夫曼编码不需要事先构造哈夫曼树，而是随着编码的进行，逐步构造哈夫曼树。同时，这种编码方式对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。

在构造动态哈夫曼编码数的过程中，需要遵循两条重要的原则： （1）权重值大的节点，节点编号也较大。 （2）父节点的节点编号总大于子节点的节点编号。

以上两点成为兄弟属性。在每次调整权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点的权重值加一。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性依然得到满足。最后由于节点的权重发生变化，必须递归的对节点的父节点进行加一操作。

初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预知各种符号的出现频率。为了对所有符号一致对待，编码书的初始状态只包含一个叶节点，包含符号NYT（Not Yet Transmitted,尚未传送），权重值为0.NYT

14

南京邮电大学2009届本科生毕业设计（论文）

是一个逸出码（escape code），不同于任何一个将要传送的符号。但有一个尚未包含在编码树种的符号需要被编码时，系统就输出NYT编码，然后跟着符号的原始表达。当解码器出一个NYT之后，它就知道下面的内容暂时不再是哈夫曼编码，而是一个从未在编码数据流中出现过的原始符号。这样任何符号都可以在增加到编码树之前进行传送。

在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号的两个节点，然后将旧的NYT节点由这个子树代替，由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1.因此，下一步将试图对其父节点执行权重值“加一操作”。

动态哈夫曼编码的方式与今天哈夫曼编码一致，每次符号编码完成后，也对包含符号的节点权值进行加一操作。

将一个新的符号插入编码树或者输出摸一个已编码符号后，相应的符号的出现次数增加1，继而编码树种各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。

2.3.3 动态哈夫曼编码的算法思想

（1）初始化编码树，即建立一棵只有一个空叶结点的哈夫曼树，该结点的 符号为NYT（尚未传送），权值始终为0；

（2）每读进一个字符，首先检查该字符是否已经在编码树中，如果是，就以

静态哈夫曼编码中相同的方式对其进行编码，然后更新编码树；如果不是，先对空叶结点进行编码，再生成一棵子树，其右分支结点为刚读入的字符，其左分支结点为一个新的空叶结点，然后用这棵子树代替原来的空叶结点；

（3）将前i 个字符的哈夫曼树调整成一棵i+1 个字符的哈夫曼树，首先， 以叶结点ai 为初始的当前结点，重复地将当前结点与具有同样权值的编号最大的结点进行交换，并使得后者的父结点成为新的当前结点，直到遇到根结点为止；其次，将根到叶结点ai 路径上的所有结点的权值加1，该树就变成了前i+1 个字符的哈夫曼树，并且该二叉树仍是最优二叉树。该算法流程图如图2-2所示：

15

南京邮电大学2009届本科生毕业设计（论文）

图2-2 动态哈夫曼编码算法对一个输入符号进行编码并更新编码树流程图

2.3.4解压缩的实现

首先，初始化哈夫曼树，然后，对每一个字符进行两种操作：解码，更新哈夫曼树，直到符号END_OF_STREAM。具体实现过程如图2-3所示：

16