6     110 10    7     110 11    8    1110 000    9    1110 001</pre><p>其實，如果對 off值考慮其傾向于窗口后部的規律，我們也可以采用變長的編碼方法。但這種方式對窗口較小的情況改善并不明顯，有時壓縮效果還不如固定長編碼。</p><p>對三元組的最后一個分量——字符 c，因為其分布并無規律可循，我們只能老老實實地用8 個二進制位對其編碼。</p><p>根據上面的敘述，相信你一定也能寫出高效的編碼和解碼程序了。</p><p><strong>另一種輸出方式</strong></p><p>LZ77的原始算法采用三元組輸出每一個匹配串及其后續字符，即使沒有匹配，我們仍然需要輸出一個len = 0 的三元組來表示單個字符。試驗表明，這種方式對于某些特殊情況（例如同一字符不斷重復的情形）有著較好的適應能力。但對于一般數據，我們還可以設計出另外一種更為有效的輸出方式：將匹配串和不能匹配的單個字符分別編碼、分別輸出，輸出匹配串時不同時輸出后續字符。</p><p>我們將每一個輸出分成匹配串和單個字符兩種類型，并首先輸出一個二進制位對其加以區分。例如，輸出0 表示下面是一個匹配串，輸出 1表示下面是一個單個字符。</p><p>之后，如果要輸出的是單個字符，我們直接輸出該字符的字節值，這要用8 個二進制位。也就是說，我們輸出一個單個的字符共需要9 個二進制位。</p><p>如果要輸出的是匹配串，我們按照前面的方法依次輸出off 和 len。對 off，我們可以輸出定長編碼，也可以輸出變長前綴碼，對len 我們輸出變長前綴碼。有時候我們可以對匹配長度加以限制，例如，我們可以限制最少匹配3 個字符。因為，對于 2 個字符的匹配串，我們使用匹配串的方式輸出并不一定比我們直接輸出2 個單個字符（需要 18位）節省空間（是否節省取決于我們采用何種編碼輸出off 和 len）。</p><p>這種輸出方式的優點是輸出單個字符的時候比較節省空間。另外，因為不強求每次都外帶一個后續字符，可以適應一些較長匹配的情況。</p><p><strong>如何查找匹配串</strong></p><p>在滑動窗口中查找最長的匹配串，大概是 LZ77算法中的核心問題。容易知道，LZ77算法中空間和時間的消耗集中于對匹配串的查找算法。每次滑動窗口之后，都要進行下一個匹配串的查找，如果查找算法的時間效率在O(n<sup>2</sup>) 或者更高，總的算法時間效率就將達到O(n<sup>3</sup>)，這是我們無法容忍的。正常的順序匹配算法顯然無法滿足我們的要求。事實上，我們有以下幾種可選的方案。</p><p>1、限制可匹配字符串的最大長度（例如 20個字節），將窗口中每一個 20 字節長的串抽取出來，按照大小順序組織成二叉有序樹。在這樣的二叉有序樹中進行字符串的查找，其效率是很高的。樹中每一個節點大小是20(key) + 4(off) + 4(left child) + 4(right child) = 32。樹中共有MAX_WND_SIZE - 19 個節點，假如窗口大小為 4096字節，樹的大小大約是 130k字節。空間消耗也不算多。這種方法對匹配串長度的限制雖然影響了壓縮程序對一些特殊數據（又很長的匹配串）的壓縮效果，但就平均性能而言，壓縮效果還是不錯的。</p><p>2、將窗口中每個長度為 3 （視情況也可取 2 或4）的字符串建立索引，先在此索引中匹配，之后對得出的每個可匹配位置進行順序查找，直到找到最長匹配字符串。因為長度為3 的字符串可以有 256<sup>3</sup>種情況，我們不可能用靜態數組存儲該索引結構。使用Hash 表是一個明智的選擇。我們可以僅用MAX_WND_SIZE - 1 的數組存儲每個索引點，Hash函數的參數當然是字符串本身的 3 個字符值了，Hash函數算法及 Hash之后的散列函數很容易設計。每個索引點之后是該字符串出現的所有位置，我們可以使用單鏈表來存儲每一個位置。值得注意的是，對一些特殊情況比如aaaaaa...之類的連續字串，字符串 aaa有很多連續出現位置，但我們無需對其中的每一個位置都進行匹配，只要對最左邊和最右邊的位置操作就可以了。解決的辦法是在鏈表節點中紀錄相同字符連續出現的長度，對連續的出現位置不再建立新的節點。這種方法可以匹配任意長度的字符串，壓縮效果要好一些，但缺點是查找耗時多于第一種方法。</p><p>3、使用字符樹( trie )來對窗口內的字符串建立索引，因為字符的取值范圍是0 - 255，字符樹本身的層次不可能太多，3 - 4層之下就應該換用其他的數據結構例如 Hash表等。這種方法可以作為第二種方法的改進算法出現，可以提高查找速度，但空間的消耗較多。</p><p>如果對窗口中的數據進行索引，就必然帶來一個索引位置表示的問題，即我們在索引結構中該往偏移項中存儲什么數據：首先，窗口是不斷向后滑動的，我們每次將窗口向后滑動一個位置，索引結構就要作相應的更新，我們必須刪除那些已經移動出窗口的數據，并增加新的索引信息。其次，窗口不斷向后滑動的事實使我們無法用相對窗口左邊界的偏移來表示索引位置，因為隨著窗口的滑動，每個被索引的字符串相對窗口左邊界的位置都在改變，我們無法承擔更新所有索引位置的時間消耗。</p><p>解決這一問題的辦法是，使用一種可以環形滾動的偏移系統來建立索引，而輸出匹配字符串時再將環形偏移還原為相對窗口左邊界的真正偏移。讓我們用圖形來說明，窗口剛剛達到最大時，環形偏移和原始偏移系統相同：</p><pre>偏移：     0 1 2 3 4 ......                                              Max          |--------------------------------------------------------------|環形偏移： 0 1 2 3 4 ......                                              Max</pre><p>窗口向后滑動一個字節后，滑出窗口左端的環形偏移0 被補到了窗口右端：</p><pre>偏移：     0 1 2 3 4 ......                                              Max          |--------------------------------------------------------------|環形偏移： 1 2 3 4 5 ......                                           Max 0</pre><p>窗口再滑動 3 個子節后，偏移系統的情況是：</p><pre>偏移：     0 1 2 3 4 ......                                              Max          |--------------------------------------------------------------|環形偏移： 4 5 6 7 8......                                      Max 0 1 2 3</pre><p>依此類推。</p><p>我們在索引結構中保存環形偏移，但在查找到匹配字符串后，輸出的匹配位置off 必須是原始偏移（相對窗口左邊），這樣才可以保證解碼程序的順利執行。我們用下面的代碼將環形偏移還原為原始偏移：</p><pre>// 由環形 off 得到真正的off(相對于窗口左邊)// 其中 nLeftOff 為當前與窗口左邊對應的環形偏移值int GetRealOff(int off){    if (off &gt;= nLeftOff)        return off - nLeftOff;    else        return (_MAX_WINDOW_SIZE - (nLeftOff - off));}</pre><p>這樣，解碼程序無需考慮環形偏移系統就可以順利高速解碼了。</p><p><strong>資源</strong></p><p>結合上面的討論，典型的 LZ77算法應當不難實現，我們本章給出的源碼是一個較為特殊的實現。</p><p>示例程序 lz77.exe使用對匹配串和單個字符分類輸出的模型，輸出匹配串時，off采用定長編碼，len 采用γ編碼。索引結構采用 2字節長字符串的索引，使用 256 * 256大小的靜態數組存儲索引點，每個索引點指向一個位置鏈表。鏈表節點考慮了對aaaaa... 之類的重復串的優化。</p><p>示例程序的獨特之處在于使用了 64k大小的固定長度窗口，窗口不做滑動（因此不需要環形偏移系統，也節省了刪除索引點的時間）。壓縮函數每次只對最多64k 長的數據進行壓縮，主函數將原始文件分成 64k大小的塊逐個壓縮存儲。使用這種方法首先可以增大匹配的概率，字符串可以在64k 空間內任意尋找最大匹配串，以此提高壓縮效率。其次，這種方法有利于實現解壓縮的同步。也就是說，利用這種方法分塊壓縮的數據，很容易從原始文件中間的任何一個位置開始解壓縮，這尤其適用于全文檢索系統中全文信息的保存和隨機讀取。</p><p>結合上述示例程序，王笨笨開發了可壓縮多個文件并可同步（隨機）解壓縮的文件級接口，但此接口并非自由代碼(freecode)。如果需要可以和王笨笨聯系。</p><p>示例程序 lz77 的所有源文件被包裝在文件 <ahref="src/lz77.zip">lz77.zip</a> 中，由王笨笨編寫，在Visual C++ 5.0 環境下編譯通過。其使用方法是：</p><p>壓縮： lz77 c 源文件名 壓縮文件名</p><p>解壓縮： lz77 d 壓縮文件名 源文件名</p><p>　</p><div align="center"><center><address>    <a href="Chapter4.htm">第四章</a> <a href="Chapter6.htm">第六章</a></address></center></div><p align="center">　</p><div align="right"><address>    <a href="mailto:wangyg@contextfree.net">有問題嗎？有建議嗎？快給王笨笨寫信</a></address></div><div align="right"><address>    <strong>章節書簽：</strong><a href="default.htm">前言</a>    <a href="content.htm">目錄</a> <a href="Chapter1.htm">1</a>    <a href="Chapter2.htm">2</a> <a href="Chapter3.htm">3</a> <a    href="Chapter4.htm">4</a> <a href="Chapter5.htm">5</a> <a    href="Chapter6.htm">6</a> <a href="Chapter7.htm">7</a> <a    href="Chapter8.htm">8</a> <a href="Chapter9.htm">9</a> <a    href="Chapter10.htm">10</a> <a href="Chapter11.htm">11</a> <a    href="Chapter12.htm">12</a> </address></div></body></html>