解讀資料壓縮的方法與算法

[psac]

第一章 輕鬆一下：資料壓縮簡史



算起來，資料壓縮的起源要比電腦的起源早得多，有興趣的讀者可以翻閱一下任何一本成語辭典，查查諸如「二桃三士」、「蕭規曹隨」之類的短語涵蓋了多少信息內容。:-)



認真一點：資料壓縮技術在電腦技術的萌芽時期就已經被提上了議事日程，有關信息如何被高效存儲和傳遞的話題不斷被軍事科學家、數學家、電子學家討論來、討論去。終於，隨著信息論的產生和發展，資料壓縮也由熱門話題演變成了真正的技術。



通用無損資料壓縮



科學家在研究中發現，大多數信息的表達都存在著一定的冗余度，通過採用一定的模型和編碼方法，可以降低這種冗余度。貝爾實驗室的 Claude Shannon 和 MIT 的 R.M.Fano 幾乎同時提出了最早的對符號進行有效編碼從而實現資料壓縮的 Shannon-Fano 編碼方法。



D.A.Huffman 於 1952 年第一次發表了他的論文「最小冗余度程式碼的構造方法」(A Method for the Construction of Minimum Redundancy Codes)。從此，資料壓縮開始在商業程序中實現並被套用在許多技術領域。UNIX 系統上一個不太為現代人熟知的壓縮程序 COMPACT 就是 Huffman 0 階自適應編碼的具體實現。80 年代初，Huffman 編碼又在 CP/M 和 DOS 系統中實現，其代表程序叫 SQ。在資料壓縮領域，Huffman 的這一論文事實上開創了資料壓縮技術一個值得回憶的時代，60 年代、70 年代乃至 80 年代的早期，資料壓縮領域幾乎一直被 Huffman 編碼及其分支所壟斷。如果不是後面將要提到的那兩個以色列人，也許我們今天還要在 Huffman 編碼的 0 和 1 的組合中流連忘返。



讓我們沿著 Huffman 的軌跡再向後跳躍幾年，80 年代，數學家們不滿足於 Huffman 編碼中的某些致命弱點，他們從新的角度入手，遵循 Huffman 編碼的主導思想，設計出另一種更為精確，更能接近信息論中「熵」極限的編碼方法——算術編碼。憑借算術編碼的精妙設計和卓越表現，人們終於可以向著資料壓縮的極限前進了。可以證明，算術編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達原始信息內容。當然，算術編碼同時也給程序員和電腦帶來了新的挑戰：要實現和執行算術編碼，需要更為艱苦的編程勞動和更加快速的電腦系統。也就是說，在同樣的電腦系統上，算術編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾十倍的計算時間。這就是為什麼算術編碼不能在我們日常使用的壓縮工具中實現的主要原因。



那麼，能不能既在壓縮效果上超越 Huffman，又不增加程序對系統資源和時間的需求呢？我們必須感謝下面將要介紹的兩個以色列人。



直到 1977 年，資料壓縮的研究工作主要集中於熵、字串和單詞頻率以及統計模型等方面，研究者們一直在絞盡腦汁為使用 Huffman 編碼的程序找出更快、更好的改進方法。1977 年以後，一切都改變了。



1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 發表了論文「順序資料壓縮的一個通用算法」(A Universal Alogrithem for Sequential Data Compression)。



1978 年，他們發表了該論文的續篇「通過可變比率編碼的獨立序列的壓縮」(Compression of Individual Sequences via Variable-Rate Coding)。



所有的一切都改變了，在這兩篇論文中提出的兩個壓縮技術被稱為 LZ77 和 LZ78 (不知為什麼，作者名字的首字母被倒置了)。簡單地說，這兩種壓縮方法的思路完全不同於從 Shannon 到 Huffman 到算術壓縮的傳統思路，倒是和本章開頭所舉的成語辭典的例子頗為相似，因此，人們將關於這一思路的編碼方法稱作「字典」式編碼。字典式編碼不但在壓縮效果上大大超過了 Huffman，而且，對於好的實現，其壓縮和解壓縮的速度也異常驚人。



1984 年，Terry Welch 發表了名為「高效能資料壓縮技術」(A Technique for High-Performance Data Compression)的論文，描述了他在 Sperry Research Center(現在是 Unisys 的一部分)的研究成果。他實現了 LZ78 算法的一個變種 —— LZW。LZW 繼承了 LZ77 和 LZ78 壓縮效果好、速度快的優點，而且在算法描述上更容易被人們接受（有的研究者認為是由於 Welch 的論文比 Ziv 和 Lempel 的更容易理解），實現也比較簡單。不久，UNIX 上出現了使用 LZW 算法的 Compress 程序，該程序效能優良，並有高水準的我的文件，很快成為了 UNIX 世界的壓縮程序標準。緊隨其後的是 MS-DOS 環境下的 ARC 程序( System Enhancement Associates, 1985 )，還有象 PKWare、PKARC 等仿製品。LZ78 和 LZW 一時間統治了 UNIX 和 DOS 兩大平台。



80 年代中期以後，人們對 LZ77 進行了改進，隨之誕生了一批我們今天還在大量使用的壓縮程序。Haruyasu Yoshizaki(Yoshi) 的 LHarc 和 Robert Jung 的 ARJ 是其中兩個著名的例子。LZ77 得以和 LZ78、LZW 一起壟斷當今的通用資料壓縮領域。



目前，關於字典方式的壓縮已經有了一個被廣泛認可的標準，從古老的 PKZip 到現在的 WinZip，特別是隨著 Internet 上文件傳輸的流行，ZIP 格式成為了事實上的標準，沒有哪一種通用的文件壓縮、歸檔系統敢於不支持 ZIP 格式。



多媒體信息的壓縮



今天的程序員們和設計師們往往樂此不疲地為電腦更換更大的硬碟，增加更多的記憶體，其主要目的是為了存放和處理越來越多的聲音、圖像和視瀕資料。對聲音、圖像、視瀕等多媒體信息的壓縮有兩條思路，要麼採用成熟的通用資料壓縮技術進行壓縮，要麼根據媒體信息的特性設計新的壓縮方法。事實上，人們在兩條道路上都作了卓有成效的探索。



還記得 GIF 格式嗎？GIF 可以把原始圖形文件以非常小資料量存儲，可以在同一個文件中存儲多幅圖像從而實現動畫效果。知道 GIF 中的圖像使用什麼方法壓縮的嗎？LZW! 原來如此啊。GIF 大概是使用通用壓縮技術壓縮圖像信息的最成功的例子，當然，GIF 文件中除了經過 LZW 壓縮的像素信息以外，還儲存有圖像的各種內容信息以及圖像所使用的調色板信息等。GIF 精確地保留了原始圖像的每一個像素信息，是無損圖像壓縮的代表。



根據媒體特性量身定制的壓縮方法中，行程編碼(RLE: Run-Length Encoding)是最為簡單、最容易被想到的一種。大多數電腦中產生的圖像(和現實世界的圖像例如照片不同)都具有著大面積重複的顏色塊，為什麼非要用無數個完全相同的顏色值來表示某塊圖像呢？我們完全可以用一個顏色值加一個重複次數來表示這一塊圖像，冗余度由此減小了，這就是 RLE 方法的基本思路。顯然，它不適於用來壓縮照片、聲音等很少連續重複信息的資料。RLE 方法最有代表性的實現有 PCX 和 Targa 圖形格式。



