哈夫曼编码和数据压缩

《算法设计与分析》课程论文

题 目：哈夫曼编码和数据压缩 学 号：201422111920020 学生姓名: 李辉

指导教师： 肖奎

2016年12月17日

第1页

哈夫曼编码和数据压缩

算法的描述

哈夫曼编码在数据的压缩领域有着一席之地，他以简洁简单的方式再出现了这么久的时候人在在被应用虽然哈夫曼编码的效率不是很高，但是他的经典性不容置疑。

在数据通信中，经常需要将传送的文字转换为二进制的字符0和字符1组成的字串，这个过程称为编码。显然我们希望电文编码的长度最短哈夫曼树可以构建使得电文编码的代码长度最短的编码方案。

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。它广泛的应用于数据文件的压缩，它的压缩率通常在20% ~90%之间，哈夫曼编码算法使用字符在文件中出现的频率来表示一个用0.1串表示字符的最优有表示方式。哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个二进制位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

摘要

论文是简单的描述哈夫曼编码和是如何实现数据压缩的，查阅诸多文献，以及老师授课都有说得到哈夫曼编码通过绪论中简单介绍的方法实现。

关键字

哈夫曼编码，最优二叉树，文件压缩。

第2页

哈夫曼编码和数据压缩

哈夫曼编码和文件压缩

哈弗曼树

哈夫曼编码，说道哈夫曼编码就必须提到哈夫曼树是一个特殊的二叉树。哈夫曼树是怎样产生的呢？在许多的应用之中，经常将树的节点赋上某一个特殊意义的数值，称此数值为该节点的权。从树根节点到某节点之间的路径长度与该节点的权值的乘积称为该节点的带权路径长度。树种所有的带权路径长度之和称为该树的带权路径长度，记为WPL。

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、?、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、?，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

哈夫曼编码

哈夫曼编码就是由哈夫曼树而来的，根据哈夫曼树的由来哈夫曼编码的原理也是很简单的。

在数据通讯之中，举一个简单的例子，在一个报文中，需要编码的字符集假如有a,c,c,d，e，f，这五个字符。这五个字符在这一段报文中分别出现了1,5,6,7,14次。这里的每一个字符相当于哈弗曼树的一个叶子节点，这里的字符所出现的次数对应着权值。在数据传送的过程中，无疑我们需要将数据的编码变得最少，这样既节省了空间还提高了传送的效率。而哈弗曼编码正是一种能够将数据压缩的一种算法。原理和构建哈夫曼树相似。原理如下：

由于经过哈夫曼编码法所编码出来的档案是具有唯一码性质的即时码,即各个相异字元所编码出的所元串并不相同,解码时能立即解出。因此，哈夫曼编码法的解码过程是即时且唯一的解码。由此可见，曼编码具有以下明显的特点：

1)编出来的码都是异字头码，保证了码的唯一可译性。

2)由于编码长度可变，因此译码时间较长,使得哈夫曼编码的压缩与还原相当费时。 3)编码长度不统一，硬件实现有难度。

4)由于“0”与“1”的指定是任意的,故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，影响编码效率与数据压缩性能。

由此可见,哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短;而对于出现频率低的,编码长度较长。

生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。 算法步骤如下：

第3页

哈夫曼编码和数据压缩

1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。 4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

这样我们就实现了哈弗曼编码。

哈夫曼编码的具体实现

笔者用java实现哈弗曼编码。这里需要实现的字符是：a,g,f,d,t,o,k,v,j,q，他们所对应的权值也就是出现的次数是：3,5,8,6,7,9,11,12,15,14得到的结果是：

这样就实现了哈夫曼编码，这样压缩的文件能够达到10%~90%不等的压缩效率。 具体的实现方法在在代码文件中。

建立哈夫曼编码表的时间复杂度为O（n）。编码的函数时间复杂度为O（n）。解码函数的时间复杂度为O（n^2）。

这是程序运行的截图。

第4页