苏州推荐网络公司建网站,做微信公众号直接套用模板,搜索引擎优化策略,怎样在百度做网站打广告提起 Huffman 这个名字#xff0c;程序员们至少会联想到二叉树和二进制编码。的确#xff0c;我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道#xff0c;压缩 模型 编码#xff0c;作为一种压缩方法#xff0c;我们必… 提起 Huffman 这个名字程序员们至少会联想到二叉树和二进制编码。的确我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道压缩 模型 编码作为一种压缩方法我们必须全面考虑其模型和编码两个模块的功效但同时模型和编码两个模块又相互具有独立性。举例来说一个使用 Huffman 编码方法的程序完全可以采用不同的模型来统计字符在信息中出现的概率。因此我们这一章将首先围绕 Huffman 先生最为重要的贡献 —— Huffman 编码展开讨论随后我们再具体介绍可以和 Huffman 联合使用的概率模型。 为什么是二叉树 为什么压缩领域中的编码方法总和二叉树联系在一起呢原因非常简单回忆一下我们介绍过的“前缀编码”为了使用不固定的码长表示单个字符编码必须符合“前缀编码”的要求即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系二叉树是最理想的选择。考察下面这棵二叉树 根(root)0 | 1------------0 | 1 0 | 1---------- -------| | | |a | d e0 | 1----------| |b c 要编码的字符总是出现在树叶上假定从根向树叶行走的过程中左转为0右转为1则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上任何一个字符的路径都不会是另一字符路径的前缀路径符合要求的前缀编码也就构造成功了 a - 00 b - 010 c - 011 d - 10 e - 11 Shannon-Fano 编码 进入 Huffman 先生构造的神奇二叉树之前我们先来看一下它的前身由 Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。 讨论之前我们假定要编码字符的出现概率已经由某一模型统计出来例如对下面这串出现了五种字符的信息( 40 个字符长 ): cabcedeacacdeddaaabaababaaabbacdebaceada 五种字符的出现次数分别a - 16b - 7c - 6d - 6e - 5。 Shannon-Fano 编码的核心仍然是构造二叉树构造的方式非常简单 1) 将给定符号按照其频率从大到小排序。对上面的例子应该得到 a - 16b - 7c - 6d - 6e - 5 2) 将序列分成上下两部分使得上部频率总和尽可能接近下部频率总和。我们有 a - 16b - 7
-----------------c - 6d - 6e - 5 3) 我们把第二步中划分出的上部作为二叉树的左子树记 0下部作为二叉树的右子树记 1。 4) 分别对左右子树重复 2 3 两步直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树 根(root)0 | 1------------0 | 1 0 | 1---------- -------| | | |a b c |0 | 1----------| |d e 于是我们得到了此信息的编码表 a - 00 b - 01 c - 10 d - 110 e - 111 可以将例子中的信息编码为 cabcedeacacdeddaaabaababaaabbacdebaceada 10 00 01 10 111 110 111 00 10 00 10 ...... 码长共 91 位。考虑用 ASCII 码表示上述信息需要 8 * 40 240 位我们确实实现了数据压缩。 Huffman 编码 Huffman 编码构造二叉树的方法和 Shannon-Fano 正好相反不是自上而下而是从树叶到树根生成二叉树。现在我们仍然使用上面的例子来学习 Huffman 编码方法。 1) 将各个符号及其出现频率分别作为不同的小二叉树目前每棵树只有根节点。 a(16) b(7) c(6) d(6) e(5) 2) 在 1 中得到的树林里找出频率值最小的两棵树将他们分别作为左、右子树连成一棵大一些的二叉树该二叉树的频率值为两棵子树频率值之和。对上面的例子我们得到一个新的树林 | (11)a(16) b(7) c(6) ------ | |d e 3) 对上面得到的树林重复 2 的做法直到所有符号都连入树中为止。这一步完成后我们有这样的二叉树 根(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 对例子中信息的编码为 cabcedeacacdeddaaabaababaaabbacdebaceada 101 0 100 101 111 110 111 0 101 0 101 ...... 码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。 让我们回顾一下熵的知识使用我们在第二章学到的计算方法上面的例子中每个字符的熵为 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 还是 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 编码利用的模型是“静态统计模型”也就是说在编码前统计要编码的信息中所有字符的出现频率让后根据统计出的信息建立编码树进行编码。这种模型的缺点是显而易见的首先对数据量较大的信息静态统计要消耗大量的时间其次必须保存统计出的结果以便解码时构造相同的编码树或者直接保存编码树本身而且对于每次静态统计都有不同的结果必须分别予以保存这要消耗大量的空间这意味着压缩效率的下降再次事实上即使不将编码树计算在内对通常含有 0 - 255 字符集的计算机文件来说静态统计模型统计出的频率是字符在整个文件中的出现频率往往反映不出字符在文件中不同局部出现频率的变化情况使用这一频率进行压缩大多数情况下得不到太好压缩效果文件有时甚至在压缩后反而增大了。所以“静态统计模型”一般仅作为复杂算法的某一部分出现在信息的某一局部完成压缩功能。我们很难将其用于独立的压缩系统。 有一种有效的“静态统计模型”的替代方案如果我们要压缩的所有信息具有某些共同的特性也即在分布上存在着共同的特征比如我们要压缩的是普通的英文文本那么字母 a 或者字母 e 的出现频率应当是大致稳定的。使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩不但不用保存多份统计信息而且一般说来对该类文件有着较好的压缩效果。这种方案除了适应性不太强以外偶尔还会有一些尴尬的时候。读一遍下面这段话 If Youththroughout all history had had a champion to stand up for it to show a doubting world that a child can thinkand 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 真让人惊讶但没有办法事先拟定的频率分布总有意外的时候。 对英文或中文文本有一种比较实用的静态模型不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。也就是说每次编码的不再是 a b c 这样的单个符号而是 the look flower 这样的单词。这种压缩方式可以达到相当不错的压缩效果并被广泛地用于全文检索系统。 对基于词的编码方式需要解决几个技术难点。首先是分词的问题英文单词可以由词间空格分隔但中文怎么办呢其实有很多中文分词算法可以解决这个问题本书就不再详细介绍了。王笨笨就曾开发过一个不错的分词模块但希望通过收取一定报酬的方式提供该模块如有需要请和王笨笨 E-Mail 联系。一旦我们将词语分离出来我们就可以对每个词进行频率统计然后建立 Huffman 编码树输出编码时一个编码将代替一个词语。但要注意英文和汉语的单词数量都在几万到十几万左右也就是说我们的 Huffman 编码树将拥有十几万个叶子节点这对于一棵树来说太大太大了系统将无力承担所需要的资源这怎么办呢我们可以暂时抛开树结构采用另一种构造 Huffman 编码的方式——范式 Huffman 编码。 范式 Huffman 编码(Canonical Huffman Code)的基本思路是并非只有使用二叉树建立的前缀编码才是 Huffman 编码只要符合(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做 Huffman 编码。考虑对下面六个单词的编码 符号 出现次数 传统 Huffman 编码 范式 Huffman 编码
------------------------------------------------------------单词1 10 000 000单词2 11 001 001单词3 12 100 010单词4 13 101 011单词5 22 01 10单词6 23 11 11 注意到范式 Huffman 编码的独特之处了吗你无法使用二叉树来建立这组编码但这组编码确实能起到和 Huffman 编码相同的作用。而且范式 Huffman 编码具有一个明显的特点当我们把要编码的符号按照其频率从小到大排列时如果把范式 Huffman 编码本身作为单词的话也呈现出从小到大的字典顺序。 构造范式 Huffman 编码的方法大致是 1) 统计每个要编码符号的频率。 2) 根据这些频率信息求出该符号在传统 Huffman 编码树中的深度也就是表示该符号所需要的位数 - 编码长度。因为我们关心的仅仅是该符号在树中的深度我们完全没有必要构造二叉树仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度具体方法这里就不详述了。 3) 分别统计从最大编码长度 maxlength 到 1 的每个长度对应了多少个符号。根据这一信息从 maxlength 个 0 开始以递增顺序为每个符号分配编码。例如编码长度为 5 的符号有 4 个长度为 3 的有 1 个长度为 2 的有 3 个则分配的编码依次为 00000 00001 00010 00011 001 01 10 11 4) 编码输出压缩信息并保存按照频率顺序排列的符号表然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数。 现在完全可以不依赖任何树结构进行高速解压缩了。而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多。 最后要提到的是Huffman 编码可以采用自适应模型根据已经编码的符号频率决定下一个符号的编码。这时我们无需为解压缩预先保存任何信息整个编码是在压缩和解压缩过程中动态创建的而且自适应编码由于其符号频率是根据信息内容的变化动态得到的更符合符号的局部分布规律因此在压缩效果上比静态模型好许多。但是采用自适应模型必须考虑编码表的动态特性即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说我们很难建立能够随时更新的二叉树使用范式 Huffman 编码是个不错的选择但依然存在不少技术上的难题。幸好如果愿意的话我们可以暂时不考虑自适应模型的 Huffman 编码因为对于自适应模型我们还有许多更好的选择下面几章将要谈到的算术编码、字典编码等更为适合采用自适应模型我们将在其中深入探讨自适应模型的各种实现方法。 转载于:https://www.cnblogs.com/k1988/archive/2010/05/18/2165647.html