如果分別考察的話，只有黑白兩種顏色的二值圖像以及只有 256 級灰度變化的圖像具有一些獨特的地方，可以被壓縮算法加以利用。我們知道，傳真圖像是一種典型的二值圖像。國際電報電話咨詢委員會( CCITT )為此建立了一系列的壓縮標準，專門用於壓縮傳遞二值圖像（可以是無損的或有損的）。對於灰度圖像，除了著名的 JPEG 標準以外，後文將要介紹的一種叫 FELICS 的算法可以實現效果非常好的無損壓縮。



70 年代末 80 年代初，人們逐漸意識到，對到多數灰度或是彩色圖像乃至聲音文件，沒有必要忠實地保留其所有信息，在允許一定的精度損失的情況下，可以實現更為有效的壓縮方法。到 80 年代末，許多人已經在這一領域取得了不小的收穫，設計出了一批在壓縮效果上讓人驚奇不已的聲音和圖像壓縮算法。在此基礎上，國際標準化組織( ISO )和 CCITT 聯合組成了兩個委員會。委員會的名字我們大概都已經非常熟悉了：靜態圖像聯合專家小組( JPEG )和動態圖像聯合專家小組( MPEG )。JPEG 的壓縮目標是靜止圖像（灰度的和彩色的），MPEG 的目標則是聲音和視瀕。但他們的基本思路是完全一樣的，即保留媒體信息中最有規律、最能體現信息主要特徵的資料，而略去其他不重要的資料。他們都取得了令人讚歎的成就。



你剛看完 VCD 嗎？那麼你剛剛享用過他們為我們帶來的樂趣了。知道普通 VCD 每一畫格有多少彩色像素嗎？知道每秒鐘播放多少畫格嗎？知道的話，算一算一部 100 分鐘的電影不壓縮的話需要多少空間。每張光碟的容量是 640M，那麼，不壓縮的電影需要多少張光碟來存放呢？你該知道 JPEG 或是 MPEG 的厲害了吧。



最後，必須簡單地提到與圖像壓縮領域相關的電子出版印刷領域中的一種叫做 PostScript 的東西。PostScript是作為電子印刷業的標準頁面描述語言被設計出來的，它起源於 1976 年的 Evans & Sutherland 電腦公司，當時的名字是 Design System。1978 年，John Warnock 和 Martin Newel 將其演變為 JAM 語言。1982 年，John Warnock 和 Chuck Geschke 新增了著名的 Adobe System 公司，並第三次設計和實現了這個語言，並將其稱為 PostScript。



PostScript 的主要思路是存儲和傳輸預先定義的指令來「畫」出圖像，而不是存儲和傳輸圖像的每一個像素，這特別適用於在激光列印機上的輸出。採用類似「從(10, 10)到(100, 100)畫一條紅色直線」或是「在（50，50）以 40 為半徑畫一個藍色的圓」之類的指令存儲圖像顯然比直接存儲每個像素節省了不少地方。所以，從壓縮技術的角度來看，PostScript 也可以算是壓縮方法的一種。根據類似的原理，Windows 中的 WMF 格式、HP 的 HPGL 語言、AutoCAD 中使用的 DXF 格式等等，都可以對某種特定的圖像進行有效的壓縮。



第二章 技術準備：概率、模型和編碼



什麼是熵



資料壓縮不僅起源於 40 年代由 Claude Shannon 首創的信息論，而且其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學中的名詞「熵」( Entropy )來表示一條信息中真正需要編碼的信息量：



考慮用 0 和 1 組成的二進制數碼為含有 n 個符號的某條信息編碼，假設符號 Fn 在整條信息中重複出現的概率為 Pn，則該符號的熵也即表示該符號所需的位數位為：



En = - log2( Pn )
整條信息的熵也即表示整條信息所需的位數為：E = ΣEn



舉個例子，對下面這條只出現了 a b c 三個字串的字串串：



aabbaccbaa



字串串長度為 10，字串 a b c 分別出現了 5 3 2 次，則 a b c 在信息中出現的概率分別為 0.5 0.3 0.2，他們的熵分別為：



Ea = -log2(0.5) = 1
Eb = -log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整條信息的熵也即表達整個字串串需要的位數為：



E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
回想一下如果用電腦中常用的 ASCII 編碼，表示上面的字串串我們需要整整 80 位呢！現在知道信息為什麼能被壓縮而不丟失原有的信息內容了吧。簡單地講，用較少的位數表示較頻繁出現的符號，這就是資料壓縮的基本準則。



細心的讀者馬上會想到，我們該怎樣用 0 1 這樣的二進制數碼表示零點幾個二進制位呢？確實很困難，但不是沒有辦法。一旦我們找到了準確表示零點幾個二進制位的方法，我們就有權利向無損壓縮的極限挑戰了。不要著急，看到第四章就明白了。



模型



從上面的描述，我們明白，要壓縮一條信息，首先要分析清楚信息中每個符號出現的概率。不同的壓縮程序通過不同的方法確定符號的出現概率，對符號的概率計算得越準確，也就越容易得到好的壓縮效果。在壓縮程序中，用來處理輸入信息，計算符號的概率並決定輸出哪個或哪些程式碼的模組叫做模型。



難道對信息中字串的出現概率這麼難以估計以至於有各種不同的壓縮模型嗎？對上面的字串串我們不是很容易就知道每個字串的概率了嗎？是的是的，不過上面的字串串僅有 10 個字串長呀，那只是例子而已。考慮我們現實中要壓縮的文件，大多數可是有幾十 K 甚至幾百 K 長，幾 M 字元的文件不是也屢見不鮮嗎？



是的，我們可以預先掃瞄文件中的所有字串，統計出每個字串出現的概率，這種方法在壓縮術語裡叫做「靜態統計模型」。但是，不同的文件中，字串有不同的分佈概率，我們要麼先花上大量的時間統計我們要壓縮的所有文件中的字串概率，要麼為每一個單獨的文件儲存一份概率表以備解壓縮時需要。糟糕的是，不但掃瞄文件要消耗大量時間，而且儲存一份概率表也使壓縮後的文件增大了不少。所以，在實際套用中，「靜態統計模型」套用的很少。



真正的壓縮程序中使用的大多是一種叫「自適應模型」的東西。自適應模型可以說是一台具有學習功能的自動機。他在信息被輸入之前對信息內容一無所知並假定每個字串的出現概率均等，隨著字串不斷被輸入和編碼，他統計並紀錄已經出現過的字串的概率並將這些概率套用於對後續字串的編碼。也就是說，自適應模型在壓縮開始時壓縮效果並不理想，但隨著壓縮的進行，他會越來越接近字串概率的準確值，並達到理想的壓縮效果。自適應模型還可以適應輸入信息中字串分佈的突然變化，可以適應不同的文件中的字串分佈而不需要儲存概率表。



上面提到的模型可以統稱為「統計模型」，因為他們都是關於對每個字串出現次數的統計得到字串概率的。另一大類模型叫做「字典模型」。實際上，當我們在生活中提到「工行」這個詞的時候，我們都知道其意思是指「中國工商銀行」，類似的例子還有不少，但共同的前提是我們心中都有一本約定俗成的縮寫字典。字典模型也是如此，他並不直接計算字串出現的概率，而是使用一本字典，隨著輸入信息的讀入，模型找出輸入信息在字典中匹配的最長的字串串，然後輸出該字串串在字典中的索引信息。匹配越長，壓縮效果越好。事實上，字典模型本質上仍然是關於對字串概率的計算的，只不過，字典模型使用整個字串串的匹配替代了對某一字串重複次數的統計。可以證明，字典模型得到的壓縮效果仍然無法突破熵的極限。



