張永棠

（廣東東軟學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，廣東佛山528225）

?

一種改進(jìn)的LZ77無損數(shù)據(jù)壓縮算法設(shè)計(jì)

張永棠

（廣東東軟學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，廣東佛山528225）

摘要：研究了LZ77無損數(shù)據(jù)壓縮算法的原理，在對(duì)LZ77各種改進(jìn)算法進(jìn)行深入分析的基礎(chǔ)上，結(jié)合TUNEDBM單模式匹配算法，提出了一種新的改進(jìn)的LZ77無損數(shù)據(jù)壓縮算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的LZ77壓縮率比原LZ77稍有降低，但在壓縮時(shí)間有很明顯的優(yōu)勢(shì)，尤其當(dāng)文件較小時(shí)，這種優(yōu)勢(shì)體現(xiàn)得更加明顯。

關(guān)鍵詞：通信編碼；無損壓縮；LZ77；算法設(shè)計(jì)；TUNEDBM

隨著大數(shù)據(jù)和云計(jì)算的應(yīng)用，給互聯(lián)網(wǎng)數(shù)據(jù)的存儲(chǔ)和傳輸帶來了更大的挑戰(zhàn)。應(yīng)用數(shù)據(jù)壓縮技術(shù)解決這一難題是重要手段。為了達(dá)到最好的壓縮效果，無損壓縮法（也叫熵編碼）是一種最常用的壓縮編碼方法。目前無損壓縮主要有兩大分支，一種是基于字符概率統(tǒng)計(jì)的，如Huffma等；一種是基于字典的，如LZ系列［1］。

現(xiàn)在的字典壓縮算法大都可以追溯到由ZIV和LEMPEL［1-2］提出的LZ77和LZ78算法。日常使用的通用壓縮工具有WinZip，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR等，此外，許多網(wǎng)絡(luò)設(shè)備中內(nèi)置的壓縮程序都可以歸結(jié)為這些算法及其變種。雖然現(xiàn)有的LZ78其壓縮思想有較大變化，它采用了保存先前所遇到的字符串的字典方法來取代傳統(tǒng)的滑動(dòng)窗口。由于字典中的表項(xiàng)很少，彌補(bǔ)初期的低效，逐漸顯出自己的優(yōu)勢(shì)。但是LZ78算法實(shí)現(xiàn)起來較為復(fù)雜，而且需要額外的內(nèi)存開銷，這對(duì)資源有限且處理能力不足的平臺(tái)數(shù)據(jù)壓縮并不適合，比如單片機(jī)。對(duì)LZ77進(jìn)行改進(jìn)，可使其能實(shí)現(xiàn)嵌入式平臺(tái)的數(shù)據(jù)壓縮。

1 LZ77壓縮算法

LZ77壓縮是一種基于字典及滑動(dòng)窗的無損壓縮技術(shù)，廣泛應(yīng)用于通信傳輸。LZ77的基本原理是：以經(jīng)常出現(xiàn)的字母組合（或較長的字符串）構(gòu)建字典中的數(shù)據(jù)項(xiàng)，并且使用較短的數(shù)字（或符號(hào)）編碼來代替比較復(fù)雜的數(shù)據(jù)項(xiàng)。數(shù)據(jù)壓縮時(shí)，將從待壓縮數(shù)據(jù)中讀入的源數(shù)據(jù)與字典中的數(shù)據(jù)項(xiàng)進(jìn)行匹配，從中檢索出相應(yīng)的代碼并輸出。從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。

LZ77算法執(zhí)行流程如下：

步驟1：從輸入的待壓縮數(shù)據(jù)的起始位置，讀取未編碼的源數(shù)據(jù)，從滑動(dòng)窗口的字典數(shù)據(jù)項(xiàng)中查找最長的匹配字符串。若結(jié)果為T，則執(zhí)行步驟2，若結(jié)果為F，則執(zhí)行步驟3；

步驟2：輸出函數(shù)F（off，len，c）。其中，off為滑動(dòng)窗口邊界的偏移，len為可匹配的長度，c為下一個(gè)字符。然后將窗口向后滑動(dòng)到len++，繼續(xù)步驟1；

步驟3：輸出函數(shù)F（0，0，c），其中c為下一個(gè)字符。并且窗口向后滑動(dòng)（len + 1）個(gè)字符，執(zhí)行步驟1。

從上面對(duì)LZ77算法的分析可以看到，LZ77算法是二叉樹遍歷查找最優(yōu)良的字符串匹配，改變以往的逐一文本比對(duì)，提高了LZ77的壓縮速度。該匹配算法的時(shí)間復(fù)雜度可以表示為O（n*q），其中n為滑動(dòng)窗口編號(hào)，并且執(zhí)行n++，q為平均可匹配長度。如果n大到一定程度，則這種壓縮速度會(huì)下降到讓人無法接受的程度，則對(duì)實(shí)時(shí)性要求較高的嵌入式平臺(tái)不能勝任。

