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

（5）将哈夫曼 树的左支标0，右支标1，或者左支标1，右支标0（本文采用前一种形式）。然后将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。

哈夫曼编码有静态和动态两类。静态哈夫曼编码是以每个字符出现的概率为权值构造哈夫曼编码树，字符存在于叶子上，每个字符都有唯一的二进制序列表示，压缩时，只要压入相应的哈夫曼编码即可；解压时，根据取出的哈夫曼编码，从根结点出发，编码为0时走左子树，为1时走右子树，直至叶结点。动态哈夫曼编码又称自适应哈夫曼编码，它对数据压缩依据的是动态变化的哈夫曼编码树，具体地说，对第i+1个字符的编码是根据原始数据中前i个字符所建立哈夫曼编码树进行的。

9

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

第二章 哈夫曼编码相关技术的研究

通过上一章节的介绍，对哈夫曼的产生背景和哈夫曼编码本身有了一个简单的了解，但是哈夫曼编码的现有技术是什么样的呢？在这一章节将向大家呈现，介绍现有的关于哈夫曼编码的技术、压缩技术等。

2.1 压缩技术

文件压缩的实现有几种方式，提供的各种工具使你能每次压缩一个文件，或压缩一组文件。一组文件能压缩成单个文件，更易于传送到其它用户，解压缩工具把文件解开。一个流行的共享文件压缩工具称为PKZIP（威斯康辛州Glendale的PKWARE公司），用于CompuServe和其它公告牌软件上压缩文件，可以从大多数公告牌服务上卸下PKZIP。

大多数操作系统，包括DOS、NetWare、Windows NT等现在都包含压缩软件。在NetWare 4.x中，能自动压缩指定文件或整卷上的或指定目录中的所有文件。指定文件属性能被设置以标记你希望系统在它们不用时自动压缩的文件。启动自动压缩系统时要小心，一些应用程序由于文件处在压缩状态而不能正常工作。

文件压缩里两个重要概念是无失真（lossless）和有失真（lossy）：无失真压缩(Lossless Compression）无失真压缩系统假定从已压缩文件中返回所有信息，文件中每一位都是重要的，所以压缩算法精确地压缩和解压文件。

有失真压缩(Lossy Compression）有失真系统假定在压缩和解压过程中允许一定的信息损失。许多高清晰度的图形文件包含的信息如果在压缩阶段丢失了也不会引起变化。例如，如果你以高分辨率扫描彩色图画，但是你的显示器不能显示这种清晰度，你就可以使用有失真压缩方案，因为不会遗漏细节。声音和图象文件也适于用有失真压缩，因为信息损失引起的变化很小，解压播放时可能觉察不出来。

虽然无失真压缩中没有信息损失，但压缩比通常只有2:1，有失真压缩根据被压缩信息的类型提供的压缩比从100:1至200:1，声音和图象信息能很好地压缩，因为它通常包含大量冗余信息。

基本的压缩技术有：

空格压缩(Null Compression) 将一串空格用一个压缩码代替，压缩码后面的数值代表空格的个数。

游长压缩(Run-Length Compression)它是空格压缩技术的扩充，压缩任何4个或更多的重复字符的串。该字符串被一个压缩码、一个重复字符和一个代表重复字符个数的值所取代。

关键字编码(Key-word encoding）创建一张由表示普通字符集的值所组成的

10

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

表。频繁出现的单词如for、the或字符对如sh、th，被表示为一些标记（token），用来保存或传送这些字符。

哈夫曼统计方法(Huffman statistical method）这种压缩技术假定数据中的字符有一个变化分布，换句话说，有些字符的出现次数比其余的多。字符出现越频繁，用于编码的位数就越少。这种编码方案保存在一张表中，在数据传输时，它能被传送到接收方调制解调器使其知道如何译码字符。因为压缩算法是基于软件的，所以实时环境中，存在着额外开销，会引起不少问题。而文件备份、归档过程中的压缩不会有什么问题。使用高性能的系统有助于消除大部分的额外开销和性能问题。另外，压缩消除了文件的可移植性，除非解压缩软件也与文件一起传送。

2.2静态哈夫曼编码实现压缩 2.2.1静态哈夫曼编码介绍

哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树. 因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用.

那么,哈夫曼编码是如何来实现数据的压缩和解压缩的呢?

众所周知,在计算机当中,数据的存储和加工都是以字节作为基本单位的,一个西文字符要通过一个字节来表达,而一个汉字就要用两个字节,我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码. 以西文为例,例如我们要在计算机当中存储这样的一句话: I am a teacher . 就需要15个字节,也就是120个二进制位的数据来实现.

与这种定长编码不同的是,哈夫曼编码是一种变长编码. 它根据字符出现的概率来构造平均长度最短的编码. 换句话说如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长. 当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的. 这就是哈夫曼编码实现数据压缩的基本原理.

2.2.2静态哈夫曼编码树的构造

哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，该算法的核心部分为哈夫曼编码树（huffman coding tree）

11

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

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

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

2.2.3静态哈夫曼编码的具体编码过程

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

2.2.4解压缩的实现

(1)解压算法思想

12