📄 chapter3.htm
字号:
<html><head><meta http-equiv="Content-Type"content="text/html; charset=gb_2312-80"><meta name="GENERATOR" content="Microsoft FrontPage Express 2.0"><title>笨笨数据压缩教程</title></head><body bgcolor="#FFFFFF"><p align="right"><a href="../../../index.html">返回断章取义堂</a> <a href="../../index.html">返回咏刚的家</a></p><p style="background-color:#AAEEFF;font-size:14px;color:#0000AA">《笨笨数据压缩教程》是我在1998年因工作需要研究压缩算法时写的文章（算是一种工作笔记吧，其中难免有许多疏漏），1999年初随着项目变迁，就把压缩技术的研究暂时搁置了。从那以后，一是工作太忙，二是自己懒惰，总之是没能把半部压缩教程补全。非常对不住大家。——王咏刚，2003年3月</p><p><img src="benben.jpg"alt="笨笨数据压缩教程(Benben's Data Compression Guide)"width="370" height="129"></p><h2>第三章 奇妙的二叉树：Huffman的贡献</h2><div align="right"><address> <a href="Chapter2.htm">第二章</a> <a href="Chapter4.htm">第四章</a></address></div><p>提起 Huffman这个名字，程序员们至少会联想到二叉树和二进制编码。的确，我们总以Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道，压缩= 模型 +编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有独立性。举例来说，一个使用Huffman 编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。因此，我们这一章将首先围绕Huffman 先生最为重要的贡献 —— Huffman编码展开讨论，随后，我们再具体介绍可以和Huffman 联合使用的概率模型。</p><p><strong>为什么是二叉树</strong></p><p>为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：</p><pre> 根(root) 0 | 1 +------+------+ 0 | 1 0 | 1 +-----+-----+ +---+----+ | | | | a | d e 0 | 1 +-----+-----+ | | b c</pre><p>要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：</p><pre>a - 00 b - 010 c - 011 d - 10 e - 11</pre><p><strong>Shannon-Fano 编码</strong></p><p>进入 Huffman先生构造的神奇二叉树之前，我们先来看一下它的前身，由Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。</p><p>讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息(40 个字符长 ):</p><pre>cabcedeacacdeddaaabaababaaabbacdebaceada</pre><p>五种字符的出现次数分别：a - 16，b - 7，c - 6，d- 6，e - 5。</p><p>Shannon-Fano编码的核心仍然是构造二叉树，构造的方式非常简单：</p><p>1)将给定符号按照其频率从大到小排序。对上面的例子，应该得到：</p><pre> a - 16 b - 7 c - 6 d - 6 e - 5</pre><p>2)将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：</p><pre> a - 16 b - 7----------------- c - 6 d - 6 e - 5</pre><p>3)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记 1。</p><p>4) 分别对左右子树重复 2 3两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：</p><pre> 根(root) 0 | 1 +------+------+ 0 | 1 0 | 1 +-----+-----+ +---+----+ | | | | a b c | 0 | 1 +-----+-----+ | | d e</pre><p>于是我们得到了此信息的编码表：</p><pre>a - 00 b - 01 c - 10 d - 110 e - 111</pre><p>可以将例子中的信息编码为：</p><pre>cabcedeacacdeddaaabaababaaabbacdebaceada</pre><pre>10 00 01 10 111 110 111 00 10 00 10 ......</pre><p>码长共 91 位。考虑用 ASCII 码表示上述信息需要8 * 40 = 240 位，我们确实实现了数据压缩。</p><p><strong>Huffman 编码</strong></p><p>Huffman 编码构造二叉树的方法和 Shannon-Fano正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习Huffman 编码方法。</p><p>1)将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。</p><pre> a(16) b(7) c(6) d(6) e(5)</pre><p>2) 在 1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：</p><pre> | (11) a(16) b(7) c(6) +---+---+ | | d e</pre><p>3) 对上面得到的树林重复 2的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：</p><pre> 根(root) 0 | 1 +------+----------------+ | 0 | 1 | +---------+-----------+ | 0 | 1 0 | 1 a +-------+------+ +-------+-------+ | | | | b c d e </pre><p>由此，我们可以建立和 Shannon-Fano编码略微不同的编码表：</p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -