采用LZ77算法壓縮數(shù)據(jù)與實(shí)現(xiàn)分析

LZ77簡(jiǎn)介

Ziv和Lempel于1977年發(fā)表題為“順序數(shù)據(jù)壓縮的一個(gè)通用算法（A Universal Algorithm for Sequential Data Compression ）”的論文，論文中描述的算法被后人稱為L(zhǎng)Z77算法。值得說(shuō)的是，LZ77嚴(yán)格意義上來(lái)說(shuō)不是一種算法，而是一種編碼理論。同Huffman編碼一樣，只定義了原理，并沒(méi)有定義如何實(shí)現(xiàn)?；谶@種理論來(lái)實(shí)現(xiàn)的算法才稱為L(zhǎng)Z77算法，或者人們更愿意稱為L(zhǎng)Z77變種。實(shí)際上這類算法已經(jīng)有很多了，比如LZSS、LZB、LZH等。至今，幾乎我們?nèi)粘Ｊ褂玫乃型ㄓ脡嚎s工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR??甚至許多硬件如網(wǎng)絡(luò)設(shè)備中內(nèi)置的壓縮算法，無(wú)一例外，都可以最終歸結(jié)為這兩個(gè)以色列人的杰出貢獻(xiàn)。

LZ77是一種基于字典的算法，它將長(zhǎng)字符串（也稱為短語(yǔ)）編碼成短小的標(biāo)記，用小標(biāo)記代替字典中的短語(yǔ)，從而達(dá)到壓縮的目的。也就是說(shuō)，它通過(guò)用小的標(biāo)記來(lái)代替數(shù)據(jù)中多次重復(fù)出現(xiàn)的長(zhǎng)串方法來(lái)壓縮數(shù)據(jù)。其處理的符號(hào)不一定是文本字符，可以是任意大小的符號(hào)。

短語(yǔ)字典的維護(hù)

不同的基于字典的算法使用不同的方法來(lái)維護(hù)它們的字典。LZ77使用的是一個(gè)前向緩沖區(qū)和一個(gè)滑動(dòng)窗口。

LZ77首先將一部分?jǐn)?shù)據(jù)載入前向緩沖區(qū)。為了便于理解前向緩沖區(qū)如何存儲(chǔ)短語(yǔ)并形成字典，我們將緩沖區(qū)描繪成S1，…，Sn的字符序列，Pb是由字符組成的短語(yǔ)集合。從字符序列S1，…，Sn，組成n個(gè)短語(yǔ)，定義如下：

Pb= {(S1),(S1,S2),…,(S1,…,Sn)}

例如，如果前向緩沖區(qū)包含字符(A,B,D)，那么緩沖區(qū)中的短語(yǔ)為{(A),(A,B),(A,B,D)}。

一旦數(shù)據(jù)中的短語(yǔ)通過(guò)前向緩沖區(qū)，那么它將移動(dòng)到滑動(dòng)窗口中，并變成字典的一部分。為理解短語(yǔ)是如何在滑動(dòng)窗口中表示的，首先，把窗口想象成S1，…，Sm的字符序列，且Pw是由這些字符組成的短語(yǔ)集合。從序列S1，…，Sm產(chǎn)生短語(yǔ)數(shù)據(jù)集合的過(guò)程如下：

Pw= {P1,P2,…,Pm}，其中Pi= {(Si),(Si,Si+1),…,(Si,Si+1,…,Sm)}

例如，如果滑動(dòng)窗口中包含符號(hào)(A,B,C)，那么窗口和字典中的短語(yǔ)為{(A),(A,B),(A,B,C),(B),(B,C),(C)}。

LZ77算法的主要思想就是在前向緩沖區(qū)中不斷尋找能夠與字典中短語(yǔ)匹配的最長(zhǎng)短語(yǔ)。以上面描述的前向緩沖區(qū)和滑動(dòng)窗口為例，其最長(zhǎng)的匹配短語(yǔ)為(A,B)。

壓縮和解壓縮數(shù)據(jù)

前向緩沖區(qū)和滑動(dòng)窗口之間的匹配有兩種情況：要么找到一個(gè)匹配短語(yǔ)，要么找不到匹配的短語(yǔ)。當(dāng)找到最長(zhǎng)的匹配時(shí)，將其編碼成短語(yǔ)標(biāo)記。

短語(yǔ)標(biāo)記包含三個(gè)部分：1、滑動(dòng)窗口中的偏移量（從頭部到匹配開始的前一個(gè)字符）；2、匹配中的符號(hào)個(gè)數(shù)；3、匹配結(jié)束后，前向緩沖區(qū)中的第一個(gè)符號(hào)。

