２．實(shí)現(xiàn)部分
如果世界上從沒有一個(gè)壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個(gè)可以壓縮大多數(shù)格式、內(nèi)容的數(shù)據(jù)的程序，當(dāng)我們著手要做這樣一個(gè)程序的時(shí)候，會發(fā)現(xiàn)有很多的難題需要我們?nèi)ヒ粋€(gè)個(gè)解決，下面將逐個(gè)描述這些難題，并詳細(xì)分析 zip 算法是如何解決這些難題的，其中很多問題帶有普遍意義，比如查找匹配，比如數(shù)組排序等等，這些都是說不盡的話題，讓我們深入其中，做一番思考。
我們前面說過，對于短語式重復(fù)，我們用“重復(fù)距當(dāng)前位置的距離”和“重復(fù)的長度”這兩個(gè)數(shù)字來表示這一段重復(fù)，以實(shí)現(xiàn)壓縮，現(xiàn)在問題來了，一個(gè)字節(jié)能表示的數(shù)字大小為 0 －255，然而重復(fù)出現(xiàn)的位置和重復(fù)的長度都可能超過 255，事實(shí)上，二進(jìn)制數(shù)的位數(shù)確定下來后，所能表示的數(shù)字大小的范圍是有限的，ｎ位的二進(jìn)制數(shù)能表示的最大值是２的ｎ次方減１，如果位數(shù)取得太大，對于大量的短匹配，可能不但起不到壓縮作用，反而增大了最終的結(jié)果。針對這種情況，有兩種不同的算法來解決這個(gè)問題，它們是兩種不同的思路。一種稱為 lz77 算法，這是一種很自然的思路：限制這兩個(gè)數(shù)字的大小，以取得折衷的壓縮效果。例如距離取 15 位，長度取 8 位，這樣，距離的最大取值為 32 k - 1，長度的最大取值為 255，這兩個(gè)數(shù)字占 23 位，比三個(gè)字節(jié)少一位，是符合壓縮的要求的。讓我們在頭腦中想象一下 lz77 算法壓縮進(jìn)行時(shí)的情況，會出現(xiàn)有意思的模型：
最遠(yuǎn)匹配位置－＞ 當(dāng)前處理位置－＞
───┸─────────────────╂─────────────＞壓縮進(jìn)行方向
已壓縮部分 ┃ 未壓縮部分
在最遠(yuǎn)匹配位置和當(dāng)前處理位置之間是可以用來查找匹配的“字典”區(qū)域，隨著壓縮的進(jìn)行，“字典”區(qū)域從待壓縮文件的頭部不斷地向后滑動(dòng)，直到達(dá)到文件的尾部，短語式壓縮也就結(jié)束了。
解壓縮也非常簡單：
┎────────拷貝────────┒
匹配位置 ┃ 當(dāng)前處理位置 ┃
┃＜──匹配長度──＞┃ ┠─────∨────┨
───┸──────────┸───────╂──────────┸─＞解壓進(jìn)行方向
已解壓部分 ┃ 未解壓部分
不斷地從壓縮文件中讀出匹配位置值和匹配長度值，把已解壓部分的匹配內(nèi)容拷貝到解壓文件尾部，遇到壓縮文件中那些壓縮時(shí)未能得到匹配，而是直接保存的單、雙字節(jié)，解壓時(shí)只要直接拷貝到文件尾部即可，直到整個(gè)壓縮文件處理完畢。
lz77算法模型也被稱為“滑動(dòng)字典”模型或“滑動(dòng)窗口”模型。
另有一種lzw算法對待壓縮文件中存在大量簡單匹配的情況進(jìn)行了完全不同的算法設(shè)計(jì)，它只用一個(gè)數(shù)字來表示一段短語，下面來描述一下lzw的壓縮解壓過程，然后來綜合比較兩者的適用情況。
lzw的壓縮過程：
1) 初始化一個(gè)指定大小的字典，把 256 種字節(jié)取值加入字典。
2) 在待壓縮文件的當(dāng)前處理位置尋找在字典中出現(xiàn)的最長匹配，輸出該匹配在字典中的序號。
3) 如果字典沒有達(dá)到最大容量，把該匹配加上它在待壓縮文件中的下一個(gè)字節(jié)加入字典。
4) 把當(dāng)前處理位置移到該匹配后。
5) 重復(fù) 2、3、4 直到文件輸出完畢。
lzw 的解壓過程：
1) 初始化一個(gè)指定大小的字典，把 256 種字節(jié)取值加入字典。
2) 從壓縮文件中順序讀出一個(gè)字典序號，根據(jù)該序號，把字典中相應(yīng)的數(shù)據(jù)拷貝到解壓文件尾部。
3) 如果字典沒有達(dá)到最大容量，把前一個(gè)匹配內(nèi)容加上當(dāng)前匹配的第一個(gè)字節(jié)加入字典。
4) 重復(fù) 2、3 兩步直到壓縮文件處理完畢。
從 lzw 的壓縮過程，我們可以歸納出它不同于 lz77 算法的一些主要特點(diǎn)：
1) 對于一段短語，它只輸出一個(gè)數(shù)字，即字典中的序號。（這個(gè)數(shù)字的位數(shù)決定了字典的最大容量，當(dāng)它的位數(shù)取得太大時(shí)，比如 24 位以上，對于短匹配占多數(shù)的情況，壓縮率可能很低。取得太小時(shí)，比如 8 位，字典的容量受到限制。所以同樣需要取舍。）
2) 對于一個(gè)短語，比如 abcd ，當(dāng)它在待壓縮文件中第一次出現(xiàn)時(shí)，ab 被加入字典，第二次出現(xiàn)時(shí)，abc 被加入字典，第三次出現(xiàn)時(shí)，abcd 才會被加入字典，對于一些長匹配，它必須高頻率地出現(xiàn)，并且字典有較大的容量，才會被最終完整地加入字典。相應(yīng)地，lz77 只要匹配在“字典區(qū)域”中存在，馬上就可以直接使用。
3) 設(shè) lzw 的“字典序號”取 n 位，它的最大長度可以達(dá)到 2 的 n 次方；設(shè) lz77 的“匹配長度”取 n 位，“匹配距離”取 d 位，它的最大長度也是 2 的 n 次方，但還要多輸出 d 位（d 至少不小于 n），從理論上說 lzw 每輸出一個(gè)匹配只要 n 位，不管是長匹配還是短匹配，壓縮率要比 lz77 高至少一倍，但實(shí)際上，lzw 的字典中的匹配長度的增長由于各匹配互相打斷，很難達(dá)到最大值。而且雖然 lz77 每一個(gè)匹配都要多輸出 d 位，但 lzw 每一個(gè)匹配都要從單字節(jié)開始增長起，對于種類繁多的匹配，lzw 居于劣勢。
可以看出，在多數(shù)情況下，lz77 擁有更高的壓縮率，而在待壓縮文件中占絕大多數(shù)的是些簡單的匹配時(shí)，lzw 更具優(yōu)勢，GIF 就是采用了 lzw 算法來壓縮背景單一、圖形簡單的圖片。zip 是用來壓縮通用文件的，這就是它采用對大多數(shù)文件有更高壓縮率的 lz77 算法的原因。
接下來 zip 算法將要解決在“字典區(qū)域”中如何高速查找最長匹配的問題。
（注：以下關(guān)于技術(shù)細(xì)節(jié)的描述是以 gzip 的公開源代碼為基礎(chǔ)的，如果需要完整的代碼，可以在 gzip 的官方網(wǎng)站
www.gzip.org 下載。下面提到的每一個(gè)問題，都首先介紹最直觀簡單的解決方法，然后指出這種方法的弊端所在，最后介紹 gzip 采用的做法，這樣也許能使讀者對 gzip 看似復(fù)雜、不直觀的做法的意義有更好的理解。）
最直觀的搜索方式是順序搜索：以待壓縮部分的第一個(gè)字節(jié)與窗口中的每一個(gè)字節(jié)依次比較，當(dāng)找到一個(gè)相等的字節(jié)時(shí)，再比較后續(xù)的字節(jié)…… 遍歷了窗口后得出最長匹配。gzip 用的是被稱作“哈希表”的方法來實(shí)現(xiàn)較高效的搜索。“哈希（hash）”是分散的意思，把待搜索的數(shù)據(jù)按照字節(jié)值分散到一個(gè)個(gè)“桶”中，搜索時(shí)再根據(jù)字節(jié)值到相應(yīng)的“桶”中去尋找。短語式壓縮的最短匹配為 3 個(gè)字節(jié)，gzip 以 3 個(gè)字節(jié)的值作為哈希表的索引，但 3 個(gè)字節(jié)共有 2 的 24 次方種取值，需要 16M 個(gè)桶，桶里存放的是窗口中的位置值，窗口的大小為 32K，所以每個(gè)桶至少要有大于兩個(gè)字節(jié)的空間，哈希表將大于 32M，作為 90 年代開發(fā)的程序，這個(gè)要求是太大了，而且隨著窗口的移動(dòng)，哈希表里的數(shù)據(jù)會不斷過時(shí)，維護(hù)這么大的表，會降低程序的效率，gzip 定義哈希表為 2 的 15 次方（32K）個(gè)桶，并設(shè)計(jì)了一個(gè)哈希函數(shù)把 16M 種取值對應(yīng)到 32K 個(gè)桶中，不同的值被對應(yīng)到相同的桶中是不可避免的，哈希函數(shù)的任務(wù)是 1.使各種取值盡可能均勻地分布到各個(gè)桶中，避免許多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。2.函數(shù)的計(jì)算盡可能地簡單，因?yàn)槊看巍安迦搿焙汀八褜ぁ惫１矶家獔?zhí)行哈希函數(shù)，哈希函數(shù)的復(fù)雜度直接影響程序的執(zhí)行效率，容易想到的哈希函數(shù)是取 3 個(gè)字節(jié)的左邊（或右邊）15 位二進(jìn)制值，但這樣只要左邊（或右邊）2 個(gè)字節(jié)相同，就會被放到同一個(gè)桶中，而 2 個(gè)字節(jié)相同的概率是比較高的，不符合“平均分布”的要求。gzip 采用的算法是：A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8) （說明：A 指 3 個(gè)字節(jié)中的第 1 個(gè)字節(jié)，B 指第 2 個(gè)字節(jié)，C 指第 3 個(gè)字節(jié)，A(4,5) 指第一個(gè)字節(jié)的第 4,5 位二進(jìn)制碼，“^”是二進(jìn)制位的異或操作，“+”是“連接”而不是“加”，“^”優(yōu)先于“+”）這樣使 3 個(gè)字節(jié)都盡量“參與”到最后的結(jié)果中來，而且每個(gè)結(jié)果值 h 都等于 ((前1個(gè)h << 5) ^ c)取右 15 位，計(jì)算也還簡單。
哈希表的具體實(shí)現(xiàn)也值得探討,因?yàn)闊o法預(yù)先知道每一個(gè)“桶”會存放多少個(gè)元素，所以最簡單的，會想到用鏈表來實(shí)現(xiàn)：哈希表里存放著每個(gè)桶的第一個(gè)元素，每個(gè)元素除了存放著自身的值，還存放著一個(gè)指針，指向同一個(gè)桶中的下一個(gè)元素，可以順著指針鏈來遍歷該桶中的每一個(gè)元素，插入元素時(shí)，先用哈希函數(shù)算出該放到第幾個(gè)桶中，再把它掛到相應(yīng)鏈表的最后。這個(gè)方案的缺點(diǎn)是頻繁地申請和釋放內(nèi)存會降低運(yùn)行速度；內(nèi)存指針的存放占據(jù)了額外的內(nèi)存開銷。有更少內(nèi)存開銷和更快速的方法來實(shí)現(xiàn)哈希表，并且不需要頻繁的內(nèi)存申請和釋放：gzip 在內(nèi)存中申請了兩個(gè)數(shù)組，一個(gè)叫 head[]，一個(gè)叫 pre[]，大小都為 32K，根據(jù)當(dāng)前位置 strstart 開始的 3 個(gè)字節(jié)，用哈希函數(shù)計(jì)算出在 head[] 中的位置 ins_h，然后把 head[ins_h] 中的值記入 pre[strstart]，再把當(dāng)前位置 strstart 記入 head[ins_h]。隨著壓縮的進(jìn)行，head[]里記載著最近的可能的匹配的位置（如果有匹配的話，head[ins_h]不為 0），pre[]中的所有位置與原始數(shù)據(jù)的位置相對應(yīng)，但每一個(gè)位置保存的值是前一個(gè)最近的可能的匹配的位置。（“可能的匹配”是指哈希函數(shù)計(jì)算出的 ins_h 相同。）順著 pre[] 中的指示找下去，直到遇到 0，可以得到所有匹配在原始數(shù)據(jù)中的位置，0 表示不再有更遠(yuǎn)的匹配。
接下來很自然地要觀察 gzip 具體是如何判斷哈希表中數(shù)據(jù)的過時(shí)，如何清理哈希表的，因?yàn)?pre[] 里只能存放 32K 個(gè)元素，所以這項(xiàng)工作是必須要做的。
gzip 從原始文件中讀出兩個(gè)窗口大小的內(nèi)容（共 64K 字節(jié)）到一塊內(nèi)存中，這塊內(nèi)存也是一個(gè)數(shù)組，稱作 Window[]；申請 head[]、pre[] 并清零；strstart 置為 0。然后 gzip 邊搜索邊插入，搜索時(shí)通過計(jì)算 ins_h，檢查 head[] 中是否有匹配，如果有匹配，判斷 strstart 減 head[] 中的位置是否大于 1 個(gè)窗口的大小，如果大于 1 個(gè)窗口的大小，就不到 pre[] 中去搜索了，因?yàn)?pre[] 中保存的位置更遠(yuǎn)了，如果不大于，就順著 pre[] 的指示到 Window[] 中逐個(gè)匹配位置開始，逐個(gè)字節(jié)與當(dāng)前位置的數(shù)據(jù)比較，以找出最長匹配，pre[] 中的位置也要判斷是否超出一個(gè)窗口，如遇到超出一個(gè)窗口的位置或者 0 就不再找下去，找不到匹配就輸出當(dāng)前位置的單個(gè)字節(jié)到另外的內(nèi)存（輸出方法在后文中會介紹），并把 strstart 插入哈希表，strstart 遞增，如果找到了匹配，就輸出匹配位置和匹配長度這兩個(gè)數(shù)字到另外的內(nèi)存中，并把 strstart 開始的，直到 strstart + 匹配長度 為止的所有位置都插入哈希表，strstart += 匹配長度。插入哈希表的方法為：
pre[strstart % 32K] = head[ins_h];
head[ins_h] = strstart;
可以看出，pre[] 是循環(huán)利用的，所有的位置都在一個(gè)窗口以內(nèi)，但每一個(gè)位置保存的值不一定是一個(gè)窗口以內(nèi)的。在搜索時(shí)，head[] 和 pre[] 中的位置值對應(yīng)到 pre[] 時(shí)也要 % 32K。當(dāng) Window[] 中的原始數(shù)據(jù)將要處理完畢時(shí)，要把 Window[] 中后一窗的數(shù)據(jù)復(fù)制到前一窗，再讀取 32K 字節(jié)的數(shù)據(jù)到后一窗，strstart -= 32K，遍歷 head[]，值小于等于 32K 的，置為 0，大于 32K 的，-= 32K；pre[] 同 head[] 一樣處理。然后同前面一樣處理新一窗的數(shù)據(jù)。
分析：現(xiàn)在可以看到，雖然 3 個(gè)字節(jié)有 16M 種取值，但實(shí)際上一個(gè)窗口只有 32K 個(gè)取值需要插入哈希表，由于短語式重復(fù)的存在，實(shí)際只有 < 32K 種取值插入哈希表的 32K 個(gè)“桶”中，而且哈希函數(shù)又符合“平均分布”的要求，所以哈希表中實(shí)際存在的“沖突”一般不會多，對搜索效率的影響不大。可以預(yù)計(jì)，在“一般情況”下，每個(gè)“桶”中存放的數(shù)據(jù)，正是我們要找的。哈希表在各種搜索算法中，實(shí)現(xiàn)相對的比較簡單，容易理解，“平均搜索速度”最快，哈希函數(shù)的設(shè)計(jì)是搜索速度的關(guān)鍵，只要符合“平均分布”和“計(jì)算簡單”，就常常能成為諸種搜索算法中的首選，所以哈希表是最流行的一種搜索算法。但在某些特殊情況下，它也有缺點(diǎn)，比如：1.當(dāng)鍵碼 k 不存在時(shí)，要求找出小于 k 的最大鍵碼或大于 k 的最小鍵碼，哈希表無法有效率地滿足這種要求。2.哈希表的“平均搜索速度”是建立在概率論的基礎(chǔ)上的，因?yàn)槭孪炔荒茴A(yù)知待搜索的數(shù)據(jù)集合，我們只能“信賴”搜索速度的“平均值”，而不能“保證”搜索速度的“上限”。在同人類性命攸關(guān)的應(yīng)用中（如醫(yī)療或宇航領(lǐng)域），將是不合適的。這些情況及其他一些特殊情況下，我們必須求助其他“平均速度”較低，但能滿足相應(yīng)的特殊要求的算法。（見《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第3卷 排序與查找）。幸而“在窗口中搜索匹配字節(jié)串”不屬于特殊情況。
時(shí)間與壓縮率的平衡：
gzip 定義了幾種可供選擇的 level，越低的 level 壓縮時(shí)間越快但壓縮率越低，越高的 level 壓縮時(shí)間越慢但壓縮率越高。
不同的 level 對下面四個(gè)變量有不同的取值：
nice_length
max_chain
max_lazy
good_length
nice_length：前面說過，搜索匹配時(shí)，順著 pre[] 的指示到 Window[] 中逐個(gè)匹配位置開始，找出最長匹配，但在這過程中，如果遇到一個(gè)匹配的長度達(dá)到或超過 nice_length，就不再試圖尋找更長的匹配。最低的 level 定義 nice_length 為 8，最高的 level 定義 nice_length 為 258（即一個(gè)字節(jié)能表示的最大短語匹配長度 3 + 255）。
max_chain：這個(gè)值規(guī)定了順著 pre[] 的指示往前回溯的最大次數(shù)。最低的 level 定義 max_chain 為 4，最高的 level 定義 max_chain 為 4096。當(dāng) max_chain 和 nice_length 有沖突時(shí)，以先達(dá)到的為準(zhǔn)。
max_lazy：這里有一個(gè)懶惰匹配（lazy match）的概念，在輸出當(dāng)前位置（strstart）的匹配之前，gzip 會去找下一個(gè)位置（strstart + 1）的匹配，如果下一個(gè)匹配的長度比當(dāng)前匹配的長度更長，gzip 就放棄當(dāng)前匹配，只輸出當(dāng)前位置處的首個(gè)字節(jié)，然后再查找 strstart + 2 處的匹配，這樣的方式一直往后找，如果后一個(gè)匹配比前一個(gè)匹配更長，就只輸出前一個(gè)匹配的首字節(jié)，直到遇到前一個(gè)匹配長于后一個(gè)匹配，才輸出前一個(gè)匹配。
gzip 作者的思路是，如果后一個(gè)匹配比前一個(gè)匹配更長，就犧牲前一個(gè)匹配的首字節(jié)來換取后面的大于等于1的額外的匹配長度。
max_lazy 規(guī)定了，如果匹配的長度達(dá)到或超過了這個(gè)值，就直接輸出，不再管后一個(gè)匹配是否更長。最低的4級 level 不做懶惰匹配，第5級 level 定義 max_lazy 為 4，最高的 level 定義 max_lazy 為 258。
good_length：這個(gè)值也和懶惰匹配有關(guān)，如果前一個(gè)匹配長度達(dá)到或超過 good_length，那在尋找當(dāng)前的懶惰匹配時(shí)，回溯的最大次數(shù)減小到 max_chain 的 1/4，以減少當(dāng)前的懶惰匹配花費(fèi)的時(shí)間。第5級 level 定義 good_length 為 4（這一級等于忽略了 good_length），最高的 level 定義 good_length 為 32。
分析：懶惰匹配有必要嗎？可以改進(jìn)嗎？
gzip 的作者是無損壓縮方面的專家，但是世界上沒有絕對的權(quán)威，吾愛吾師，更愛真理。我覺得 gzip 的作者對懶惰匹配的考慮確實(shí)不夠周詳。只要是進(jìn)行了認(rèn)真客觀的分析，誰都有權(quán)利提出自己的觀點(diǎn)。
采用懶惰匹配，需要對原始文件的更多的位置查找匹配，時(shí)間肯定增加了許多倍，但壓縮率的提高在總體上十分有限。在幾種情況下，它反而增長了短語壓縮的結(jié)果，所以如果一定要用懶惰匹配，也應(yīng)該改進(jìn)一下算法，下面是具體的分析。
1. 連續(xù)3次以上找到了更長的匹配，就不應(yīng)該單個(gè)輸出前面的那些字節(jié)，而應(yīng)該作為匹配輸出。
2. 于是，如果連續(xù)找到更長的匹配的次數(shù)大于第一個(gè)匹配的長度，對于第一個(gè)匹配，相當(dāng)于沒有做懶惰匹配。
3. 如果小于第一個(gè)匹配的長度但大于2，就沒有必要作懶惰匹配，因?yàn)檩敵龅目偸莾蓚€(gè)匹配。
4. 所以找到一個(gè)匹配后，最多只需要向后做 2 次懶惰匹配，就可以決定是輸出第一個(gè)匹配，還是輸出1（或 2）個(gè)首字節(jié)加后面的匹配了。
5. 于是，對于一段原始字節(jié)串，如果不做懶惰匹配時(shí)輸出兩個(gè)匹配（對于每個(gè)匹配，距離占15位二進(jìn)制數(shù)，長度占8位二進(jìn)制數(shù)，加起來約占3字節(jié)，輸出兩個(gè)匹配約需要6字節(jié)），做了懶惰匹配如果有改進(jìn)的話，將是輸出1或2個(gè)單字節(jié)加上1個(gè)匹配（也就是約4或5字節(jié)）。這樣，懶惰匹配可以使某些短語壓縮的結(jié)果再縮短1/3到1/6。
6. 再觀察這樣一個(gè)例子：
1232345145678[當(dāng)前位置]12345678
不用懶惰匹配，約輸出6字節(jié)，用懶惰匹配，約輸出7字節(jié)，由于使用了懶惰匹配，把更后面的一個(gè)匹配拆成了兩個(gè)匹配。（如果 678 正好能歸入再后面的一個(gè)匹配，那懶惰匹配可能是有益的。）
7. 綜合考慮各種因素（匹配數(shù)和未匹配的單雙字節(jié)在原始文件中所占的比例，后一個(gè)匹配長度大于前一個(gè)匹配長度的概率，等等），經(jīng)過改進(jìn)的懶惰匹配算法，對總的壓縮率即使有貢獻(xiàn)，也仍是很小的，而且也仍然很有可能會降低壓縮率。再考慮到時(shí)間的確定的明顯的增加與壓縮率的不確定的微弱的增益，也許最好的改進(jìn)是果斷地放棄懶惰匹配。