?? chapter5.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>第五章 聰明的以色列人(上)：LZ77</h2><div align="right"><address> <a href="Chapter4.htm">第四章</a> <a href="Chapter6.htm">第六章</a></address></div><p><strong>全新的思路</strong></p><p>我們在第三和第四章中討論的壓縮模型都是基于對信息中單個字符出現頻率的統計而設計的，直到70 年代末期，這種思路在數據壓縮領域一直占據著統治地位。在我們今天看來，這種情形在某種程度上顯得有些可笑，但事情就是這樣，一旦某項技術在某一領域形成了慣例，人們就很難創造出在思路上與其大相徑庭的哪怕是更簡單更實用的技術來。</p><p>我們敬佩那兩個在數據壓縮領域做出了杰出貢獻的以色列人，因為正是他們打破了Huffman 編碼一統天下的格局，帶給了我們既高效又簡便的“字典模型”。至今，幾乎我們日常使用的所有通用壓縮工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至許多硬件如網絡設備中內置的壓縮算法，無一例外，都可以最終歸結為這兩個以色列人的杰出貢獻。</p><p>說起來，字典模型的思路相當簡單，我們日常生活中就經常在使用這種壓縮思想。我們常常跟人說“奧運會”、“IBM”、“TCP”之類的詞匯，說者和聽者都明白它們指的是“奧林匹克運動會”、“國際商業機器公司”和“傳輸控制協議”，這實際就是信息的壓縮。我們之所以可以順利使用這種壓縮方式而不產生語義上的誤解，是因為在說者和聽者的心中都有一個事先定義好的縮略語字典，我們在對信息進行壓縮（說）和解壓縮（聽）的過程中都對字典進行了查詢操作。字典壓縮模型正是基于這一思路設計實現的。</p><p>最簡單的情況是，我們擁有一本預先定義好的字典。例如，我們要對一篇中文文章進行壓縮，我們手中已經有一本《現代漢語詞典》。那么，我們掃描要壓縮的文章，并對其中的句子進行分詞操作，對每一個獨立的詞語，我們在《現代漢語詞典》查找它的出現位置，如果找到，我們就輸出頁碼和該詞在該頁中的序號，如果沒有找到，我們就輸出一個新詞。這就是靜態字典模型的基本算法了。</p><p>你一定可以發現，靜態字典模型并不是好的選擇。首先，靜態模型的適應性不強，我們必須為每類不同的信息建立不同的字典；其次，對靜態模型，我們必須維護信息量并不算小的字典，這一額外的信息量影響了最終的壓縮效果。所以，幾乎所有通用的字典模型都使用了自適應的方式，也就是說，將已經編碼過的信息作為字典，如果要編碼的字符串曾經出現過，就輸出該字符串的出現位置及長度，否則輸出新的字符串。根據這一思路，你能從下面這幅圖中讀出其中包含的原始信息嗎？</p><p><img src="putao.gif" width="440" height="57"></p><p>啊，對了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。現在你該大致明白自適應字典模型的梗概了吧。好了，下面就讓我們來深入學習字典模型的第一類實現——LZ77算法。</p><p><strong>滑動的窗口</strong></p><p>LZ77算法在某種意義上又可以稱為“滑動窗口壓縮”，這是由于該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為術語字典，要壓縮的字符串如果在該窗口中出現，則輸出其出現位置和長度。使用固定大小窗口進行術語匹配，而不是在所有已經編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制字典的大小才能保證算法的效率；隨著壓縮的進程滑動字典窗口，使其中總包含最近編碼過的信息，是因為對大多數信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。</p><p>參照下圖，讓我們熟悉一下 LZ77算法的基本流程。</p><p><img src="lz77.gif" width="440" height="130"></p><p>1、從當前壓縮位置開始，考察未編碼的數據，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟2，否則進行步驟 3。</p><p>2、輸出三元符號組 ( off, len, c )。其中 off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c 為下一個字符。然后將窗口向后滑動len + 1 個字符，繼續步驟 1。</p><p>3、輸出三元符號組 ( 0, 0, c )。其中 c為下一個字符。然后將窗口向后滑動 len + 1個字符，繼續步驟 1。</p><p>我們結合實例來說明。假設窗口的大小為 10個字符，我們剛編碼過的 10 個字符是：abcdbbccaa，即將編碼的字符為：abaeaaabaee</p><p>我們首先發現，可以和要編碼字符匹配的最長串為ab ( off = 0, len = 2 ), ab 的下一個字符為 a，我們輸出三元組：(0, 2, a )</p><p>現在窗口向后滑動 3個字符，窗口中的內容為：dbbccaaaba</p><p>下一個字符 e在窗口中沒有匹配，我們輸出三元組：( 0, 0, e )</p><p>窗口向后滑動 1 個字符，其中內容變為：bbccaaabae</p><p>我們馬上發現，要編碼的 aaabae 在窗口中存在(off = 4, len = 6 )，其后的字符為 e，我們可以輸出：(4, 6, e )</p><p>這樣，我們將可以匹配的字符串都變成了指向窗口內的指針，并由此完成了對上述數據的壓縮。</p><p>解壓縮的過程十分簡單，只要我們向壓縮時那樣維護好滑動的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應的匹配串，綴上后繼字符c 輸出（如果 off 和 len 都為 0 則只輸出后繼字符 c)即可還原出原始數據。</p><p>當然，真正實現 LZ77算法時還有許多復雜的問題需要解決，下面我們就來對可能碰到的問題逐一加以探討。</p><p><strong>編碼方法</strong></p><p>我們必須精心設計三元組中每個分量的表示方法，才能達到較好的壓縮效果。一般來講，編碼的設計要根據待編碼的數值的分布情況而定。對于三元組的第一個分量——窗口內的偏移，通常的經驗是，偏移接近窗口尾部的情況要多于接近窗口頭部的情況，這是因為字符串在與其接近的位置較容易找到匹配串，但對于普通的窗口大小（例如4096字節）來說，偏移值基本還是均勻分布的，我們完全可以用固定的位數來表示它。</p><p>編碼 off 需要的位數 bitnum = upper_bound( log<sub>2</sub>(MAX_WND_SIZE ))</p><p>由此，如果窗口大小為 4096，用 12位就可以對偏移編碼。如果窗口大小為 2048，用 11位就可以了。復雜一點的程序考慮到在壓縮開始時，窗口大小并沒有達到MAX_WND_SIZE，而是隨著壓縮的進行增長，因此可以根據窗口的當前大小動態計算所需要的位數，這樣可以略微節省一點空間。</p><p>對于第二個分量——字符串長度，我們必須考慮到，它在大多數時候不會太大，少數情況下才會發生大字符串的匹配。顯然可以使用一種變長的編碼方式來表示該長度值。在前面我們已經知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實Huffman 編碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我在這里介紹其中兩種應用非常廣泛的編碼。</p><p>第一種叫 Golomb 編碼。假設對正整數 x 進行Golomb 編碼，選擇參數 m，令 </p><p>b = 2<sup>m</sup></p><p>q = INT((x - 1)/b)</p><p>r = x - qb - 1</p><p>則 x 可以被編碼為兩部分，第一部分是由 q 個 1加 1 個 0 組成，第二部分為 m位二進制數，其值為 r。我們將 m = 0, 1, 2, 3 時的Golomb 編碼表列出：</p><pre> 值 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</pre><p>從表中我們可以看出，Golomb編碼不但符合前綴編碼的規律，而且可以用較少的位表示較小的x 值，而用較長的位表示較大的 x 值。這樣，如果x 的取值傾向于比較小的數值時，Golomb編碼就可以有效地節省空間。當然，根據 x的分布規律不同，我們可以選取不同的 m值以達到最好的壓縮效果。</p><p>對我們上面討論的三元組 len 值，我們可以采用Golomb 方式編碼。上面的討論中 len 可能取 0，我們只需用len + 1 的 Golomb 編碼即可。至于參數 m 的選擇，一般經驗是取3 或 4 即可。</p><p>可以考慮的另一種變長前綴編碼叫做 γ編碼。它也分作前后兩個部分，假設對 x 編碼，令q = int( log<sub>2</sub>x )，則編碼的前一部分是 q 個 1加一個 0，后一部分是 q位長的二進制數，其值等于 x - 2<sup>q</sup>。γ編碼表如下：</p><pre> 值 x γ編碼--------------------- 1 0 2 10 0 3 10 1 4 110 00 5 110 01?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -