孫 超， 周國祥

（合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，安徽 合肥 230009）

0 引 言

進(jìn)入信息時代，人們逐漸對數(shù)據(jù)壓縮已不再陌生，數(shù)據(jù)壓縮軟件已成為計算機(jī)的必備軟件，而一些不易被人們察覺的數(shù)據(jù)壓縮也滲透進(jìn)入生活中。大多數(shù)多媒體文件標(biāo)準(zhǔn)中都內(nèi)嵌了壓縮算法，例如，數(shù)碼相機(jī)拍攝的JPG格式圖片是由BMP格式文件壓縮而成，但體積只有原來的1／10；MP3格式音頻文件也是由CD格式文件壓縮而來，體積也只有原來的1／10。近20年，LZ系列無損數(shù)據(jù)壓縮算法日趨成熟，在實踐中被廣泛應(yīng)用，包括著名的軟件 WINRAR、WINZIP。該系列算法以LZ77衍生的LZSS算法和LZ78衍生的LZW算法最突出，在日常使用中最多。

1 優(yōu)化思想分析

近年來由于信息技術(shù)的飛速發(fā)展，計算機(jī)軟硬件性能都得到大幅度提高，壓縮／解壓縮的計算能力已不再是考慮的重點。而網(wǎng)絡(luò)傳輸?shù)钠款i現(xiàn)象日益顯現(xiàn)，高壓縮率更符合實際的需求。使用無損數(shù)據(jù)壓縮算法時，主流的LZW算法或LZSS算法對不同數(shù)據(jù)文件壓縮的效果有時候區(qū)別很大，這是因為無損數(shù)據(jù)壓縮算法的收斂速度還與數(shù)據(jù)文件本身屬性有關(guān)。網(wǎng)絡(luò)上傳輸量極大的圖形界面文檔文件、圖像圖形文件、超文本文件等大多屬于LZW算法收斂速度快的數(shù)據(jù)文件［1］，所以本文采用LZW算法為主體的方法，結(jié)合LZSS算法中一些巧妙的方法，形成一個新的算法應(yīng)用于當(dāng)前網(wǎng)絡(luò)。

LZ77算法由文獻(xiàn)［2］提出，該算法是把數(shù)據(jù)壓縮從Huffman和算術(shù)編碼的思路中解放出來。LZ77算法巧妙運用類似于查字典的方法，運用了近鄰原則，在壓縮的數(shù)據(jù)流中設(shè)2個窗口，即滑動窗口和前向緩沖區(qū)。

將2個窗口比較后編碼，使用1個三元組〈offset（偏移量）、length（匹配長度）、char（字符）〉代替輸出。

LZSS算法是由LZ77算法發(fā)展而來，改變了對滑動窗口查詢的方法，由順序遍歷變成了二叉樹遍歷，大大提高了匹配的查詢速度；另外，將三元組的輸出方式改變成二元組〈offset（偏移量）、length（匹配長度）〉的方式。

LZ78對LZ77做了修改，最大的變化就是改變了字典的構(gòu)成方式［3］。LZ77使用臨近的已編碼部分作為字典；而LZ78的字典是一個潛在的先前所見短語的無序序列，先將數(shù)據(jù)流與字典中的記錄項進(jìn)行對比，當(dāng)查詢到不能匹配的數(shù)據(jù)時，則將新的結(jié)果添加到字典中，再輸出原查詢到的最長的匹配。

LZW是LZ78的變種，最大的特點是預(yù)先對所有單字符（256個）進(jìn)行了加載，這樣輸出中就不會有單字節(jié)。

2 優(yōu)化算法原理

LZW算法有2個致命的弱點，一是自適應(yīng)速度緩慢；二是舊字典滿了后清除，再重新建立字典，初期壓縮率會急劇下降。

LZSS算法雖然可以獲得較高且穩(wěn)定的壓縮率，但是由于使用的是二叉樹進(jìn)行遍歷查詢，造成壓縮速度過慢，并且對大文件的壓縮率不夠理想。

LZW算法必須有足夠的前置代碼建立一個足夠大的字典后，才能達(dá)到最佳的壓縮率，而LZSS算法較好地克服了這一難題。

