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

張永棠

（廣東東軟學院計算機科學與技術系，廣東佛山528225）

?

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

張永棠

（廣東東軟學院計算機科學與技術系，廣東佛山528225）

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

關鍵詞：通信編碼；無損壓縮；LZ77；算法設計；TUNEDBM

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

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

1 LZ77壓縮算法

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

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

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

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

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

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

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

2 TUNEDBM算法

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

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

3一種改進的LZ77無損壓縮算法

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

TUNEDBM直接應用到的LZ77中存在以下幾個方面的問題：

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

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

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

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

3.1預處理階段

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

3.2查找最長匹配串

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

圖1滑動窗口查找匹配字符串示意圖

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

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

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

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

算法：FindLongestStr

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

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

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

4實驗結果及分析

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

表1改進前后的LZ77算法壓縮性能對比

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

參考文獻：

［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］劉存良,張秉權,黃河燕.基于嵌入式系統(tǒng)的改進快速壓縮算法［J］.兵工自動化, 2003, 22（1）: 46- 48.

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

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

【責任編輯：周紹纓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

文章編號：1008- 0171（2016）01- 0057- 05

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

收稿日期：2015-09-20

中圖分類號：TP301.6

文獻標志碼：A