當(dāng)沒(méi)有找到匹配時(shí)，將未匹配的符號(hào)編碼成符號(hào)標(biāo)記。這個(gè)符號(hào)標(biāo)記僅僅包含符號(hào)本身，沒(méi)有壓縮過(guò)程。事實(shí)上，我們將看到符號(hào)標(biāo)記實(shí)際上比符號(hào)多一位，所以會(huì)出現(xiàn)輕微的擴(kuò)展。

一旦把n個(gè)符號(hào)編碼并生成相應(yīng)的標(biāo)記，就將這n個(gè)符號(hào)從滑動(dòng)窗口的一端移出，并用前向緩沖區(qū)中同樣數(shù)量的符號(hào)來(lái)代替它們。然后，重新填充前向緩沖區(qū)。這個(gè)過(guò)程使滑動(dòng)窗口中始終有最新的短語(yǔ)?；瑒?dòng)窗口和前向緩沖區(qū)具體維護(hù)的短語(yǔ)數(shù)量由它們自身的容量決定。

下圖（1）展示了用LZ77算法壓縮字符串的過(guò)程，其中滑動(dòng)窗口大小為8個(gè)字節(jié)，前向緩沖區(qū)大小為4個(gè)字節(jié)。在實(shí)際中，滑動(dòng)窗口典型的大小為4KB（4096字節(jié)）。前向緩沖區(qū)大小通常小于100字節(jié)。

圖（1）：使用LZ77算法對(duì)字符串ABABCBABABCAD進(jìn)行壓縮

我們通過(guò)解碼標(biāo)記和保持滑動(dòng)窗口中符號(hào)的更新來(lái)解壓縮數(shù)據(jù)，其過(guò)程類似于壓縮過(guò)程。當(dāng)解碼每個(gè)標(biāo)記時(shí)，將標(biāo)記編碼成字符拷貝到滑動(dòng)窗口中。每當(dāng)遇到一個(gè)短語(yǔ)標(biāo)記時(shí)，就在滑動(dòng)窗口中查找相應(yīng)的偏移量，同時(shí)查找在那里發(fā)現(xiàn)的指定長(zhǎng)度的短語(yǔ)。每當(dāng)遇到一個(gè)符號(hào)標(biāo)記時(shí)，就生成標(biāo)記中保存的一個(gè)符號(hào)。下圖（2）展示了解壓縮圖（1）中數(shù)據(jù)的過(guò)程。

圖（2）：使用LZ77算法對(duì)圖（1）中壓縮的字符串進(jìn)行解壓縮

LZ77的效率

用LZ77算法壓縮的程度取決于很多因素，例如，選擇滑動(dòng)窗口的大小，為前向緩沖區(qū)設(shè)置的大小，以及數(shù)據(jù)本身的熵。最終，壓縮的程度取決于能匹配的短語(yǔ)的數(shù)量和短語(yǔ)的長(zhǎng)度。大多數(shù)情況下，LZ77比霍夫曼編碼有著更高的壓縮比，但是其壓縮過(guò)程相對(duì)較慢。

用LZ77算法壓縮數(shù)據(jù)是非常耗時(shí)的，國(guó)為要花很多時(shí)間尋找窗口中的匹配短語(yǔ)。然而在通常情況下，LZ77的解壓縮過(guò)程要比霍夫曼編碼的解壓縮過(guò)程耗時(shí)要少。LZ77的解壓縮過(guò)程非?？焓且?yàn)槊總€(gè)標(biāo)記都明確地告訴我們?cè)诰彌_區(qū)中哪個(gè)位置可以讀取到所需要的符號(hào)。事實(shí)上，我們最終只從滑動(dòng)窗口中讀取了與原始數(shù)據(jù)數(shù)量相等的符號(hào)而已。

LZ77的接口定義

lz77_compress

int lz77_compress(const unsigned char *original, unsigned char **compressed, int size);

返回值：如果數(shù)據(jù)壓縮成功，返回壓縮后數(shù)據(jù)的字節(jié)數(shù)；否則返回-1；

描述： 用LZ77算法壓縮緩沖區(qū)original中的數(shù)據(jù)，original包含size個(gè)字節(jié)的空間。壓縮后的數(shù)據(jù)存入緩沖區(qū)compressed中。lz77_compress需要調(diào)用malloc來(lái)動(dòng)態(tài)的為compressed分配存儲(chǔ)空間，當(dāng)這塊空間不再使用時(shí)，由調(diào)用者調(diào)用函數(shù)free來(lái)釋放空間。

