?? chapter2.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>第二章 技術準備：概率、模型和編碼</h2><div align="right"><address> <a href="Chapter1.htm">第一章</a> <a href="Chapter3.htm">第三章</a></address></div><p align="left"><strong>什么是熵</strong></p><p align="left">數據壓縮不僅起源于 40 年代由 ClaudeShannon 首創的信息論，而且其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學中的名詞“熵”(Entropy )來表示一條信息中真正需要編碼的信息量：</p><p align="left">考慮用 0 和 1組成的二進制數碼為含有 n 個符號的某條信息編碼，假設符號Fn <font size="3">在整條信息中重復出現的概率為 Pn，則該符號的熵也即表示該符號所需的位數位為：</font></p><div align="left"><pre><font size="3">En = - log<sub>2</sub>( Pn )</font></pre></div><p align="left"><font size="3">整條信息的熵也即表示整條信息所需的位數為：E= ∑En</font></p><p align="left"><font size="3">舉個例子，對下面這條只出現了a b c 三個字符的字符串：</font></p><p align="left"><font size="3">aabbaccbaa</font></p><p align="left"><font size="3">字符串長度為 10，字符 a bc 分別出現了 5 3 2 次，則 a b c 在信息中出現的概率分別為0.5 0.3 0.2，他們的熵分別為：</font></p><div align="left"><pre><font size="3">Ea = -log<sub>2</sub>(0.5) = 1</font></pre></div><div align="left"><pre><font size="3">Eb = -log<sub>2</sub>(0.3) = 1.737</font></pre></div><div align="left"><pre><font size="3">Ec = -log<sub>2</sub>(0.2) = 2.322</font></pre></div><p align="left"><font size="3">整條信息的熵也即表達整個字符串需要的位數為：</font></p><div align="left"><pre><font size="3">E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位</font></pre></div><p align="left"><font size="3">回想一下如果用計算機中常用的ASCII 編碼，表示上面的字符串我們需要整整 80 位呢！現在知道信息為什么能被壓縮而不丟失原有的信息內容了吧。簡單地講，用較少的位數表示較頻繁出現的符號，這就是數據壓縮的基本準則。</font></p><p align="left"><font size="3">細心的讀者馬上會想到，我們該怎樣用0 1 這樣的二進制數碼表示零點幾個二進制位呢？確實很困難，但<strong>不是沒有辦法</strong>。一旦我們找到了準確表示零點幾個二進制位的方法，我們就有權利向無損壓縮的極限挑戰了。不要著急，看到第四章就明白了。</font></p><p align="left"><font size="3"><strong>模型</strong></font></p><p align="left"><font size="3">從上面的描述，我們明白，要壓縮一條信息，首先要分析清楚信息中每個符號出現的概率。不同的壓縮程序通過不同的方法確定符號的出現概率，對符號的概率計算得越準確，也就越容易得到好的壓縮效果。在壓縮程序中，用來處理輸入信息，計算符號的概率并決定輸出哪個或哪些代碼的模塊叫做模型。</font></p><p align="left"><font size="3">難道對信息中字符的出現概率這么難以估計以至于有各種不同的壓縮模型嗎？對上面的字符串我們不是很容易就知道每個字符的概率了嗎？是的是的，不過上面的字符串僅有10 個字符長呀，那只是例子而已。考慮我們現實中要壓縮的文件，大多數可是有幾十K 甚至幾百 K 長，幾 M字節的文件不是也屢見不鮮嗎？</font></p><p align="left"><font size="3">是的，我們可以預先掃描文件中的所有字符，統計出每個字符出現的概率，這種方法在壓縮術語里叫做“靜態統計模型”。但是，不同的文件中，字符有不同的分布概率，我們要么先花上大量的時間統計我們要壓縮的所有文件中的字符概率，要么為每一個單獨的文件保存一份概率表以備解壓縮時需要。糟糕的是，不但掃描文件要消耗大量時間，而且保存一份概率表也使壓縮后的文件增大了不少。所以，在實際應用中，“靜態統計模型”應用的很少。</font></p><p align="left"><font size="3">真正的壓縮程序中使用的大多是一種叫“自適應模型”的東西。自適應模型可以說是一臺具有學習功能的自動機。他在信息被輸入之前對信息內容一無所知并假定每個字符的出現概率均等，隨著字符不斷被輸入和編碼，他統計并紀錄已經出現過的字符的概率并將這些概率應用于對后續字符的編碼。也就是說，自適應模型在壓縮開始時壓縮效果并不理想，但隨著壓縮的進行，他會越來越接近字符概率的準確值，并達到理想的壓縮效果。自適應模型還可以適應輸入信息中字符分布的突然變化，可以適應不同的文件中的字符分布而不需要保存概率表。</font></p><p align="left"><font size="3">上面提到的模型可以統稱為“統計模型”，因為他們都是基于對每個字符出現次數的統計得到字符概率的。另一大類模型叫做“字典模型”。實際上，當我們在生活中提到“工行”這個詞的時候，我們都知道其意思是指“中國工商銀行”，類似的例子還有不少，但共同的前提是我們心中都有一本約定俗成的縮寫字典。字典模型也是如此，他并不直接計算字符出現的概率，而是使用一本字典，隨著輸入信息的讀入，模型找出輸入信息在字典中匹配的最長的字符串，然后輸出該字符串在字典中的索引信息。匹配越長，壓縮效果越好。事實上，字典模型本質上仍然是基于對字符概率的計算的，只不過，字典模型使用整個字符串的匹配代替了對某一字符重復次數的統計。可以證明，字典模型得到的壓縮效果仍然無法突破熵的極限。</font></p><p align="left"><font size="3">當然，對通用的壓縮程序來說，保存一本大字典所需的空間仍然是無法讓人忍受的，況且，任何一本預先定義的字典都無法適應不同文件中數據的變化情況。對了，字典模型也有相應的“自適應”方案。我們可以隨著信息的不斷輸入，從已經輸入的信息中建立合適的字典，并不斷更新這本字典，以適應數據的不斷變化。</font></p><p align="left"><font size="3">讓我們從另一個角度理解一下自適應模型。CluadeShannon 曾試圖通過一個“聚會游戲”(party game)來測定英語的真實信息容量。他每次向聽眾公布一條被他隱藏起一個字符的消息，讓聽眾來猜下一個字符是什么，一次猜一個，直到猜對為止。然后，Shannon使用猜測次數來確定整個信息的熵。在這個實驗中，一種根據前面出現過的字符估計下一個字符概率的模型就存在于聽眾的頭腦中，比計算機中使用的自適應模型更為高級的是，聽眾除了根據字符出現過的次數外，還可以根據他們對語言的經驗進行猜測。</font></p><p align="left"><font size="3"><strong>編碼</strong></font></p><p align="left"><font size="3">通過模型，我們已經確定了對某一個符號該用多少位二進制數進行編碼。現在的問題是，如何設計一種編碼方案，使其盡量精確地用模型計算出來的位數表示某個符號。</font></p><p align="left"><font size="3">最先被考慮的問題是，如果對a 用 3 個二進制位就可以表示，而對 b 用 4 個二進制位就可以表示，那么，在解碼時，面對一連串的二進制流，我怎么知道哪三個位是a，哪四個位是 b 呢？所以，必須設計出一種編碼方式，使得解碼程序可以方便地分離每個字符的編碼部分。于是有了一種叫“前綴編碼”的技術。該技術的主導思想是，任何一個字符的編碼，都不是另一個字符編碼的前綴。反過來說就是，任何一個字符的編碼，都不是由另一個字符的編碼加上若干位0 或 1 組成。看一下前綴編碼的一個最簡單的例子：</font></p><div align="left"><pre><font size="3"> 符號 編碼 A 0 B 10 C 110 D 1110 E 11110</font></pre></div><p align="left">有了上面的碼表，你一定可以輕松地從下面這串二進制流中分辨出真正的信息內容了：</p><div align="left"><pre>1110010101110110111100010 - DABBDCEAAB</pre></div><p align="left">下一個問題是：象上面這樣的前綴編碼只能表示整數位的符號，對幾點幾位的符號只能用近似的整數位輸出，那么怎樣輸出小數位數呢？科學家們用算術編碼解決了這個問題，我們將在第四章對算術編碼作詳細的討論。</p><p align="left"><strong>總結一下</strong></p><p align="left">不同的模型使用不同的方法計算字符的出現概率，由此概率可以得出字符的熵；然后使用不同的編碼方法，盡量接近我們期望得到的熵值。所以，壓縮效果的好壞一方面取決于模型能否準確地得到字符概率，另一方面也取決于編碼方法能否準確地用期望的位數輸出字符代碼。換句話說，壓縮= 模型 + 編碼。如下圖所示：</p><div align="left"><pre><font size="3">--------- 符號 ---------- 概率 ---------- 代碼 ----------| 輸入 |-------->| 模型 |-------->| 編碼 |-------->| 輸出 |--------- ---------- ---------- ---------- </font></pre></div><p align="left"><font size="3"><strong>資源</strong></font></p><p align="left"><font size="3">我們已經知道，編寫壓縮程序往往不能對數據的整個字節進行處理，而是要按照二進制位來讀寫和處理數據，操作二進制位的函數也就成為了壓縮程序中使用最為普遍的工具函數。我們在此提供兩組函數集，使用它們可以有效的進行文件或內存中的二進制位操作。它們共有六個文件：</font></p><p align="left"><font size="3">bitio.h -用于文件中二進制位操作的函數說明。</font></p><p align="left"><font size="3">bitio.cpp -用于文件中二進制位操作的函數實現。</font></p><p align="left"><font size="3">errhand.h 和 errhand.cpp -bitio.cpp 中使用的錯誤處理函數。</font></p><p align="left"><font size="3">wm_bitio.h -用于內存中二進制位操作的函數說明。</font></p><p align="left"><font size="3">wm_bitio.cpp -用于內存中二進制位操作的函數實現。</font></p><p align="left"><font size="3">它們被共同包裝在文件 </font><ahref="src/bitio.zip"><font size="3">bitio.zip</font></a><fontsize="3"> 中。</font></p><p align="left"><font size="3"></font> </p><div align="center"><center><address> <a href="Chapter1.htm">第一章</a> <a href="Chapter3.htm">第三章</a></address></center></div><p align="left"> </p><div align="right"><address> <a href="mailto:wangyg@contextfree.net">有問題嗎？有建議嗎？快給王笨笨寫信</a></address></div><div align="right"><address> <strong>章節書簽：</strong><a href="default.htm">前言</a> <a href="content.htm">目錄</a> <a href="Chapter1.htm">1</a> <a href="Chapter2.htm">2</a> <a href="Chapter3.htm">3</a> <a href="Chapter4.htm">4</a> <a href="Chapter5.htm">5</a> <a href="Chapter6.htm">6</a> <a href="Chapter7.htm">7</a> <a href="Chapter8.htm">8</a> <a href="Chapter9.htm">9</a> <a href="Chapter10.htm">10</a> <a href="Chapter11.htm">11</a> <a href="Chapter12.htm">12</a> </address></div></body></html>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -