6     110 10
    7     110 11
    8    1110 000
    9    1110 001</pre>

<p>其實，如果對 off
值考慮其傾向于窗口后部的規(guī)律，我們也可以采用變長的編碼方法。但這種方式對窗口較小的情況改善并不明顯，有時壓縮效果還不如固定長編碼。</p>

<p>對三元組的最后一個分量——字符 c，因為其分布并無規(guī)律可循，我們只能老老實實地用
8 個二進制位對其編碼。</p>

<p>根據(jù)上面的敘述，相信你一定也能寫出高效的編碼和解碼程序了。</p>

<p><strong>另一種輸出方式</strong></p>

<p>LZ77
的原始算法采用三元組輸出每一個匹配串及其后續(xù)字符，即使沒有匹配，我們?nèi)匀恍枰敵鲆粋€
len = 0 的三元組來表示單個字符。試驗表明，這種方式對于某些特殊情況（例如同一字符不斷重復的情形）有著較好的適應能力。但對于一般數(shù)據(jù)，我們還可以設計出另外一種更為有效的輸出方式：將匹配串和不能匹配的單個字符分別編碼、分別輸出，輸出匹配串時不同時輸出后續(xù)字符。</p>

<p>我們將每一個輸出分成匹配串和單個字符兩種類型，并首先輸出一個二進制位對其加以區(qū)分。例如，輸出
0 表示下面是一個匹配串，輸出 1
表示下面是一個單個字符。</p>

<p>之后，如果要輸出的是單個字符，我們直接輸出該字符的字節(jié)值，這要用
8 個二進制位。也就是說，我們輸出一個單個的字符共需要
9 個二進制位。</p>

<p>如果要輸出的是匹配串，我們按照前面的方法依次輸出
off 和 len。對 off，我們可以輸出定長編碼，也可以輸出變長前綴碼，對
len 我們輸出變長前綴碼。有時候我們可以對匹配長度加以限制，例如，我們可以限制最少匹配
3 個字符。因為，對于 2 個字符的匹配串，我們使用匹配串的方式輸出并不一定比我們直接輸出
2 個單個字符（需要 18
位）節(jié)省空間（是否節(jié)省取決于我們采用何種編碼輸出
off 和 len）。</p>

<p>這種輸出方式的優(yōu)點是輸出單個字符的時候比較節(jié)省空間。另外，因為不強求每次都外帶一個后續(xù)字符，可以適應一些較長匹配的情況。</p>

<p><strong>如何查找匹配串</strong></p>

<p>在滑動窗口中查找最長的匹配串，大概是 LZ77
算法中的核心問題。容易知道，LZ77
算法中空間和時間的消耗集中于對匹配串的查找算法。每次滑動窗口之后，都要進行下一個匹配串的查找，如果查找算法的時間效率在
O(n<sup>2</sup>) 或者更高，總的算法時間效率就將達到
O(n<sup>3</sup>)，這是我們無法容忍的。正常的順序匹配算法顯然無法滿足我們的要求。事實上，我們有以下幾種可選的方案。</p>

<p>1、限制可匹配字符串的最大長度（例如 20
個字節(jié)），將窗口中每一個 20 字節(jié)長的串抽取出來，按照大小順序組織成二叉有序樹。在這樣的二叉有序樹中進行字符串的查找，其效率是很高的。樹中每一個節(jié)點大小是
20(key) + 4(off) + 4(left child) + 4(right child) = 32。樹中共有
MAX_WND_SIZE - 19 個節(jié)點，假如窗口大小為 4096
字節(jié)，樹的大小大約是 130k
字節(jié)。空間消耗也不算多。這種方法對匹配串長度的限制雖然影響了壓縮程序?qū)σ恍┨厥鈹?shù)據(jù)（又很長的匹配串）的壓縮效果，但就平均性能而言，壓縮效果還是不錯的。</p>

<p>2、將窗口中每個長度為 3 （視情況也可取 2 或
4）的字符串建立索引，先在此索引中匹配，之后對得出的每個可匹配位置進行順序查找，直到找到最長匹配字符串。因為長度為
3 的字符串可以有 256<sup>3</sup>
種情況，我們不可能用靜態(tài)數(shù)組存儲該索引結構。使用
Hash 表是一個明智的選擇。我們可以僅用
MAX_WND_SIZE - 1 的數(shù)組存儲每個索引點，Hash
函數(shù)的參數(shù)當然是字符串本身的 3 個字符值了，Hash
函數(shù)算法及 Hash
之后的散列函數(shù)很容易設計。每個索引點之后是該字符串出現(xiàn)的所有位置，我們可以使用單鏈表來存儲每一個位置。值得注意的是，對一些特殊情況比如
aaaaaa...之類的連續(xù)字串，字符串 aaa
有很多連續(xù)出現(xiàn)位置，但我們無需對其中的每一個位置都進行匹配，只要對最左邊和最右邊的位置操作就可以了。解決的辦法是在鏈表節(jié)點中紀錄相同字符連續(xù)出現(xiàn)的長度，對連續(xù)的出現(xiàn)位置不再建立新的節(jié)點。這種方法可以匹配任意長度的字符串，壓縮效果要好一些，但缺點是查找耗時多于第一種方法。</p>

<p>3、使用字符樹( trie )來對窗口內(nèi)的字符串建立索引，因為字符的取值范圍是
0 - 255，字符樹本身的層次不可能太多，3 - 4
層之下就應該換用其他的數(shù)據(jù)結構例如 Hash
表等。這種方法可以作為第二種方法的改進算法出現(xiàn)，可以提高查找速度，但空間的消耗較多。</p>

<p>如果對窗口中的數(shù)據(jù)進行索引，就必然帶來一個索引位置表示的問題，即我們在索引結構中該往偏移項中存儲什么數(shù)據(jù)：首先，窗口是不斷向后滑動的，我們每次將窗口向后滑動一個位置，索引結構就要作相應的更新，我們必須刪除那些已經(jīng)移動出窗口的數(shù)據(jù)，并增加新的索引信息。其次，窗口不斷向后滑動的事實使我們無法用相對窗口左邊界的偏移來表示索引位置，因為隨著窗口的滑動，每個被索引的字符串相對窗口左邊界的位置都在改變，我們無法承擔更新所有索引位置的時間消耗。</p>

<p>解決這一問題的辦法是，使用一種可以環(huán)形滾動的偏移系統(tǒng)來建立索引，而輸出匹配字符串時再將環(huán)形偏移還原為相對窗口左邊界的真正偏移。讓我們用圖形來說明，窗口剛剛達到最大時，環(huán)形偏移和原始偏移系統(tǒng)相同：</p>

<pre>偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
環(huán)形偏移： 0 1 2 3 4 ......                                              Max</pre>

<p>窗口向后滑動一個字節(jié)后，滑出窗口左端的環(huán)形偏移
0 被補到了窗口右端：</p>

<pre>偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
環(huán)形偏移： 1 2 3 4 5 ......                                           Max 0</pre>

<p>窗口再滑動 3 個子節(jié)后，偏移系統(tǒng)的情況是：</p>

<pre>偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
環(huán)形偏移： 4 5 6 7 8......                                      Max 0 1 2 3</pre>

<p>依此類推。</p>

<p>我們在索引結構中保存環(huán)形偏移，但在查找到匹配字符串后，輸出的匹配位置
off 必須是原始偏移（相對窗口左邊），這樣才可以保證解碼程序的順利執(zhí)行。我們用下面的代碼將環(huán)形偏移還原為原始偏移：</p>

<pre>// 由環(huán)形 off 得到真正的off(相對于窗口左邊)
// 其中 nLeftOff 為當前與窗口左邊對應的環(huán)形偏移值
int GetRealOff(int off)
{
    if (off &gt;= nLeftOff)
        return off - nLeftOff;
    else
        return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}</pre>

<p>這樣，解碼程序無需考慮環(huán)形偏移系統(tǒng)就可以順利高速解碼了。</p>

<p><strong>資源</strong></p>

<p>結合上面的討論，典型的 LZ77
算法應當不難實現(xiàn)，我們本章給出的源碼是一個較為特殊的實現(xiàn)。</p>

<p>示例程序 lz77.exe
使用對匹配串和單個字符分類輸出的模型，輸出匹配串時，off
采用定長編碼，len 采用γ編碼。索引結構采用 2
字節(jié)長字符串的索引，使用 256 * 256
大小的靜態(tài)數(shù)組存儲索引點，每個索引點指向一個位置鏈表。鏈表節(jié)點考慮了對
aaaaa... 之類的重復串的優(yōu)化。</p>

<p>示例程序的獨特之處在于使用了 64k
大小的固定長度窗口，窗口不做滑動（因此不需要環(huán)形偏移系統(tǒng)，也節(jié)省了刪除索引點的時間）。壓縮函數(shù)每次只對最多
64k 長的數(shù)據(jù)進行壓縮，主函數(shù)將原始文件分成 64k
大小的塊逐個壓縮存儲。使用這種方法首先可以增大匹配的概率，字符串可以在
64k 空間內(nèi)任意尋找最大匹配串，以此提高壓縮效率。其次，這種方法有利于實現(xiàn)解壓縮的同步。也就是說，利用這種方法分塊壓縮的數(shù)據(jù)，很容易從原始文件中間的任何一個位置開始解壓縮，這尤其適用于全文檢索系統(tǒng)中全文信息的保存和隨機讀取。</p>

<p>結合上述示例程序，王笨笨開發(fā)了可壓縮多個文件并可同步（隨機）解壓縮的文件級接口，但此接口并非自由代碼(free
code)。如果需要可以和王笨笨聯(lián)系。</p>

<p>示例程序 lz77 的所有源文件被包裝在文件 <a
href="src/lz77.zip">lz77.zip</a> 中，由王笨笨編寫，在
Visual C++ 5.0 環(huán)境下編譯通過。其使用方法是：</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>
    有問題嗎？有建議嗎？快給王笨笨寫信：wangyg@contextfree.net
</address>
</div><div align="right">

<address>
    <strong>章節(jié)書簽：</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>