當然，對通用的壓縮程序來說，儲存一本大字典所需的空間仍然是無法讓人忍受的，況且，任何一本預先定義的字典都無法適應不同文件中資料的變化情況。對了，字典模型也有相應的「自適應」方案。我們可以隨著信息的不斷輸入，從已經輸入的信息中建立合適的字典，並不斷更新這本字典，以適應資料的不斷變化。



讓我們從另一個角度理解一下自適應模型。Cluade Shannon 曾試突通過一個「聚會遊戲」(party game)來測定英語的真實信息容量。他每次向聽眾公佈一條被他隱藏起一個字串的消息，讓聽眾來猜下一個字串是什麼，一次猜一個，直到猜對為止。然後，Shannon 使用猜測次數來確定整個信息的熵。在這個實驗中，一種根據前面出現過的字串估計下一個字串概率的模型就存在於聽眾的頭腦中，比電腦中使用的自適應模型更為進階的是，聽眾除了根據字串出現過的次數外，還可以根據他們對語言的經驗進行猜測。



編碼



通過模型，我們已經確定了對某一個符號該用多少位二進制數進行編碼。現在的問題是，如何設計一種編碼方案，使其盡量精確地用模型計算出來的位數表示某個符號。



最先被考慮的問題是，如果對 a 用 3 個二進制位就可以表示，而對 b 用 4 個二進制位就可以表示，那麼，在解碼時，面對一連串的二進制流，我怎麼知道哪三個位是 a，哪四個位是 b 呢？所以，必須設計出一種編碼方式，使得解碼程序可以方便地分離每個字串的編碼部分。於是有了一種叫「前綴編碼」的技術。該技術的主導思想是，任何一個字串的編碼，都不是另一個字串編碼的前綴。反過來說就是，任何一個字串的編碼，都不是由另一個字串的編碼加上若干位 0 或 1 組成。看一下前綴編碼的一個最簡單的例子：




符號 編碼
A 0
B 10
C 110
D 1110
E 11110



有了上面的碼表，你一定可以輕鬆地從下面這串二進制流中分辨出真正的信息內容了：



1110010101110110111100010 - DABBDCEAAB
下一個問題是：象上面這樣的前綴編碼只能表示整數位的符號，對幾點幾位的符號只能用近似的整數位輸出，那麼怎樣輸出小數位數呢？科學家們用算術編碼解決了這個問題，我們將在第四章對算術編碼作詳細的討論。



總結一下



不同的模型使用不同的方法計算字串的出現概率，由此概率可以得出字串的熵；然後使用不同的編碼方法，盡量接近我們期望得到的熵值。所以，壓縮效果的好壞一方面取決於模型能否準確地得到字串概率，另一方面也取決於編碼方法能否準確地用期望的位數輸出字串程式碼。換句話說，壓縮 = 模型 + 編碼。如下圖所顯示：




--------- 符號 ---------- 概率 ---------- 程式碼 ----------
| 輸入 |-------->| 模型 |-------->| 編碼 |-------->| 輸出 |
--------- ---------- ---------- ----------



第三章 奇妙的二叉樹：Huffman的貢獻

提起 Huffman 這個名字，程序員們至少會聯想到二叉樹和二進制編碼。的確，我們總以 Huffman 編碼來概括 D.A.Huffman 個人對電腦領域特別是資料壓縮領域的傑出貢獻。我們知道，壓縮 = 模型 + 編碼，作為一種壓縮方法，我們必須全面考慮其模型和編碼兩個模組的功效；但同時，模型和編碼兩個模組又相互具有獨立性。舉例來說，一個使用 Huffman 編碼方法的程序，完全可以採用不同的模型來統計字串在信息中出現的概率。因此，我們這一章將首先圍繞 Huffman 先生最為重要的貢獻 —— Huffman 編碼展開討論，隨後，我們再具體介紹可以和 Huffman 聯合使用的概率模型。



為什麼是二叉樹



為什麼壓縮領域中的編碼方法總和二叉樹聯繫在一起呢？原因非常簡單，回憶一下我們介紹過的「前綴編碼」：為了使用不類BIOS的碼長表示單個字串，編碼必須符合「前綴編碼」的要求，即較短的編碼決不能是較長編碼的前綴。要構造符合這一要求的二進制編碼體系，二叉樹是最理想的選項。考察下面這棵二叉樹：



根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a | d e
0 | 1
+-----+-----+
| |
b c
要編碼的字串總是出現在樹葉上，假定從根向樹葉行走的程序中，左轉為0，右轉為1，則一個字串的編碼就是從根走到該字串所在樹葉的路徑。正因為字串只能出現在樹葉上，任何一個字串的路徑都不會是另一字串路徑的前綴路徑，符合要求的前綴編碼也就構造成功了：



a - 00 b - 010 c - 011 d - 10 e - 11
Shannon-Fano 編碼



進入 Huffman 先生構造的神奇二叉樹之前，我們先來看一下它的前身，由 Claude Shannon 和 R.M.Fano 兩人提出的 Shannon-Fano 編碼。



討論之前，我們假定要編碼字串的出現概率已經由某一模型統計出來，例如，對下面這串出現了五種字串的信息( 40 個字串長 ):



cabcedeacacdeddaaabaababaaabbacdebaceada
五種字串的出現次數分別：a - 16，b - 7，c - 6，d - 6，e - 5。



Shannon-Fano 編碼的核心仍然是構造二叉樹，構造的方式非常簡單：



1) 將給定符號按照其頻率從大到小排序。對上面的例子，應該得到：



a - 16
b - 7
c - 6
d - 6
e - 5
2) 將序列分成上下兩部分，使得上部頻率總和盡可能接近下部頻率總和。我們有：



a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我們把第二步中劃分出的上部作為二叉樹的左子樹，記 0，下部作為二叉樹的右子樹，記 1。



4) 分別對左右子樹重複 2 3 兩步，直到所有的符號都成為二叉樹的樹葉為止。現在我們有如下的二叉樹：



根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a b c |
0 | 1
+-----+-----+
| |
d e
於是我們得到了此信息的編碼表：



a - 00 b - 01 c - 10 d - 110 e - 111
可以將例子中的信息編碼為：



cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
碼長共 91 位。考慮用 ASCII 碼表示上述信息需要 8 * 40 = 240 位，我們確實實現了資料壓縮。



Huffman 編碼



Huffman 編碼構造二叉樹的方法和 Shannon-Fano 正好相反，不是自上而下，而是從樹葉到樹根產生二叉樹。現在，我們仍然使用上面的例子來學習 Huffman 編碼方法。



1) 將各個符號及其出現頻率分別作為不同的小二叉樹（目前每棵樹只有根節點）。



a(16) b(7) c(6) d(6) e(5)
2) 在 1 中得到的樹林裡找出頻率值最小的兩棵樹，將他們分別作為左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值為兩棵子樹頻率值之和。對上面的例子，我們得到一個新的樹林：



| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 對上面得到的樹林重複 2 的做法，直到所有符號都連入樹中為止。這一步完成後，我們有這樣的二叉樹：



根(root)
0 | 1
+------+----------------+
| 0 | 1
| +---------+-----------+
| 0 | 1 0 | 1
a +-------+------+ +-------+-------+
| | | |
b c d e
由此，我們可以建立和 Shannon-Fano 編碼略微不同的編碼表：



a - 0 b - 100 c - 101 d - 110 e - 111
對例子中信息的編碼為：



cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
碼長共 88 位。這比使用 Shannon-Fano 編碼要更短一點。



讓我們回顧一下熵的知識，使用我們在第二章學到的計算方法，上面的例子中，每個字串的熵為：



Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵為：



