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