例如字符串“ABCDABCD”，LZW算法需要“ABCD”出現(xiàn)4次才能將整個字符串添加到字典中，而LZSS在“ABCD”出現(xiàn)第2次就可以對其進(jìn)行整體壓縮。文獻(xiàn)［1］提出過一種組合使用LZ78和LZ77的思想，定義一個相似結(jié)構(gòu)的字典表，在字典構(gòu)建初期使用LZ77算法，當(dāng)字典足夠大時再進(jìn)行字典轉(zhuǎn)換使用LZ78算法，該思想規(guī)避了2種算法的弱點。

本文受其啟發(fā)，并且將該思想進(jìn)行了發(fā)展，吸收2種算法構(gòu)造字典方法的優(yōu)點［4－5］，運用偏移編碼的方法，通過生成一個字典表和一個與之關(guān)聯(lián)的字典編碼表，創(chuàng)新地修改了壓縮的輸出方式，進(jìn)一步提高了壓縮效率。

改進(jìn)的壓縮算法生成字典的基礎(chǔ)方法是使用LZW算法的字典構(gòu)造法，同時在字典構(gòu)造的過程中變通地引入LZSS算法的滑動窗口偏移編碼思想，將滑動窗口演變成一張與字典每個記錄都有關(guān)聯(lián)的字典編碼表（表在壓縮／解壓縮過程中建立，不需要傳輸）。壓縮數(shù)據(jù)的輸出是通過字典和關(guān)聯(lián)的字典編碼表共同決定，首先輸出字典記錄，然后通過關(guān)聯(lián)找出偏移匹配項，最終組合輸出壓縮數(shù)據(jù)。

通過對輸出方式和字典結(jié)構(gòu)的優(yōu)化，優(yōu)化算法可以在更高效地獲得2種算法優(yōu)點的同時，避免構(gòu)建字典過程中2種算法的頻繁切換。特別是在字典建立初期和中期，最大限度地提高了壓縮率；其次偏移匹配有效地增加了各個字典記錄的聯(lián)系，可以實現(xiàn)對原文中相鄰的字符串進(jìn)行跨字符串壓縮，在相同的規(guī)模下字典將包含更大的信息量，有效地減少了字典重建的次數(shù)，始終保持著較高壓縮率的狀態(tài)。

字典編碼表的偏移匹配借助于字典的Hash查找，極大地提高了查找的速度［6］，提高了整體的壓縮速度。

實現(xiàn)這個方法的核心就是改變原來的字典結(jié)構(gòu)［6］，添加1個編碼字節(jié)偏移位置索引的屬性，建立1個四元組字典：

long Order－index；／＊ 編碼字節(jié)偏移位置索引＊／｝

再建立1個字典編碼表來維護(hù)1個與當(dāng)前字典對應(yīng)的已編碼字符窗口，每讀入1個待壓縮字符時，字典編碼表也實時更新，字典滿后初始化時也會將字典編碼表初始化，壓縮／解壓縮時可以通過字典快速索引，找到其在字典編碼表中的相對位置。例如，Order－index＝3，則表示該符號代碼所對應(yīng)的后續(xù)偏移匹配從字典編碼表中第3位開始比較。

此時，算法輸出發(fā)生了變化，有2種輸出方式，為了區(qū)別2種輸出格式的輸出數(shù)據(jù)，在輸出前需要增加標(biāo)志位用來標(biāo)記是哪種輸出格式［7］。一種是原LZW算法輸出方式，使用“11”作為標(biāo)志；另一種是新增的算法輸出格式，使用“10”作為標(biāo)志。對于第2種輸出格式，為了增強(qiáng)算法的適應(yīng)性，本文引入?yún)?shù)調(diào)節(jié)機(jī)制，在LZW字典最大匹配位置后加入了L位，用來表示后續(xù)匹配的字符偏移長度。

例如，字符串“ABCDEFABCDEFABCDEF”。使用一般LZW壓縮過程和結(jié)果見表1所列，壓縮后的輸出為“ABCDEF（259）（261）（263）（265）（262）F”，字符串在字典中添加了11組數(shù)據(jù)，并且輸出需要12組數(shù)據(jù)。

表1 LZW算法字典