復(fù)雜度：O(n)，其中n是原始數(shù)據(jù)中符號(hào)的個(gè)數(shù)。

lz77_uncompress

int lz77_uncompress(const unsigned char *compressed, unsigned char **original);

返回值：如果解壓縮數(shù)據(jù)成功，返回恢復(fù)后數(shù)據(jù)的字節(jié)數(shù)；否則返回-1；

描述： 用LZ77算法解壓縮緩沖區(qū)compressed中的數(shù)據(jù)。假定緩沖區(qū)包含的數(shù)據(jù)之前由lz77_compress壓縮。恢復(fù)后的數(shù)據(jù)存入緩沖區(qū)original中。lz77_uncompress函數(shù)調(diào)用malloc來(lái)動(dòng)態(tài)的為original分配存儲(chǔ)空間。當(dāng)這塊存儲(chǔ)空間不再使用時(shí)，由調(diào)用者調(diào)用函數(shù)free來(lái)釋放空間。

復(fù)雜度：O（n）其中n是原始數(shù)據(jù)中符號(hào)的個(gè)數(shù)。

LZ77的實(shí)現(xiàn)與分析

LZ77算法，通過(guò)一個(gè)滑動(dòng)窗口將前向緩沖區(qū)中的短語(yǔ)編碼成相應(yīng)的標(biāo)記，從而達(dá)到壓縮的目的。在解壓縮的過(guò)程中，將每個(gè)標(biāo)記解碼成短語(yǔ)或符號(hào)本身。要做到這些，必須要不斷地更新窗口，這樣，在壓縮過(guò)程中的任何時(shí)刻，窗口都能按照規(guī)則進(jìn)行編碼。在本節(jié)所有的示例中，原始數(shù)據(jù)中的一個(gè)符號(hào)占一個(gè)字節(jié)。

lz77_compress

lz77_compress操作使用LZ77算法來(lái)壓縮數(shù)據(jù)。首先，它將數(shù)據(jù)中的符號(hào)寫入壓縮數(shù)據(jù)的緩沖區(qū)中，并同時(shí)初始化滑動(dòng)窗口和前向緩沖區(qū)。隨后，前向緩沖區(qū)將用來(lái)加載符號(hào)。

壓縮發(fā)生在一個(gè)循環(huán)中，循環(huán)會(huì)持續(xù)迭代直到處理完所有符號(hào)。使用ipos來(lái)保存原始數(shù)據(jù)中正在處理的當(dāng)前字節(jié)，并用opos來(lái)保存向壓縮數(shù)據(jù)緩沖區(qū)寫入的當(dāng)前位。在循環(huán)的每次迭代中，調(diào)用compare_win來(lái)確定前向緩沖區(qū)與滑動(dòng)窗口中匹配的最長(zhǎng)短語(yǔ)。函數(shù)compare_win返回最長(zhǎng)匹配串的長(zhǎng)度。

當(dāng)找到一個(gè)匹配串時(shí)，compare_win設(shè)置offset為滑動(dòng)窗口中匹配串的位置，同時(shí)設(shè)置next為前向緩沖區(qū)中匹配串后一位的符號(hào)。在這種情況下，向壓縮數(shù)據(jù)中寫入一個(gè)短語(yǔ)標(biāo)記（如圖3-a）。在本節(jié)展示的實(shí)現(xiàn)中，對(duì)于偏移量offset短語(yǔ)標(biāo)記需要12位，這是因?yàn)榛瑒?dòng)窗口的大小為4KB（4096字節(jié)）。此時(shí)短語(yǔ)標(biāo)志需要5位來(lái)表示長(zhǎng)度，因?yàn)樵谝粋€(gè)32字節(jié)的前向緩沖區(qū)中，不會(huì)有匹配串超過(guò)這個(gè)長(zhǎng)度。當(dāng)沒(méi)有找到匹配串時(shí)，compare_win返回，并且設(shè)置next為前向緩沖區(qū)起始處未匹配的符號(hào)。在這種情況下，向壓縮數(shù)據(jù)中寫入一個(gè)符號(hào)（如圖3-b）。無(wú)論向壓縮數(shù)據(jù)中寫入的是一個(gè)短語(yǔ)還是一個(gè)符號(hào)，在實(shí)際寫入標(biāo)記之前，都需要調(diào)用網(wǎng)絡(luò)函數(shù)htonl來(lái)轉(zhuǎn)換串，以保證標(biāo)記是大端格式。這種格式是在實(shí)際壓縮數(shù)據(jù)和解壓縮數(shù)據(jù)時(shí)所要求的。

