实验十 哈夫曼树

实验十 哈夫曼树

实验目的和要求

  1. 掌握哈夫曼树的特点和性质
  2. 掌握构造哈夫曼树的方法
  3. 掌握产生哈夫曼编码的方法

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 利用哈夫曼树设计并实现一个解压缩程序

实验过程

任务一

设计

常规情况下,一个系统中字符的内部编码是等长的,如西文字符的长度是 8 位(bit),汉字的编码长度是 16 位。在这种情况下,无压缩可言。

然而,如果给各字符的编码不等长,并使高频字符编码长度更短一些,则可实现压缩。压缩的方法可借助于哈夫曼树来实现求解。

首先,将所给出的各字符的个数作为权值来构造一棵哈夫曼树,然后对此哈夫曼树编码就可以得到哈夫曼编码,这些编码就可以作为各字符的新编码。具体求解方法如下:

  1. 以所给出的数据集 {3, 4, 8, 10, 16, 18, 20, 21}所构造的哈夫曼树。
  2. 设根结点的编码为空,然后从根结点开始依次对各结点按如下方法编码:
  • 每个结点的左孩子的编码通过在其父结点的编码后添加二进制 0 而得到,而每个结点的右孩子的编码通过在其父结点的编码后添加二进制 1 而得到。
  1. 新文件的长度。将各叶子结点所对应的编码作为对应字符的新编码可节省存储空间。其中出现个数为 3 的字符的编码为 0000 出现个数为 4 的字符的编码为 0001 等。依照这一方法来编码,可知重新编码的文件的长度为各字符的个数乘以其长度之积的和,也即为哈夫曼树的带权路径长度的值:(3 + 4) x 5 + 8 x 4 + (10 + 16 + 18) x 3 + (20 + 21) x 2 = 281,也就是说,在对文件中的字符按新的编码存储时,100 个字符所占用的位数共有 281 位。如果采用等长方式,则这 8 个字符中的每个字符都需要 3 位,因而共需要 300 位。由此可知,这一不等长编码能节省存储空间。如果字符数目较多,并且其频度有较大的差异,则其压缩程度会更明显。按照这方法,可设计出对文件进行压缩的程序.

根据哈夫曼树的特点,权重越大的叶子距离树根越近.为了压缩文件,可以对文件进行扫描,如果一次扫描一个字节,那么节点的种类最多为 2 的 8 次方,即 256 种,扫描完成后即可统计出各种节点的出现次数.根据统计结果建立哈夫曼树,即可得到按每种字节出现的次数为权重的哈夫曼树。压缩文件的方法就是,利用生成的哈夫曼树,对出现次数更多的字节进行重新编码,用更短的二进制位来替换原先的字节(8 位)。

编码实现

编码实现,通过 C++ 来实现以上分析过程。

测试

图中 9.txt 为源文件,9.txt.compress 为压缩后的文件,9.txt.compress.uncompress 是解压后的文件。可以看出文件被压缩了 0.7MB,解压后的文件的 MD5 值与压缩前的文件相同。所以解压缩的目的均已达到。

压缩/解压效果图

实验收获

通过本次实验掌握了哈夫曼树的特点和性质,掌握了构造哈夫曼树并且生成哈夫曼编码的方法。

在编写解压缩软件的过程对哈夫曼树的结构有了更进一步的了解。

在对压缩结果分析时,我发现对于一些文本文件的压缩效果非常好,而对非文本文件进行测试时发现压缩效果非常小,甚至不压缩。进一步分析这些文件,根据对各种节点出现次数的统计结果发现,这些文件的节点分布非常均匀,各种节点出现次数差异不大,根据哈夫曼树的特点可知,对于该种文件是进行不了很好的压缩的。

由此看来,哈夫曼编码更适合压缩文件中分布差距较大的文件,不同的文件应采用不同的方法来应对才能取得更好的效果。