E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是說，表示該條信息最少需要 86.601 位。我們看到，Shannon-Fano 編碼和 Huffman 編碼都已經比較接近該信息的熵值了。同時，我們也看出，無論是 Shannon-Fano 還是 Huffman，都只能用近似的整數位來表示單個符號，而不是理想的小數位。我們可以將它們做一個對比：



符號 理想位數 S-F 編碼 Huffman 編碼
( 熵 ) 需要位數 需要位數
----------------------------------------------------
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
----------------------------------------------------
總 計 86。601 91 88
這就是象 Huffman 這樣的整數位編碼方式無法達到最理想的壓縮效果的原因。



為 Huffman 編碼選項模型（附範式 Huffman 編碼）



最簡單，最容易被 Huffman 編碼利用的模型是「靜態統計模型」，也就是說在編碼前統計要編碼的信息中所有字串的出現頻率，讓後根據統計出的信息建立編碼樹，進行編碼。這種模型的缺點是顯而易見的：首先，對資料量較大的信息，靜態統計要消耗大量的時間；其次，必須儲存統計出的結果以便解碼時構造相同的編碼樹，或者直接儲存編碼樹本身，而且，對於每次靜態統計，都有不同的結果，必須分別予以儲存，這要消耗大量的空間（這意味著壓縮效率的下降）；再次，事實上，即使不將編碼樹計算在內，對通常含有 0 - 255 字串集的電腦文件來說，靜態統計模型統計出的頻率是字串在整個文件中的出現頻率，往往反映不出字串在文件中不同局部出現頻率的變化情況，使用這一頻率進行壓縮，大多數情況下得不到太好壓縮效果，文件有時甚至在壓縮後反而增大了。所以，「靜態統計模型」一般僅作為複雜算法的某一部分出現，在信息的某一局部完成壓縮功能。我們很難將其用於獨立的壓縮系統。



有一種有效的「靜態統計模型」的替代方案，如果我們要壓縮的所有信息具有某些共同的特性，也即在分佈上存在著共同的特徵，比如我們要壓縮的是普通的英文文本，那麼，字母 a 或者字母 e 的出現頻率應當是大致穩定的。使用語言學家事先已經建立好的字母頻率表來進行壓縮和解壓縮，不但不用儲存多份統計信息，而且一般說來對該類文件有著較好的壓縮效果。這種方案除了適應性不太強以外，偶爾還會有一些尷尬的時候。讀一遍下面這段話：



If Youth，throughout all history， had had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldn't constantly run across folks today who claim that "a child don't know anything." - Gadsby by E.V.Wright, 1939.



發現什麼問題了嗎？哦，整段話中竟沒有出現一次英文中出現頻率最高的字母 e ！真讓人驚奇，但沒有辦法，事先擬定的頻率分佈總有意外的時候。



對英文或中文文本，有一種比較實用的靜態模型：不是把字串而是把英文單詞或中文詞語作為統計頻率和編碼的服務機構進行壓縮。也就是說，每次編碼的不再是 a b c 這樣的單個符號，而是 the look flower 這樣的單詞。這種壓縮方式可以達到相當不錯的壓縮效果，並被廣泛地用於全文檢索系統。



對關於詞的編碼方式，需要解決幾個技術難點。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎麼辦呢？其實，有很多中文分詞算法可以解決這個問題，本書就不再詳細介紹了。王笨笨就曾開發過一個不錯的分詞模組，但希望通過收取一定報酬的方式提供該模組，如有需要，請和王笨笨 E-Mail 聯繫。一旦我們將詞語分離出來，我們就可以對每個詞進行頻率統計，然後建立 Huffman 編碼樹，輸出編碼時，一個編碼將替代一個詞語。但要注意，英文和漢語的單詞數量都在幾萬到十幾萬左右，也就是說，我們的 Huffman 編碼樹將擁有十幾萬個葉子節點，這對於一棵樹來說太大太大了，系統將無力承擔所需要的資源，這怎麼辦呢？我們可以暫時拋開樹結構，採用另一種構造 Huffman 編碼的方式——範式 Huffman 編碼。



範式 Huffman 編碼(Canonical Huffman Code)的基本思路是：並非只有使用二叉樹建立的前綴編碼才是 Huffman 編碼，只要符合(1)是前綴編碼(2)某一字串編碼長度和使用二叉樹建立的該字串的編碼長度相同這兩個條件的編碼都可以叫做 Huffman 編碼。考慮對下面六個單詞的編碼：



符號 出現次數 傳統 Huffman 編碼 範式 Huffman 編碼
------------------------------------------------------------
單詞1 10 000 000
單詞2 11 001 001
單詞3 12 100 010
單詞4 13 101 011
單詞5 22 01 10
單詞6 23 11 11
注意到範式 Huffman 編碼的獨特之處了嗎？你無法使用二叉樹來建立這組編碼，但這組編碼確實能起到和 Huffman 編碼相同的作用。而且，範式 Huffman 編碼具有一個明顯的特點：當我們把要編碼的符號按照其頻率從小到大排列時，如果把範式 Huffman 編碼本身作為單詞的話，也呈現出從小到大的字典順序。



構造範式 Huffman 編碼的方法大致是：



1) 統計每個要編碼符號的頻率。



2) 根據這些頻率信息求出該符號在傳統 Huffman 編碼樹中的深度（也就是表示該符號所需要的位數 - 編碼長度）。因為我們關心的僅僅是該符號在樹中的深度，我們完全沒有必要構造二叉樹，僅用一個陣列就可以模擬二叉樹的新增程序並得到符號的深度，具體方法這裡就不詳述了。



3) 分別統計從最大編碼長度 maxlength 到 1 的每個長度對應了多少個符號。根據這一信息從 maxlength 個 0 開始以遞增順序為每個符號分配編碼。例如，編碼長度為 5 的符號有 4 個，長度為 3 的有 1 個，長度為 2 的有 3 個，則分配的編碼依次為： 00000 00001 00010 00011 001 01 10 11



4) 編碼輸出壓縮信息，並儲存按照頻率順序排列的符號表，然後儲存每組同樣長度編碼中的最前一個編碼以及該組中的編碼個數。



現在完全可以不依賴任何樹結構進行高速解壓縮了。而且在整個壓縮、解壓縮程序中需要的空間比傳統 Huffman 編碼少得多。



最後要提到的是，Huffman 編碼可以採用自適應模型，根據已經編碼的符號頻率決定下一個符號的編碼。這時，我們無需為解壓縮預先儲存任何信息，整個編碼是在壓縮和解壓縮程序中動態新增的，而且自適應編碼由於其符號頻率是根據信息內容的變化動態得到的，更符合符號的局部分佈規律，因此在壓縮效果上比靜態模型好許多。但是，採用自適應模型必須考慮編碼表的動態特性，即編碼表必須可以隨時更新以適應符號頻率的變化。對於 Huffman 編碼來說，我們很難建立能夠隨時更新的二叉樹，使用範式 Huffman 編碼是個不錯的選項，但依然存在不少技術上的難題。幸好，如果願意的話，我們可以暫時不考慮自適應模型的 Huffman 編碼，因為對於自適應模型我們還有許多更好的選項，下面幾章將要談到的算術編碼、字典編碼等更為適合採用自適應模型，我們將在其中深入探討自適應模型的各種實現方法。



第四章 向極限挑戰：算術編碼



我們在上一章中已經明白，Huffman 編碼使用整數個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優的壓縮效果。假設某個字串的出現概率為 80%，該字串事實上只需要 -log2(0.8) = 0.322 位編碼，但 Huffman 編碼一定會為其分配一位 0 或一位 1 的編碼。可以想像，整個信息的 80% 在壓縮後都幾乎相當於理想長度的 3 倍左右，壓縮效果可想而知。



