📄 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="http://www.contextfree.net/">返回断章取义堂</a> <a href="http://www.contextfree.net/wangyg/">返回咏刚的家</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 + -