因此，很多壓縮程序都對(duì)LZ77進(jìn)行了改進(jìn)，提高搜索的速度。應(yīng)用得較多的一種是用二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)來改進(jìn)，這也是LZSS對(duì)LZ77進(jìn)行的一個(gè)關(guān)鍵改進(jìn)。建立二叉搜索樹的方法的確對(duì)查找匹配串的速度有很多的提高，但是需要耗費(fèi)一定的空間去存儲(chǔ)這棵二叉樹結(jié)構(gòu)，并且需要不斷維護(hù)二叉搜索樹，增加了程序的復(fù)雜性和時(shí)間耗費(fèi)［3］。有人將KMP應(yīng)用到LZ77的字符串查找中，但是KMP本身實(shí)現(xiàn)起來較為復(fù)雜，不能真正提高LZ77的壓縮速度。本文提出的壓縮算法將LZ77與BM單模式匹配算法結(jié)合起來，可以有效提高LZ77的壓縮速度。

2 TUNEDBM算法

BM算法是一種比較新穎的單模式匹配算法，其基本思想是從右向左的把模式同文本做比較［4］。基于BM算法主要有3種算法：QS算法、HORSPOOL算法、TUNEDBM算法，它們都是BM算法的簡化。其中TUNEDBM被證明是單模式匹配算法中最快的算法［5］。BM算法只使用了壞字符規(guī)則，在搜索階段只查找待壓縮模式串的最后一個(gè)字符。如果不匹配則指針向前一個(gè)字符移動(dòng)，直到找到它。

采用BadCharacter對(duì)字符表P中字符的偏移值進(jìn)行計(jì)算，并將計(jì)算結(jié)果在跳躍表bmBc中存儲(chǔ)并對(duì)比。若待壓縮的字符沒有在表P中出現(xiàn)，偏移值為m；否則偏移值為m-i-1（i為輸入字符在表P中的位置），表示如下:

3一種改進(jìn)的LZ77無損壓縮算法

LZ77算法中的history窗口就相當(dāng)于TUNEDBM中的目標(biāo)串T，lookahead窗口的內(nèi)容就相當(dāng)于模式串P，在history窗口中查找lookahead的最長匹配串的過程其實(shí)就相當(dāng)于模式匹配［5］。但是TUNEDBM并不能直接應(yīng)用到LZ77中。

TUNEDBM直接應(yīng)用到的LZ77中存在以下幾個(gè)方面的問題：

（1）TUNEDBM算法中，字符表P的長度是固定的，是在匹配操作前確定的。所以可以用模式串的最后一個(gè)字符和正文中的字符進(jìn)行比較。而LZ77中的lookahead匹配串的長度是未知的，最長的匹配串的長度是在窗口匹配完后才確定。不知道模式串最后一個(gè)字符，就不能運(yùn)用TUNEDBM的查找思想；

（2）TUNEDBM算法中，需要首先對(duì)模式串進(jìn)行預(yù)處理，也就是使用壞字符規(guī)則，以計(jì)算每字符在失配時(shí)滑動(dòng)的長度。由于LZ77中的待匹配串預(yù)先不能確定，就無法使用壞字符規(guī)則進(jìn)行預(yù)處理；

（3）TUNEDBM算法返回的是匹配是否成功和成功的匹配位置，而LZ77搜索算法要尋找的是最長匹配串長度和匹配的位置。

針對(duì)上面的問題，必須對(duì)TUNEDBM算法實(shí)現(xiàn)做必要的調(diào)整。調(diào)整的思路主要是這樣的：事先并不計(jì)算失匹配函數(shù)，而是當(dāng)比較失敗時(shí)再計(jì)算失配字符的滑動(dòng)距離。剛開始查找時(shí)，讓模式串P的長度m 為0，內(nèi)容是整個(gè)未編碼的字符串。當(dāng)找到更長的匹配串時(shí)，更新m的值，這樣當(dāng)將窗口遍歷時(shí)，就可以找到最長的匹配串。

3.1預(yù)處理階段

改進(jìn)后的LZ77壓縮算法不是直接計(jì)算出待壓縮數(shù)據(jù)流的滑動(dòng)距離，而是采用預(yù)處理的方式在待壓縮數(shù)據(jù)流中找到的最長匹配值m。當(dāng)出現(xiàn)失配字符ch時(shí)，調(diào)用skip（）函數(shù)計(jì)算出其最大滑動(dòng)距離，直接滑動(dòng)。改進(jìn)后LZ77壓縮的skip（）函數(shù)算法描述如下:

3.2查找最長匹配串

在窗口中查找最長匹配串的過程和TunedBM算法非常類似。設(shè)當(dāng)前的窗口為T，待編碼數(shù)據(jù)流為P，最長匹配字符長度為m，滑動(dòng)窗口的長度為n。下面對(duì)匹配成功與不成功進(jìn)行分析，如圖1所示。

圖1滑動(dòng)窗口查找匹配字符串示意圖

