#lz77

我們敬佩那兩個在數據壓縮領域做出了傑出貢獻的以色列人，因為正是他們打破了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( log 2 ( MAX_WND_SIZE ))

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

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

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

b = 2 m

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

r = x - qb - 1

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

值xm = 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( log 2 x )，則編碼的前一部分是q個1加一個0，後一部分是q位長的二進制數，其值等於x - 2 q。γ編碼表如下：

值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(n 2 )或者更高，總的算法時間效率就將達到O(n 3 )，這是我們無法容忍的。正常的順序匹配算法顯然無法滿足我們的要求。事實上，我們有以下幾種可選的方案。

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的字符串可以有256 3種情況，我們不可能用靜態數組存儲該索引結構。使用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));}

這樣，解碼程序無需考慮環形偏移系統就可以順利高速解碼了。

資源

結合上面的討論，典型的LZ77 算法應當不難實現，我們本章給出的源碼是一個較為特殊的實現。

示例程序lz77.exe 使用對匹配串和單個字符分類輸出的模型，輸出匹配串時，off 採用定長編碼，len 採用γ編碼。索引結構採用2 字節長字符串的索引，使用256 * 256 大小的靜態數組存儲索引點，每個索引點指向一個位置鍊錶。鍊錶節點考慮了對aaaaa... 之類的重複串的優化。