圖3：LZ77中的短語(yǔ)標(biāo)記（A）和符號(hào)標(biāo)記（B）的結(jié)構(gòu)

一旦將相應(yīng)的標(biāo)記寫入壓縮數(shù)據(jù)的緩沖區(qū)中，就調(diào)整滑動(dòng)窗口和前向緩沖區(qū)。要使數(shù)據(jù)通過(guò)滑動(dòng)窗口，將數(shù)據(jù)從右邊滑入窗口，從左邊滑出窗口。同樣，在前向緩沖區(qū)中也是相同的滑動(dòng)過(guò)程。移動(dòng)的字節(jié)數(shù)與標(biāo)記中編碼的字符數(shù)相等。

lz77_compress的時(shí)間復(fù)雜度為O(n)，其中n是原始數(shù)據(jù)中符號(hào)的個(gè)數(shù)。這是因?yàn)椋瑢?duì)于數(shù)據(jù)中每個(gè)n/c個(gè)編碼的標(biāo)記，其中1/c是一個(gè)代表編碼效率的常量因素，調(diào)用一次compare_win。函數(shù)compare_win運(yùn)行一段固定的時(shí)間，因?yàn)榛瑒?dòng)窗口和前向緩沖區(qū)的大小均為常數(shù)。然而，這些常量比較大，會(huì)對(duì)lz77_compress的總體運(yùn)行時(shí)間產(chǎn)生較大的影響。所以，lz77_compress的時(shí)間復(fù)雜度是O(n)，但其實(shí)際的復(fù)雜度會(huì)受其常量因子的影響。這就解釋了為什么在用lz77進(jìn)行數(shù)據(jù)壓縮時(shí)速度非常慢。

lz77_uncompress

lz77_uncompress操作解壓縮由lz77_compress壓縮的數(shù)據(jù)。首先，該函數(shù)從壓縮數(shù)據(jù)中讀取字符，并初始化滑動(dòng)窗口和前向緩沖區(qū)。

解壓縮過(guò)程在一個(gè)循環(huán)中執(zhí)行，此循環(huán)會(huì)持續(xù)迭代執(zhí)行直到所有的符號(hào)處理完。使用ipos來(lái)保存向壓縮數(shù)據(jù)中寫入的當(dāng)前位，并用opos來(lái)保存寫入恢復(fù)數(shù)據(jù)緩沖區(qū)中當(dāng)前字節(jié)。在循環(huán)的每次迭代過(guò)程中，首先從壓縮數(shù)據(jù)讀取一位來(lái)確定要解碼的標(biāo)記類型。

在解析一個(gè)標(biāo)記時(shí)，如果讀取的首位是1，說(shuō)明遇到了一個(gè)短語(yǔ)標(biāo)記。此時(shí)讀取它的每個(gè)成員，查找滑動(dòng)窗口中的短語(yǔ)，然后將短語(yǔ)寫入恢復(fù)數(shù)據(jù)緩沖區(qū)中。當(dāng)查找每個(gè)短語(yǔ)時(shí)，調(diào)用網(wǎng)絡(luò)函數(shù)ntohl來(lái)保證窗口中的偏移量和長(zhǎng)度的字節(jié)順序是與操作系統(tǒng)匹配的。這個(gè)轉(zhuǎn)換過(guò)程是必要的，因?yàn)閺膲嚎s數(shù)據(jù)中讀取出來(lái)的偏移量和長(zhǎng)度是大端格式的。在數(shù)據(jù)被拷貝到滑動(dòng)窗口之前，前向緩沖區(qū)被用做一個(gè)臨時(shí)轉(zhuǎn)換區(qū)來(lái)保存數(shù)據(jù)。最后，寫入該標(biāo)記編碼的匹配的符號(hào)。如果讀取的標(biāo)記的首位是0，說(shuō)明遇到了一個(gè)符號(hào)標(biāo)記。在這種情況下，將該標(biāo)記編碼的匹配符號(hào)寫入恢復(fù)數(shù)據(jù)緩沖區(qū)中。

一旦將解碼的數(shù)據(jù)寫入恢復(fù)數(shù)據(jù)的緩沖區(qū)中，就調(diào)整滑動(dòng)窗口。要將數(shù)據(jù)通過(guò)滑動(dòng)窗口，將數(shù)據(jù)從右邊滑入窗口，從左邊滑出窗口。移動(dòng)的字節(jié)數(shù)與從標(biāo)記中解碼的字符數(shù)相等。

lz77_uncompress的時(shí)間復(fù)雜度為O(n)，其中n是原始數(shù)據(jù)中符號(hào)的個(gè)數(shù)。