難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？是用剪刀把電腦存儲器中的二進制位剪開嗎？電腦真有這樣的特異功能嗎？慢著慢著，我們不要被表面現象所迷惑，其實，在這一問題上，我們只要換一換腦筋，從另一個角度……哎呀，還是想不通，怎麼能是半個呢？好了，不用費心了，數學家們也不過是在十幾年前才想到了算術編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個角度找到突破口的吧。



輸出：一個小數



更神奇的事情發生了，算術編碼對整條信息（無論信息有多麼長），其輸出僅僅是一個數，而且是一個介於 0 和 1 之間的二進制小數。例如算術編碼對某條信息的輸出為 1010001111，那麼它表示小數 0.1010001111，也即十進制數 0.64。



咦？怎麼一會兒是表示半個二進制位，一會兒又是輸出一個小數，算術編碼怎麼這麼古怪呀？不要著急，我們借助下面一個簡單的例子來闡釋算術編碼的基本原理。為了表示上的清晰，我們暫時使用十進製表示算法中出現的小數，這絲毫不會影響算法的可行性。



考慮某條信息中可能出現的字串僅有 a b c 三種，我們要壓縮儲存的信息為 bccb。



在沒有開始壓縮排程之前，假設我們對 a b c 三者在信息中的出現概率一無所知（我們採用的是自適應模型），沒辦法，我們暫時認為三者的出現概率相等，也就是都為 1/3，我們將 0 - 1 區間按照概率的比例分配給三個字串，即 a 從 0.0000 到 0.3333，b 從 0.3333 到 0.6667，c 從 0.6667 到 1.0000。用圖形表示就是：



+-- 1.0000
|
Pc = 1/3 |
|
+-- 0.6667
|
Pb = 1/3 |
|
+-- 0.3333
|
Pa = 1/3 |
|
+-- 0.0000
現在我們拿到第一個字串 b，讓我們把目光投向 b 對應的區間 0.3333 - 0.6667。這時由於多了字串 b，三個字串的概率分佈變成：Pa = 1/4，Pb = 2/4，Pc = 1/4。好，讓我們按照新的概率分佈比例劃分 0.3333 - 0.6667 這一區間，劃分的結果可以用圖形表示為：



+-- 0.6667
Pc = 1/4 |
+-- 0.5834
|
|
Pb = 2/4 |
|
|
+-- 0.4167
Pa = 1/4 |
+-- 0.3333
接著我們拿到字串 c，我們現在要關注上一步中得到的 c 的區間 0.5834 - 0.6667。新添了 c 以後，三個字串的概率分佈變成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我們用這個概率分佈劃分區間 0.5834 - 0.6667：



+-- 0.6667
|
Pc = 2/5 |
|
+-- 0.6334
|
Pb = 2/5 |
|
+-- 0.6001
Pa = 1/5 |
+-- 0.5834
現在輸入下一個字串 c，三個字串的概率分佈為：Pa = 1/6，Pb = 2/6，Pc = 3/6。我們來劃分 c 的區間 0.6334 - 0.6667：



+-- 0.6667
|
|
Pc = 3/6 |
|
|
+-- 0.6501
|
Pb = 2/6 |
|
+-- 0.6390
Pa = 1/6 |
+-- 0.6334
輸入最後一個字串 b，因為是最後一個字串，不用再做進一步的劃分了，上一步中得到的 b 的區間為 0.6390 - 0.6501，好，讓我們在這個區間內隨便選項一個容易變成二進制的數，例如 0.64，將它變成二進制 0.1010001111，去掉前面沒有太多意義的 0 和小數點，我們可以輸出 1010001111，這就是信息被壓縮後的結果，我們完成了一次最簡單的算術壓縮程序。



怎麼樣，不算很難吧？可如何解壓縮呢？那就更簡單了。解壓縮之前我們仍然假定三個字串的概率相等，並得出上面的第一幅分佈圖。解壓縮時我們面對的是二進制流 1010001111，我們先在前面加上 0 和小數點把它變成小數 0.1010001111，也就是十進制 0.64。這時我們發現 0.64 在分佈圖中落入字串 b 的區間內，我們立即輸出字串 b，並得出三個字串新的概率分佈。類似壓縮時採用的方法，我們按照新的概率分佈劃分字串 b 的區間。在新的劃分中，我們發現 0.64 落入了字串 c 的區間，我們可以輸出字串 c。同理，我們可以繼續輸出所有的字串，完成全部解壓縮程序（注意，為了敘述方便，我們暫時迴避了如何判斷解壓縮結束的問題，實際套用中，這個問題並不難解決）。



現在把教程拋開，仔細回想一下，直到你理解了算術壓縮的基本原理，並產生了許多新的問題為止。



真的能接近極限嗎？



現在你一定明白了一些東西，也一定有了不少新問題，沒有關係，讓我們一個一個解決。



首先，我們曾反覆強調，算術壓縮可以表示小數個二進制位，並由此可以接近無損壓縮的熵極限，怎麼從上面的描述中沒有看出來呢？



算術編碼實際上採用了化零為整的思想來表示小數個二進制位，我們確實無法精確表示單個小數位字串，但我們可以將許多字串集中起來表示，僅僅允許在最後一位有些許的誤差。



結合上面的簡單例子考慮，我們每輸入一個符號，都對概率的分佈表做一下調整，並將要輸出的小數限定在某個越來越小的區間範圍內。對輸出區間的限定是問題的關鍵所在，例如，我們輸入第一個字串 b 時，輸出區間被限定在 0.3333 - 0.6667 之間，我們無法決定輸出值得第一位是 3、4、5 還是 6，也就是說，b 的編碼長度小於一個十進制位（注意我們用十進制講解，和二進制不完全相同），那麼我們暫時不決定輸出信息的任何位，繼續輸入下面的字串。直到輸入了第三個字串 c 以後，我們的輸出區間被限定在 0.6334 - 0.6667 之間，我們終於知道輸出小數的第一位（十進制）是 6，但仍然無法知道第二位是多少，也即前三個字串的編碼長度在 1 和 2 之間。等到我們輸入了所有字串之後，我們的輸出區間為 0.6390 - 0.6501，我們始終沒有得到關於第二位的確切信息，現在我們明白，輸出所有的 4 個字串，我們只需要 1 點幾個十進制位，我們唯一的選項是輸出 2 個十進制位 0.64。這樣，我們在誤差不超過 1 個十進制位的情況下相當精確地輸出了所有信息，很好地接近了熵值（需要註明的是，為了更好地和下面的課程接軌，上面的例子採用的是 0 階自適應模型，其結果和真正的熵值還有一定的差距）。



小數有多長？



你一定已經想到，如果信息內容特別豐富，我們要輸出的小數將會很長很長，我們該如何在記憶體中表示如此長的小數呢？



其實，沒有任何必要在記憶體中存儲要輸出的整個小數。我們從上面的例子可以知道，在編碼的進行中，我們會不斷地得到有關要輸出小數的各種信息。具體地講，當我們將區間限定在 0.6390 - 0.6501 之間時，我們已經知道要輸出的小數第一位（十進制）一定是 6，那麼我們完全可以將 6 從記憶體中拿掉，接著在區間 0.390 - 0.501 之間繼續我們的壓縮排程。記憶體中始終不會有非常長的小數存在。使用二進制時也是一樣的，我們會隨著壓縮的進行不斷決定下一個要輸出的二進制位是 0 還是 1，然後輸出該位並減小記憶體中小數的長度。



靜態模型如何實現？



