?? 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 + -