《奇妙的二叉树》PPT课件.ppt

《《奇妙的二叉树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《奇妙的二叉树》PPT课件.ppt（22页珍藏版）》请在三一办公上搜索。

1、奇妙的二叉树：Huffman的贡献,提起 Huffman 这个名字，程序员们至少会联想到二叉树和二进制编码。的确，我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道，压缩=模型+编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有独立性。,举例来说，一个使用 Huffman 编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。因此，我们这一章将首先围绕 Huffman 先生最为重要的贡献 Huffman 编码展开讨论，随后，我们再具体介绍可以和 Huffman

2、联合使用的概率模型。,为什么是二叉树,为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：,b,c,要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：a 00 b 010 c 011

3、d 10 e 11,Shannon-Fano 编码,进入 Huffman 先生构造的神奇二叉树之前，我们先来看一下它的前身，由 Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。,讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息(40 个字符长):cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别：a-16，b-7，c-6，d-6，e-5。,Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：1)将给定符号按照其频率从大到小排

4、序。对上面的例子，应该得到：a 16 b 7 c 6 d 6 e-5,2)将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：a 16 b 7-c 6 d 6 e-5,3)我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。4)分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：,于是我们得到了此信息的编码表：a-00 b-01 c-10 d-110 e 111可以将例子中的信息编码为：cabcedeacacdeddaaabaababaaabbacdebaceada 10 00 01 10 111

5、110 111 00 10 00 10.码长共 91 位。考虑用 ASCII 码表示上述信息需要 8*40=320 位，我们确实实现了数据压缩。,Huffman 编码,Huffman 编码构造二叉树的方法和 Shannon-Fano 正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习 Huffman 编码方法。,1)将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。a(16)b(7)c(6)d(6)e(5)2)在 1)中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和

6、。对上面的例子，我们得到一个新的树林：,3)对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：,根（root）,由此，我们可以建立和 Shannon-Fano 编码略微不同的编码表：a-0 b-100 c-101 d-110 e 111对例子中信息的编码为：cabcedeacacdeddaaabaababaaabbacdebaceada 101 0 100 101 111 110 111 0 101 0 101.码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。在Huffman 编码生成二叉树的步骤中，也经常用概率的大小来代替上

7、面我们用的频率值。,让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：Ea=-log2(16/40)=1.322 Eb=-log2(7/40)=2.515 Ec=-log2(6/40)=2.737 Ed=-log2(6/40)=2.737 Ee=-log2(5/40)=3.000,信息的熵为：,E=Ea*16+Eb*7+Ec*6+Ed*6+Ee*5=86.601也就是说，表示该条信息最少需要 86.601 位。我们看到，Shannon-Fano 编码和 Huffman 编码都已经比较接近该信息的熵值了。同时，我们也看出，无论是 Shannon-Fano 还是

8、 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：,符号 理想位数 S-F 编码 Huffman(熵)需要位数 需要位数-a 1.322 2 1 b 2.515 2 3 c 2.737 2 3 d 2.737 3 3 e 3.000 3 3-总计 86.601 91 88,这就是像 Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因。,最简单，最容易被 Huffman 编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。,为 Huffman 编码选择模型,这种模型的缺点是显而易见的：首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；再次，事实上，即使不将编码树计算在内，对通常含有 0-255 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不偿失。,