假設(shè)待編碼數(shù)據(jù)流P[m-1]位置的字符與窗口T中相應(yīng)字符進(jìn)行匹配比較。若匹配不成功，則調(diào)用skip（）函數(shù)，求出窗口位置為T[j+m-1]的最大滑動(dòng)距離s，將j的指針地址右移到j(luò)+s的位置，繼續(xù)重復(fù)這個(gè)過程直至讀取的待編碼字符為’/0’匹配結(jié)束；若成功，則從匹配的字符串的頭部開始逐一匹配，并記錄下匹配長度tml，直到數(shù)據(jù)流位置P[tml-1]與窗口位置T[j+tml-1]匹配失敗。根據(jù)tml與m的返回值：

若tml≤m，則查找更長的匹配串失敗，地址指針指向字符T[j+m]，繼續(xù)進(jìn)行匹配；

若tml>m，則查找更長的匹配串成功，更新匹配長度m=tml，調(diào)用skip（）函數(shù)求出T[j+tml-1]位置的最大滑動(dòng)距離，文件指針j=j+1，繼續(xù)進(jìn)行匹配；

從上面描述可以看出，改進(jìn)后的LZ77算法如果某一個(gè)字符比較失敗后，立即停止從后往前依次匹配，轉(zhuǎn)而跳到數(shù)據(jù)流的開關(guān)位置進(jìn)行匹配，從而提高數(shù)據(jù)編碼搜索速度，達(dá)到快速的查找最長匹配串的目的。整個(gè)查找最長匹配串算法描述如下：

算法：FindLongestStr

輸入：窗口T，待編碼字符串P，窗口長度max_win_size

輸出：最長匹配串長度len和窗口偏移

返回最長匹配串長度和窗口偏移；

4實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證改進(jìn)后LZ77壓縮算法的效果，對(duì)改進(jìn)前后的壓縮效率進(jìn)行了對(duì)比，如表1所示。本實(shí)驗(yàn)中，取滑動(dòng)窗口長度為1024，并用變長編碼Gamma編碼來表示匹配串的長度值，這樣可以提高壓縮率。

表1改進(jìn)前后的LZ77算法壓縮性能對(duì)比

從表1可以看出，改進(jìn)的LZ77壓縮率比原LZ77稍有降低，但是改進(jìn)后的LZ77比原LZ77在壓縮時(shí)間有很明顯的優(yōu)勢(shì)，尤其當(dāng)文件較小時(shí)，這種優(yōu)勢(shì)體現(xiàn)得更加明顯。當(dāng)文件較大時(shí)，兩種壓縮耗時(shí)都較長，改進(jìn)的LZ77時(shí)間優(yōu)勢(shì)也并不明顯，這是由LZ77本身壓縮算法的局限性決定的。本文提出的壓縮算法適合于實(shí)時(shí)性要求較高的場(chǎng)合，比如基本于嵌入式系統(tǒng)的數(shù)據(jù)采集與傳輸，一次壓縮的數(shù)據(jù)并不大，對(duì)實(shí)時(shí)性特別要求。

參考文獻(xiàn)：

［1］ZIV J, LEMPELA. A universal algorithm for sequential data compression［J］. IEEE Transactions on Information Theory,1977,23（5）: 337- 342.

［2］ZIVJ, LEMPELA. Compression ofindividual sequence via variable- rate coding［J］. IEEE Transactions on Information Theory, 1978, 24（5）: 530- 536.

［3］劉存良,張秉權(quán),黃河燕.基于嵌入式系統(tǒng)的改進(jìn)快速壓縮算法［J］.兵工自動(dòng)化, 2003, 22（1）: 46- 48.

［4］BOYER R S, MOORE J S. Afast stringsearchingalgorithm［J］. Commun ACM, 1977, 20（10）: 762- 772.

［5］巫喜紅,凌捷.單模式匹配算法研究［J］.微計(jì)算機(jī)信息, 2006, 22（8）: 202- 204.

【責(zé)任編輯：周紹纓410154121@qq.com】

An improved LZ77 lossless data compression algorithm design

ZHANGYong- tang
（Department of Computer Science and Technology, Guangdong Neusoft Institute, Foshan 528225, China）

Abstract:This paper studies the principle of LZ77 lossless data compression algorithm based on the in- depth analysis of various LZ77 algorithms combining with TUNEDBMsingle mode matching algorithm, and proposes a new improved LZ77 lossless data compression algorithm. Experimental results show that the improved LZ77 compression ratiois slightlylower than that ofthe original LZ77, and the improved LZ77 is more obvious than the original LZ77 in the compression time, especiallywhen the file is small, this advantage is more obvious.

Keywords:Communications encoding; lossless compression; LZ77; algorithmdesign; TUNEDBM

文章編號(hào)：1008- 0171（2016）01- 0057- 05

作者簡介：張永棠（1981-），江西南昌人，廣東東軟學(xué)院副教授。

收稿日期：2015-09-20

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A