優(yōu)化的壓縮算法過程和結(jié)果見表2所列（設(shè)定匹配最大值L＜8），同時維護(hù)后完整的字典編碼見表3所列，壓縮后的輸出為“ABCDEF（258＋7）262”，字符串在字典中只添加了8組數(shù)據(jù)，并且輸出只需要8組數(shù)據(jù)。

比較可知，對于相同的數(shù)據(jù)，優(yōu)化的方法減少了壓縮后的輸出數(shù)據(jù)，同時有效地減少了字典中存儲記錄數(shù)量，優(yōu)化方法是有效的。

具體壓縮算法流程如圖1所示，其中L為一次匹配成功的偏移長度。

表2 優(yōu)化的LZW算法字典

表3 完整的字典編碼

圖1 優(yōu)化算法流程

改進(jìn)算法的核心是字典編碼表的維護(hù)和偏移編碼統(tǒng)計，在前7個步驟中，字典中沒有前綴的壓縮記錄，每次都是向字典編碼表中寫入1個剛剛接收的待壓縮編碼字符，見表4所列。

表4 前7個步驟后字典編碼

第8個步驟中，字典編碼表會分2個部分接收待編碼字符。

（1）第1部分來源為構(gòu)造字典記錄項。由于有前綴記錄可以壓縮，將壓縮部分的字符維護(hù)到字典編碼表中，結(jié)果見表5所列。

表5 第8個步驟構(gòu)造字典后字典編碼

（2）第2部分來源為壓縮輸出計算偏移編碼匹配。首先查詢前綴字符，本例中前綴記錄編碼Hash－code為259，字典編碼表匹配首位置Order－index為3，比較得3位置的字符與后綴字符是一樣的，選擇使用改進(jìn)的壓縮數(shù)據(jù)輸出方式，并且開始統(tǒng)計偏移字符的匹配情況，讀入下一個待壓縮的字符“D”，寫入字典編碼表中，見表6所列。判斷與前綴記錄的字典編碼表匹配首位置加1位置（即4位置）相同，匹配統(tǒng)計累加。

表6 第8個步驟偏移匹配第1次成功后字典編碼

如此反復(fù)，最終第8個步驟完成時，形成的字典編碼見表7所列。

表7 第8個步驟后字典編碼

3 算法性能分析

3.1 壓縮比RC

為方便與信源的熵值做比較，引入壓余率的概念。壓余率P代表源文件每字節(jié)壓縮后平均所占的位數(shù)，它與壓縮比的轉(zhuǎn)換為即壓余率越低，壓縮比越高。

改進(jìn)算法的壓余率主要由字典和字典編碼表決定。改進(jìn)算法字典相似于LZW算法的字典構(gòu)造，而字典編碼表則是由LZSS算法的滑動窗口演化而來，故提取這2種算法壓余率作為性能分析的標(biāo)準(zhǔn)。

（1）LZSS算法總的壓余率：

其中，Nw代表滑動窗口緩沖區(qū)的大??；LS為預(yù)定最大匹配長度；Nm為總的拆分的段數(shù)；Ln是源文件的長度。

（2）LZW算法總的壓余率：

其中，Lc為單位編碼位長度；Y為信源字符串；A為信源字符集合。

優(yōu)化算法的壓縮分解成壓縮初期R1和壓縮中后期R22個部分。

改進(jìn)算法總的壓余率為：

對于改進(jìn)的壓縮算法，壓縮初期，壓余率P1依靠字典編碼表可達(dá)到和LZSS算法初期一樣低的壓余率，再通過字典記錄項的匹配又可能部分降低了壓余率，故P1＜；在壓縮中后期，壓余率P2依靠字典可以獲得一樣低的壓余率，并且可以查詢字典編碼表信息進(jìn)行跨記錄項的匹配壓縮，故P2＜。

改進(jìn)的壓縮算法的壓余率將低于LZW算法和LZSS算法，以及它們?nèi)我獾淖顑?yōu)組合算法。

3.2 壓縮速度

壓縮速度主要取決于對字典的搜索和更新速度，而相對的編碼時間開銷很小。在優(yōu)化算法中，字典的更新和搜索使用的是Hash查找算法，這是一種高效的查找算法，有力地保證了優(yōu)化算法的壓縮速度。

4 算法驗證

