第五章 聰明的以色列人(上)：LZ77
第四章 第六章
全新的思路
我們在第三和第四章中讨論的壓縮模型都是基于對資訊中單個字元出現頻率的統計
而設計的，直到 70 年代末期，這種思路在資料壓縮領域一直占據着統治地位。在
我們今天看來，這種情形在某種程度上顯得有些可笑，但事情就是這樣，一旦某項
技術在某一領域形成了慣例，人們就很難創造出在思路上與其大相徑庭的哪怕是更
簡單更實用的技術來。
我們敬佩那兩個在資料壓縮領域做出了傑出貢獻的以色列人，因為正是他們打破了
Huffman 編碼一統天下的格局，帶給了我們既高效又簡便的“字典模型”。至今
，幾乎我們日常使用的所有通用壓縮工具，象 ARJ，PKZip，WinZip，LHArc，RAR
，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至許多硬體如網絡裝置中内
置的壓縮算法，無一例外，都可以最終歸結為這兩個以色列人的傑出貢獻。
說起來，字典模型的思路相當簡單，我們日常生活中就經常在使用這種壓縮思想。
我們常常跟人說“奧運會”、“IBM”、“TCP”之類的詞彙，說者和聽者都明白它
們指的是“奧林匹克運動會”、“國際商業機器公司”和“傳輸控制協定”，這實
際就是資訊的壓縮。我們之是以可以順利使用這種壓縮方式而不産生語義上的誤解
，是因為在說者和聽者的心中都有一個事先定義好的縮略語字典，我們在對資訊進
行壓縮（說）和解壓縮（聽）的過程中都對字典進行了查詢操作。字典壓縮模型正
是基于這一思路設計實作的。
最簡單的情況是，我們擁有一本預先定義好的字典。例如，我們要對一篇中文文章
進行壓縮，我們手中已經有一本《現代漢語詞典》。那麼，我們掃描要壓縮的文章
，并對其中的句子進行分詞操作，對每一個獨立的詞語，我們在《現代漢語詞典》
查找它的出現位置，如果找到，我們就輸出頁碼和該詞在該頁中的序号，如果沒有
找到，我們就輸出一個新詞。這就是靜态字典模型的基本算法了。
你一定可以發現，靜态字典模型并不是好的選擇。首先，靜态模型的适應性不強，
我們必須為每類不同的資訊建立不同的字典；其次，對靜态模型，我們必須維護信
息量并不算小的字典，這一額外的資訊量影響了最終的壓縮效果。是以，幾乎所有
通用的字典模型都使用了自适應的方式，也就是說，将已經編碼過的資訊作為字典
，如果要編碼的字元串曾經出現過，就輸出該字元串的出現位置及長度，否則輸出
新的字元串。根據這一思路，你能從下面這幅圖中讀出其中包含的原始資訊嗎？
啊，對了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。現在你該大緻明白自
适應字典模型的梗概了吧。好了，下面就讓我們來深入學習字典模型的第一類實作
——LZ77 算法。
滑動的視窗
LZ77 算法在某種意義上又可以稱為“滑動視窗壓縮”，這是由于該算法将一個虛
拟的，可以跟随壓縮程序滑動的視窗作為術語字典，要壓縮的字元串如果在該視窗
中出現，則輸出其出現位置和長度。使用固定大小視窗進行術語比對，而不是在所
有已經編碼的資訊中比對，是因為比對算法的時間消耗往往很多，必須限制字典的
大小才能保證算法的效率；随着壓縮的程序滑動字典視窗，使其中總包含最近編碼
過的資訊，是因為對大多數資訊而言，要編碼的字元串往往在最近的上下文中更容
易找到比對串。
參照下圖，讓我們熟悉一下 LZ77 算法的基本流程。
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 位元組）來說，偏移值基本還是均勻分布的，我們完全可以用固定
的位數來表示它。
編碼 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 值考慮其傾向于視窗後部的規律，我們也可以采用變長的編碼
方法。但這種方式對視窗較小的情況改善并不明顯，有時壓縮效果還不如固定長編
碼。
對三元組的最後一個分量——字元 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
必須是原始偏移（相對視窗左邊），這樣才可以保證解碼程式的順利執行。我們
用下面的代碼将環形偏移還原為原始偏移：
// 由環形 off 得到真正的off(相對于視窗左邊)
// 其中 nLeftOff 為目前與視窗左邊對應的環形偏移值
int GetRealOff(int off)
{
if (off >= nLeftOff)
return off - nLeftOff;
else
return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}
這樣，解碼程式無需考慮環形偏移系統就可以順利高速解碼了。
--
hmisty, hey misty!
H misty
How Much I'm Special To You
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)