《奇妙的二叉树：huffman的贡献》由会员分享，可在线阅读，更多相关《奇妙的二叉树：huffman的贡献（10页珍藏版）》请在金锄头文库上搜索。
1、奇妙的二叉树：奇妙的二叉树：HuffmanHuffman 的贡献的贡献提起 Huffman 这个名字，程序员们至少会联想到二叉树和二进制编码。的确，我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道，压缩 = 模型 + 编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有独立性。举例来说，一个使用 Huffman 编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。因此，我们这一章将首先围绕 Huffman 先生最为重要的贡献 Huffman 编码展开讨论，随后
2、，我们再具体介绍可以和 Huffman 联合使用的概率模型。为什么是二叉树为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：根(root)0 | 1+-+-+0 | 1 0 | 1+-+-+ +-+-+| | | |a | d e0 | 1+-+-+| |b c要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为 0，右转为 1，则一个字符的编码就是从根走到
3、该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：a - 00 b - 010 c - 011 d - 10 e - 11Shannon-Fano 编码进入 Huffman 先生构造的神奇二叉树之前，我们先来看一下它的前身，由 Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息( 40 个字符长 ):cabcedeacacdeddaaabaababaaabbacdeba
4、ceada五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：a - 16b - 7c - 6d - 6e - 52) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：a - 16b - 7-c - 6d - 6e - 53) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下
5、的二叉树：根(root)0 | 1+-+-+0 | 1 0 | 1+-+-+ +-+-+| | | |a b c |0 | 1+-+-+| |d e于是我们得到了此信息的编码表：a - 00 b - 01 c - 10 d - 110 e - 111可以将例子中的信息编码为：cabcedeacacdeddaaabaababaaabbacdebaceada10 00 01 10 111 110 111 00 10 00 10 .码长共 91 位。考虑用 ASCII 码表示上述信息需要 8 * 40 = 240 位，我们确实实现了数据压缩。Huffman 编码Huffman 编码构造二叉树的方法和
6、 Shannon-Fano 正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习 Huffman 编码方法。1) 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点） 。a(16) b(7) c(6) d(6) e(5)2) 在 1 中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：| (11)a(16) b(7) c(6) +-+-+ | |d e3) 对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有
7、这样的二叉树：根(root)0 | 1+-+-+| 0 | 1| +-+-+| 0 | 1 0 | 1a +-+-+ +-+-+| | | |b c d e 由此，我们可以建立和 Shannon-Fano 编码略微不同的编码表：a - 0 b - 100 c - 101 d - 110 e - 111对例子中信息的编码为：cabcedeacacdeddaaabaababaaabbacdebaceada101 0 100 101 111 110 111 0 101 0 101 .码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。让我们回顾一下熵的知识，使用我们在第二章学到的计
8、算方法，上面的例子中，每个字符的熵为：Ea = - log2(16 / 40) = 1.322Eb = - log2( 7 / 40) = 2.515Ec = - log2( 6 / 40) = 2.737Ed = - log2( 6 / 40) = 2.737Ee = - log2( 5 / 40) = 3.000信息的熵为：E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601也就是说，表示该条信息最少需要 86.601 位。我们看到，Shannon-Fano 编码和 Huffman 编码都已经比较接近该信息的熵值了。同时，我们也看
9、出，无论是 Shannon-Fano 还是 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：符号 理想位数 S-F 编码 Huffman 编码( 熵 ) 需要位数 需要位数-a 1.322 2 1b 2.515 2 3c 2.737 2 3d 2.737 3 3e 3.000 3 3-总 计 86。601 91 88这就是象 Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因。为 Huffman 编码选择模型（附范式 Huffman 编码）最简单，最容易被 Huffman 编码利用的模型是“静态统计模型” ，也就是说在编码前统计
10、要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。这种模型的缺点是显而易见的：首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降） ；再次，事实上，即使不将编码树计算在内，对通常含有 0 - 255 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚
11、至在压缩后反而增大了。所以， “静态统计模型”一般仅作为复杂算法的某一部分出现，在信息的某一局部完成压缩功能。我们很难将其用于独立的压缩系统。有一种有效的“静态统计模型”的替代方案，如果我们要压缩的所有信息具有某些共同的特性，也即在分布上存在着共同的特征，比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。读一遍下面这段话：If Youth，throughout all hi
12、story， had had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that “a child dont know anything.“ - Gadsby by E.V.Wright, 1939.发现什么问题了吗？哦，整段话中竟没有出现一次英文中出现频率最高的字母 e ！真让人惊讶，但没有办法，事先
13、拟定的频率分布总有意外的时候。对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。也就是说，每次编码的不再是 a b c 这样的单个符号，而是 the look flower 这样的单词。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。对基于词的编码方式，需要解决几个技术难点。首先是分词的问题，英文单词可以由词间空格分隔，但中文怎么办呢？其实，有很多中文分词算法可以解决这个问题，本书就不再详细介绍了。王笨笨就曾开发过一个不错的分词模块，但希望通过收取一定报酬的方式提供该模块，如有需要，请和王笨笨 E-Mail 联系。一旦我们将词语分离出来，我们就可以对每个词进行频率统计，然后建立 Huffman 编码树，输出编码时，一个编码将代替一个词语。但要注意，英文和汉语的单词数量都在几万到十几万左右，也就是说，我们的 Huffman 编码树将拥有十几万个叶子节点，这对于一棵树来说太大太大了，系统将无力承担所需要的资源，这怎么办呢？我们可以暂时抛开树结构，采用另一种构造 Huffman 编码的方式范式 Huffman 编码。范式 Huffman 编码(Canonical Huffman Code)的基本思路是：并非只有使用二叉树建立的前缀编码才是 Huffman