對于判斷壓縮算法的優(yōu)劣，最重要的性能評判因素是壓縮比和壓縮速度。壓縮比計算方法為文件壓縮前后的字節(jié)大小比值，壓縮比越高，壓縮速度越快，算法性能越好。

使用LZ系列壓縮算法，其特點是對于不同的類型文件壓縮的效果會有一定的差異，這是待壓縮文件的結(jié)構(gòu)和內(nèi)容所決定的。所以，對于不同的類型文件，應(yīng)當(dāng)選擇合適的允許最大偏移匹配個數(shù)［8］。

本算法主要面向網(wǎng)絡(luò)壓縮傳輸，壓縮的文件主要為圖形界面文檔文件、圖像圖形文件、超文本文件。將該算法嵌入新開發(fā)的網(wǎng)站代碼中，實際檢測算法壓縮效率。

（1）采用從9位開始最大12位編碼的LZW9－12算法為基礎(chǔ)進(jìn)行優(yōu)化。

（2）本文重點研究無損網(wǎng)絡(luò)壓縮傳輸，使用網(wǎng)站的HTML文件作為實驗樣本，為了得到更加準(zhǔn)確的結(jié)果，選取3個不同大小的文件增加實驗的準(zhǔn)確性。

（3）擴(kuò)展位從3位起最大到9位，準(zhǔn)確測試網(wǎng)絡(luò)傳輸中最合適的參數(shù)設(shè)置。

測試參數(shù)結(jié)果見表8所列，由于壓縮時間全部分布在810ms以內(nèi)，都在可以接受的范圍內(nèi)，故壓縮時間已不是重要的考慮因素。

圖2所示為本次實驗3種不同大小文件在不同參數(shù)下的測試結(jié)果對比，可以直觀地看到偏移擴(kuò)展位為6位時，獲得的整體壓縮比最優(yōu)［6］，壓縮比提高的幅度在0.49～0.84之間。

表8 測試結(jié)果統(tǒng)計表

圖2 測試結(jié)果圖

5 結(jié)束語

本文提出了一種新穎的組合使用LZ壓縮方案，有效地對LZW算法進(jìn)行了改進(jìn)，更好地適應(yīng)現(xiàn)實網(wǎng)絡(luò)使用環(huán)境的需求。但是，改進(jìn)算法尚有進(jìn)一步改進(jìn)的空間［9］，例如，可以用多字典代替單字典避免字典重建時的低壓縮率，引用反饋機(jī)制自動調(diào)節(jié)參數(shù)維持高壓縮率等。

［1］華 強(qiáng).LZ77和LZ78在數(shù)據(jù)壓縮中的組合帶參運用［J］.小型微型計算機(jī)系統(tǒng)，2000，21（2）：211－215.

［2］Ziv J，Lempel A.A universal algorithMfor sequential data compression［J］.IEEE Transactions on Information Theory，1977，23（3）：337－343.

［3］Ziv J，Lempel A.Compression of individual sequences via variable－rate coding［J］.IEEE Transactions on Information Theory，1978，24（5）：530－536.

［4］張 燕，王 沁，余文裕，等.寬帶接入網(wǎng)中的動態(tài)壓縮技術(shù)［J］.計算機(jī)工程，2009，35（23）：27－29.

［5］胡浪濤，何輔云，沈兆鑫.油氣管道高速漏磁檢測系統(tǒng)中數(shù)據(jù)壓縮研究［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2009，32（3）：320－323.

［6］張鳳林，劉思峰.LZW＊：一個改進(jìn)的LZW數(shù)據(jù)壓縮算法［J］.小型微型計算機(jī)系統(tǒng)，2006，27（10）：1897－1899.

［7］許 霞，馬光思，魚 濤.LZW無損壓縮算法的研究與改進(jìn)［J］.計算機(jī)技術(shù)與發(fā)展，2009，19（4）：125－129.

［8］任學(xué)軍，房鼎益.一種適合無線傳感器網(wǎng)絡(luò)的混合編碼數(shù)據(jù)壓縮算法［J］.小型微型計算機(jī)系統(tǒng)，2011，32（6）：1055－1058.

［9］何 岳，王素玉，沈蘭蓀.高光譜圖像無損壓縮算法的DSP優(yōu)化實現(xiàn)［J］.計算機(jī)應(yīng)用研究，2008，25（1）：178－180.