?? 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
這個名字，程序員們至少會聯(lián)想到二叉樹和二進制編碼。的確，我們總以
Huffman 編碼來概括 D.A.Huffman 個人對計算機領域特別是數據壓縮領域的杰出貢獻。我們知道，壓縮
= 模型 +
編碼，作為一種壓縮方法，我們必須全面考慮其模型和編碼兩個模塊的功效；但同時，模型和編碼兩個模塊又相互具有獨立性。舉例來說，一個使用
Huffman 編碼方法的程序，完全可以采用不同的模型來統(tǒng)計字符在信息中出現(xiàn)的概率。因此，我們這一章將首先圍繞
Huffman 先生最為重要的貢獻 —— Huffman
編碼展開討論，隨后，我們再具體介紹可以和
Huffman 聯(lián)合使用的概率模型。</p>
<p><strong>為什么是二叉樹</strong></p>
<p>為什么壓縮領域中的編碼方法總和二叉樹聯(lián)系在一起呢？原因非常簡單，回憶一下我們介紹過的“前綴編碼”：為了使用不固定的碼長表示單個字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長編碼的前綴。要構造符合這一要求的二進制編碼體系，二叉樹是最理想的選擇。考察下面這棵二叉樹：</p>
<pre> 根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a | d e
0 | 1
+-----+-----+
| |
b c</pre>
<p>要編碼的字符總是出現(xiàn)在樹葉上，假定從根向樹葉行走的過程中，左轉為0，右轉為1，則一個字符的編碼就是從根走到該字符所在樹葉的路徑。正因為字符只能出現(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，符合要求的前綴編碼也就構造成功了：</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>討論之前，我們假定要編碼字符的出現(xiàn)概率已經由某一模型統(tǒng)計出來，例如，對下面這串出現(xiàn)了五種字符的信息(
40 個字符長 ):</p>
<pre>cabcedeacacdeddaaabaababaaabbacdebaceada</pre>
<p>五種字符的出現(xiàn)次數分別：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
兩步，直到所有的符號都成為二叉樹的樹葉為止。現(xiàn)在我們有如下的二叉樹：</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 位，我們確實實現(xiàn)了數據壓縮。</p>
<p><strong>Huffman 編碼</strong></p>
<p>Huffman 編碼構造二叉樹的方法和 Shannon-Fano
正好相反，不是自上而下，而是從樹葉到樹根生成二叉樹。現(xiàn)在，我們仍然使用上面的例子來學習
Huffman 編碼方法。</p>
<p>1)
將各個符號及其出現(xiàn)頻率分別作為不同的小二叉樹（目前每棵樹只有根節(jié)點）。</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 + -