我們知道上面的簡單例子採用的是自適應模型，那麼如何實現靜態模型呢？其實很簡單。對信息 bccb 我們統計出其中只有兩個字串，概率分佈為 Pb = 0.5，Pc = 0.5。我們在壓縮程序中不必再更新此概率分佈，每次對區間的劃分都依照此分佈即可，對上例也就是每次都平分區間。這樣，我們的壓縮程序可以簡單表示為：



輸出區間的下限 輸出區間的上限
--------------------------------------------------
壓縮前 0.0 1.0
輸入 b 0.0 0.5
輸入 c 0.25 0.5
輸入 c 0.375 0.5
輸入 b 0.375 0.4375
我們看出，最後的輸出區間在 0.375 - 0.4375 之間，甚至連一個十進制位都沒有確定，也就是說，整個信息根本用不了一個十進制位。如果我們改用二進制來表示上述程序的話，我們會發現我們可以非常接近該信息的熵值（有的讀者可能已經算出來了，該信息的熵值為 4 個二進制位）。



為什麼用自適應模型？



既然我們使用靜態模型可以很好地接近熵值，為什麼還要採用自適應模型呢？



要知道，靜態模型無法適應信息的多樣性，例如，我們上面得出的概率分佈沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間儲存靜態模型統計出的概率分佈，儲存模型所用的空間將使我們重新遠離熵值。其次，靜態模型需要在壓縮前對信息內字串的分佈進行統計，這一統計程序將消耗大量的時間，使得本來就比較慢的算術編碼壓縮更加緩慢。



另外還有最重要的一點，對較長的信息，靜態模型統計出的符號概率是該符號在整個信息中的出現概率，而自適應模型可以統計出某個符號在某一局部的出現概率或某個符號相對於某一上下文的出現概率，換句話說，自適應模型得到的概率分佈將有利於對信息的壓縮（可以說結合上下文的自適應模型的信息熵建立在更高的概率層次上，其總熵值更小），好的關於上下文的自適應模型得到的壓縮結果將遠遠超過靜態模型。



自適應模型的階



我們通常用「階」(order)這一術語區分不同的自適應模型。本章開頭的例子中採用的是 0 階自適應模型，也就是說，該例子中統計的是符號在已輸入信息中的出現概率，沒有考慮任何上下文信息。



如果我們將模型變成統計符號在某個特定符號後的出現概率，那麼，模型就成為了 1 階上下文自適應模型。舉例來說，我們要對一篇英文文本進行編碼，我們已經編碼了 10000 個英文字串，剛剛編碼的字串是 t，下一個要編碼的字串是 h。我們在前面的編碼程序中已經統計出前 10000 個字串中出現了 113 次字母 t，其中有 47 個 t 後面跟著字母 h。我們得出字串 h 在字串 t 後的出現頻率是 47/113，我們使用這一頻率對字串 h 進行編碼，需要 -log2(47/113) = 1.266 位。



對比 0 階自適應模型，如果前 10000 個字串中 h 的出現次數為 82 次，則字串 h 的概率是 82/10000，我們用此概率對 h 進行編碼，需要 -log2(82/10000) = 6.930 位。考慮上下文因素的優勢顯而易見。



我們還可以進一步擴大這一優勢，例如要編碼字串 h 的前兩個字串是 gt，而在已經編碼的文本中 gt 後面出現 h 的概率是 80%，那麼我們只需要 0.322 位就可以編碼輸出字串 h。此時，我們使用的模型叫做 2 階上下文自適應模型。



最理想的情況是採用 3 階自適應模型。此時，如果結合理術編碼，對信息的壓縮效果將達到驚人的程度。採用更高階的模型需要消耗的系統空間和時間至少在目前還無法讓人接受，使用算術壓縮的應用程式大多數採用 2 階或 3 階的自適應模型。



轉義碼的作用



使用自適應模型的算術編碼算法必須考慮如何為從未出現過的上下文編碼。例如，在 1 階上下文模型中，需要統計出現概率的上下文可能有 256 * 256 = 65536 種，因為 0 - 255 的所有字串都有可能出現在 0 - 255 個字串中任何一個之後。當我們面對一個從未出現過的上下文時（比如剛編碼過字串 b，要編碼字串 d，而在此之前，d 從未出現在 b 的後面），該怎樣確定字串的概率呢？



比較簡單的辦法是在壓縮開始之前，為所有可能的上下文分配計數為 1 的出現次數，如果在壓縮中碰到從未出現的 bd 組合，我們認為 d 出現在 b 之後的次數為 1，並可由此得到概率進行正確的編碼。使用這種方法的問題是，在壓縮開始之前，在某上下文中的字串已經具有了一個比較小的頻率。例如對 1 階上下文模型，壓縮前，任意字串的頻率都被人為地設定為 1/65536，按照這個頻率，壓縮開始時每個字串要用 16 位編碼，只有隨著壓縮的進行，出現較頻繁的字串在頻率分佈圖上佔據了較大的空間後，壓縮效果才會逐漸好起來。對於 2 階或 3 階上下文模型，情況就更糟糕，我們要為幾乎從不出現的大多數上下文浪費大量的空間。



我們通過引入「轉義碼」來解決這一問題。「轉義碼」是混在壓縮資料流中的特殊的記號，用於通知解壓縮程序下一個上下文在此之前從未出現過，需要使用低階的上下文進行編碼。



舉例來講，在 3 階上下文模型中，我們剛編碼過 ght，下一個要編碼的字串是 a，而在此之前，ght 後面從未出現過字串 a，這時，壓縮程序輸出轉義碼，然後檢查 2 階的上下文表，看在此之前 ht 後面出現 a 的次數；如果 ht 後面曾經出現過 a，那麼就使用 2 階上下文表中的概率為 a 編碼，否則再輸出轉義碼，檢查 1 階上下文表；如果仍未能查到，則輸出轉義碼，轉入最低的 0 階上下文表，看以前是否出現過字串 a；如果以前根本沒有出現過 a，那麼我們轉到一個特殊的「轉義」上下文表，該表內包含 0 - 255 所有符號，每個符號的計數都為 1，並且永遠不會被更新，任何在高階上下文中沒有出現的符號都可以退到這裡按照 1/256 的頻率進行編碼。



「轉義碼」的引入使我們擺脫了從未出現過的上下文的困擾，可以使模型根據輸入資料的變化快速調整到最佳位置，並迅速減少對高概率符號編碼所需要的位數。



存儲空間問題



在算術編碼高階上下文模型的實現中，對記憶體的需求量是一個十分棘手的問題。因為我們必須保持對已出現的上下文的計數，而高階上下文模型中可能出現的上下文種類又是如此之多，資料結構的設計將直接影響到算法實現的成功與否。



在 1 階上下文模型中，使用陣列來進行出現次數的統計是可行的，但對於 2 階或 3 階上下文模型，陣列大小將依照指數規律增長，現有電腦的記憶體滿足不了我們的要求。



比較聰明的辦法是採用樹結構存儲所有出現過的上下文。利用高階上下文總是建立在低階上下文的基礎上這一規律，我們將 0 階上下文表存儲在陣列中，每個陣列元素包含了指向相應的 1 階上下文表的游標，1 階上下文表中又包含了指向 2 階上下文表的游標……由此構成整個上下文樹。樹中只有出現過的上下文才擁有已分配的節點，沒有出現過的上下文不必佔用記憶體空間。在每個上下文表中，也無需儲存所有 256 個字串的計數，只有在該上下文後面出現過的字串才擁有計數值。由此，我們可以最大限度地減少空間消耗。



第五章 聰明的以色列人(上)：LZ77



全新的思路



我們在第三和第四章中討論的壓縮模型都是關於對信息中單個字串出現頻率的統計而設計的，直到 70 年代末期，這種思路在資料壓縮領域一直佔據著統治地位。在我們今天看來，這種情形在某種程度上顯得有些可笑，但事情就是這樣，一旦某項技術在某一領域形成了慣例，人們就很難創造出在思路上與其大相逕庭的哪怕是更簡單更實用的技術來。



我們敬佩那兩個在資料壓縮領域做出了傑出貢獻的以色列人，因為正是他們打破了 Huffman 編碼一統天下的格局，帶給了我們既高效又簡便的「字典模型」。至今，幾乎我們日常使用的所有通用壓縮工具，像 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至許多硬體如網路設備中內裝的壓縮算法，無一例外，都可以最終歸結為這兩個以色列人的傑出貢獻。



說起來，字典模型的思路相當簡單，我們日常生活中就經常在使用這種壓縮思想。我們常常跟人說「奧運會」、「IBM」、「TCP」之類的詞彙，說者和聽者都明白它們指的是「奧林匹克運動會」、「國際商業機器公司」和「傳輸控制傳輸協定」，這實際就是信息的壓縮。我們之所以可以順利使用這種壓縮方式而不產生語義上的誤解，是因為在說者和聽者的心中都有一個事先定義好的縮略語字典，我們在對信息進行壓縮（說）和解壓縮（聽）的程序中都對字典進行了查詢操作。字典壓縮模型正是關於這一思路設計實現的。



最簡單的情況是，我們擁有一本預先定義好的字典。例如，我們要對一篇中文文章進行壓縮，我們手中已經有一本《現代漢語詞典》。那麼，我們掃瞄要壓縮的文章，並對其中的句子進行分詞操作，對每一個獨立的詞語，我們在《現代漢語詞典》搜尋它的出現位置，如果找到，我們就輸出頁碼和該詞在該頁中的序號，如果沒有找到，我們就輸出一個新詞。這就是靜態字典模型的基本算法了。



你一定可以發現，靜態字典模型並不是好的選項。首先，靜態模型的適應性不強，我們必須為每類不同的信息建立不同的字典；其次，對靜態模型，我們必須維護信息量並不算小的字典，這一額外的信息量影響了最終的壓縮效果。所以，幾乎所有通用的字典模型都使用了自適應的方式，也就是說，將已經編碼過的信息作為字典，如果要編碼的字串串曾經出現過，就輸出該字串串的出現位置及長度，否則輸出新的字串串。根據這一思路，你能從下面這幅圖中讀出其中包含的原始信息嗎？



「吃葡萄不吐22皮，不吃22倒55」(22表示第二位佔2個字串大小）



啊，對了，是「吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮」。現在你該大致明白自適應字典模型的梗概了吧。好了，下面就讓我們來深入學習字典模型的第一類實現——LZ77 算法。



滑動的視窗



LZ77 算法在某種意義上又可以稱為「滑動視窗壓縮」，這是由於該算法將一個虛擬的，可以跟隨壓縮排程滑動的視窗作為術語字典，要壓縮的字串串如果在該視窗中出現，則輸出其出現位置和長度。使用類BIOS大小視窗進行術語匹配，而不是在所有已經編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制字典的大小才能保證算法的效率；隨著壓縮的工作滑動字典視窗，使其中總包含最近編碼過的信息，是因為對大多數信息而言，要編碼的字串串往往在最近的上下文中更容易找到匹配串。



參照下圖，讓我們熟悉一下 LZ77 算法的基本流程。



abc || defghijklm || nop || qrstuvwx || yzab || c || defg
0 off off＋len 下一個字串c
（ 最長匹配 ）

1、從當前壓縮位置開始，考察未編碼的資料，並試突在滑動視窗中找出最長的匹配字串串，如果找到，則進行步驟 2，否則進行步驟 3。



2、輸出三元符號組 ( off, len, c )。其中 off 為視窗中匹配字串串相對視窗邊界的偏移，len 為可匹配的長度，c 為下一個字串。然後將視窗向後滑動 len + 1 個字串，繼續步驟 1。



3、輸出三元符號組 ( 0, 0, c )。其中 c 為下一個字串。然後將視窗向後滑動 len + 1 個字串，繼續步驟 1。



我們結合實例來說明。假設視窗的大小為 10 個字串，我們剛編碼過的 10 個字串是：abcdbbccaa，即將編碼的字串為：abaeaaabaee



我們首先發現，可以和要編碼字串匹配的最長串為 ab ( off = 0, len = 2 ), ab 的下一個字串為 a，我們輸出三元組：( 0, 2, a )



現在視窗向後滑動 3 個字串，視窗中的內容為：dbbccaaaba



下一個字串 e 在視窗中沒有匹配，我們輸出三元組：( 0, 0, e )



視窗向後滑動 1 個字串，其中內容變為：bbccaaabae



我們馬上發現，要編碼的 aaabae 在視窗中存在( off = 4, len = 6 )，其後的字串為 e，我們可以輸出：( 4, 6, e )



這樣，我們將可以匹配的字串串都變成了指向視窗內的游標，並由此完成了對上述資料的壓縮。



解壓縮的程序十分簡單，只要我們向壓縮時那樣維護好滑動的視窗，隨著三元組的不斷輸入，我們在視窗中找到相應的匹配串，綴上後繼字串 c 輸出（如果 off 和 len 都為 0 則只輸出後繼字串 c )即可還原出原始資料。



當然，真正實現 LZ77 算法時還有許多複雜的問題需要解決，下面我們就來對可能碰到的問題逐一加以探討。



編碼方法



我們必須精心設計三元組中每個份量的表示方法，才能達到較好的壓縮效果。一般來講，編碼的設計要根據待編碼的數值的分佈情況而定。對於三元組的第一個份量——視窗內的偏移，通常的經驗是，偏移接近視窗尾部的情況要多於接近視窗頭部的情況，這是因為字串串在與其接近的位置較容易找到匹配串，但對於普通的視窗大小（例如 4096 字元）來說，偏移值基本還是均勻分佈的，我們完全可以用類BIOS的位數來表示它。



編碼 off 需要的位數 bitnum = upper_bound( log2( MAX_WND_SIZE ))



由此，如果視窗大小為 4096，用 12 位就可以對偏移編碼。如果視窗大小為 2048，用 11 位就可以了。複雜一點的程序考慮到在壓縮開始時，視窗大小並沒有達到 MAX_WND_SIZE，而是隨著壓縮的進行增長，因此可以根據視窗的當前大小動態計算所需要的位數，這樣可以略微節省一點空間。



對於第二個份量——字串串長度，我們必須考慮到，它在大多數時候不會太大，少數情況下才會發生大字串串的匹配。顯然可以使用一種變長的編碼方式來表示該長度值。在前面我們已經知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實 Huffman 編碼也可以在此處使用，但卻不是最好的選項。適用於此處的好的編碼方案很多，我在這裡介紹其中兩種套用非常廣泛的編碼。



第一種叫 Golomb 編碼。假設對正整數 x 進行 Golomb 編碼，選項參數 m，令



b = 2m



q = INT((x - 1)/b)



r = x - qb - 1



則 x 可以被編碼為兩部分，第一部分是由 q 個 1 加 1 個 0 組成，第二部分為 m 位二進制數，其值為 r。我們將 m = 0, 1, 2, 3 時的 Golomb 編碼表列出：



值 x m = 0 m = 1 m = 2 m = 3
-------------------------------------------------------------
1 0 0 0 0 00 0 000
2 10 0 1 0 01 0 001
3 110 10 0 0 10 0 010
4 1110 10 1 0 11 0 011
5 11110 110 0 10 00 0 100
6 111110 110 1 10 01 0 101
7 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
從表中我們可以看出，Golomb 編碼不但符合前綴編碼的規律，而且可以用較少的位表示較小的 x 值，而用較長的位表示較大的 x 值。這樣，如果 x 的取值傾向於比較小的數值時，Golomb 編碼就可以有效地節省空間。當然，根據 x 的分佈規律不同，我們可以選取不同的 m 值以達到最好的壓縮效果。



對我們上面討論的三元組 len 值，我們可以採用 Golomb 方式編碼。上面的討論中 len 可能取 0，我們只需用 len + 1 的 Golomb 編碼即可。至於參數 m 的選項，一般經驗是取 3 或 4 即可。



可以考慮的另一種變長前綴編碼叫做 γ 編碼。它也分作前後兩個部分，假設對 x 編碼，令 q = int( log2x )，則編碼的前一部分是 q 個 1 加一個 0，後一部分是 q 位長的二進制數，其值等於 x - 2q 。γ編碼表如下：



值 x γ編碼
---------------------
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
其實，如果對 off 值考慮其傾向於視窗後部的規律，我們也可以採用變長的編碼方法。但這種方式對視窗較小的情況改善並不明顯，有時壓縮效果還不如類BIOS長編碼。



對三元組的最後一個份量——字串 c，因為其分佈並無規律可循，我們只能老老實實地用 8 個二進制位對其編碼。



根據上面的敘述，相信你一定也能寫出高效的編碼和解碼程序了。



另一種輸出方式



LZ77 的原始算法採用三元組輸出每一個匹配串及其後續字串，即使沒有匹配，我們仍然需要輸出一個 len = 0 的三元組來表示單個字串。試驗表明，這種方式對於某些特殊情況（例如同一字串不斷重複的情形）有著較好的適應能力。但對於一般資料，我們還可以設計出另外一種更為有效的輸出方式：將匹配串和不能匹配的單個字串分別編碼、分別輸出，輸出匹配串時不同時輸出後續字串。



我們將每一個輸出分成匹配串和單個字串兩種類型，並首先輸出一個二進制位對其加以區分。例如，輸出 0 表示下面是一個匹配串，輸出 1 表示下面是一個單個字串。



之後，如果要輸出的是單個字串，我們直接輸出該字串的字元值，這要用 8 個二進制位。也就是說，我們輸出一個單個的字串共需要 9 個二進制位。



如果要輸出的是匹配串，我們按照前面的方法依次輸出 off 和 len。對 off，我們可以輸出定長編碼，也可以輸出變長前綴碼，對 len 我們輸出變長前綴碼。有時候我們可以對匹配長度加以限制，例如，我們可以限制最少匹配 3 個字串。因為，對於 2 個字串的匹配串，我們使用匹配串的方式輸出並不一定比我們直接輸出 2 個單個字串（需要 18 位）節省空間（是否節省取決於我們採用何種編碼輸出 off 和 len）。



這種輸出方式的優點是輸出單個字串的時候比較節省空間。另外，因為不強求每次都外帶一個後續字串，可以適應一些較長匹配的情況。



如何搜尋匹配串



在滑動視窗中搜尋最長的匹配串，大概是 LZ77 算法中的核心問題。容易知道，LZ77 算法中空間和時間的消耗集中於對匹配串的搜尋算法。每次滑動視窗之後，都要進行下一個匹配串的搜尋，如果搜尋算法的時間效率在 O(n2) 或者更高，總的算法時間效率就將達到 O(n3)，這是我們無法容忍的。正常的順序匹配算法顯然無法滿足我們的要求。事實上，我們有以下幾種可選的方案。



1、限制可匹配字串串的最大長度（例如 20 個字元），將視窗中每一個 20 字元長的串抽取出來，按照大小順序組織成二叉有序樹。在這樣的二叉有序樹中進行字串串的搜尋，其效率是很高的。樹中每一個節點大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。樹中共有 MAX_WND_SIZE - 19 個節點，假如視窗大小為 4096 字元，樹的大小大約是 130k 字元。空間消耗也不算多。這種方法對匹配串長度的限制雖然影響了壓縮程序對一些特殊資料（又很長的匹配串）的壓縮效果，但就平均效能而言，壓縮效果還是不錯的。



2、將視窗中每個長度為 3 （視情況也可取 2 或 4）的字串串建立索引，先在此索引中匹配，之後對得出的每個可匹配位置進行順序搜尋，直到找到最長匹配字串串。因為長度為 3 的字串串可以有 2563 種情況，我們不可能用靜態陣列存儲該索引結構。使用 Hash 表是一個明智的選項。我們可以僅用 MAX_WND_SIZE - 1 的陣列存儲每個索引點，Hash 函數的參數當然是字串串本身的 3 個字串值了，Hash 函數算法及 Hash 之後的散列函數很容易設計。每個索引點之後是該字串串出現的所有位置，我們可以使用單鏈表來存儲每一個位置。值得注意的是，對一些特殊情況比如 aaaaaa...之類的連續字串，字串串 aaa 有很多連續出現位置，但我們無需對其中的每一個位置都進行匹配，只要對最左邊和最右邊的位置操作就可以了。解決的辦法是在鏈表節點中紀錄相同字串連續出現的長度，對連續的出現位置不再建立新的節點。這種方法可以匹配任意長度的字串串，壓縮效果要好一些，但缺點是搜尋耗時多於第一種方法。



3、使用字串樹( trie )來對視窗內的字串串建立索引，因為字串的取值範圍是 0 - 255，字串樹本身的層次不可能太多，3 - 4 層之下就應該換用其他的資料結構例如 Hash 表等。這種方法可以作為第二種方法的改進算法出現，可以提高搜尋速度，但空間的消耗較多。



如果對視窗中的資料進行索引，就必然帶來一個索引位置表示的問題，即我們在索引結構中該往偏移項中存儲什麼資料：首先，視窗是不斷向後滑動的，我們每次將視窗向後滑動一個位置，索引結構就要作相應的更新，我們必須刪除那些已經移動出視窗的資料，並增加新的索引信息。其次，視窗不斷向後滑動的事實使我們無法用相對視窗左邊界的偏移來表示索引位置，因為隨著視窗的滑動，每個被索引的字串串相對視窗左邊界的位置都在改變，我們無法承擔更新所有索引位置的時間消耗。



解決這一問題的辦法是，使用一種可以環形滾動的偏移系統來建立索引，而輸出匹配字串串時再將環形偏移還原為相對視窗左邊界的真正偏移。讓我們用圖形來說明，視窗剛剛達到最大時，環形偏移和原始偏移系統相同：



偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環形偏移： 0 1 2 3 4 ...... Max
視窗向後滑動一個字元後，滑出視窗左端的環形偏移 0 被補到了視窗右端：



偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環形偏移： 1 2 3 4 5 ...... Max 0
視窗再滑動 3 個子節後，偏移系統的情況是：



偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環形偏移： 4 5 6 7 8...... Max 0 1 2 3
依此類推。



我們在索引結構中儲存環形偏移，但在搜尋到匹配字串串後，輸出的匹配位置 off 必須是原始偏移（相對視窗左邊），這樣才可以保證解碼程序的順利執行。




※※※※※※

[TinoLo2002]

真是受教了

謝謝你

多謝賜教 拷回家慢慢看

真是多阿
看到眼睛都花了
但還是謝謝你 ㄉ分享

感謝...真是清楚^_^