摘要：文章通過闡述兩種字典壓縮算法LZSS和LZW的原理，分析了兩種算法在進行文件壓縮時的優(yōu)缺點，并設(shè)計了一種基于LZSS和LZW的聯(lián)合壓縮算法。為了進一步對聯(lián)合壓縮算法進行優(yōu)化以提高壓縮率，引入Huffman編碼對壓縮結(jié)果進行編碼輸出。實驗結(jié)果表明，基于Huffman編碼的聯(lián)合算法能夠達到較好的壓縮效果。

關(guān)鍵詞：LZSS；LZW；Huffman；壓縮

中圖分類號：TP311

文獻標識碼：A

文章編號：1009-3044（2025）15-0060-03

0引言

隨著計算機技術(shù)、多媒體技術(shù)的高速發(fā)展，各種媒體的數(shù)據(jù)量越來越大，給信息存儲特別是網(wǎng)絡(luò)數(shù)據(jù)傳輸帶來諸多的困難，并已成為有效獲取和使用信息的瓶頸。為了節(jié)省信息的存儲空間，提高信息的傳輸效率，必須對大量的實際數(shù)據(jù)進行壓縮，而壓縮的實際數(shù)據(jù)以文本和圖片為主。實踐中采用數(shù)據(jù)壓縮技術(shù)，通?？梢怨?jié)省80％以上的開銷，并且使得一些困難的問題轉(zhuǎn)而在技術(shù)上能夠?qū)崿F(xiàn)。

文本、圖片數(shù)據(jù)的壓縮在70年代末之前基本采用統(tǒng)計編碼。由于統(tǒng)計編碼在壓縮效果方面不夠理想，字典編碼算法迅速取代了統(tǒng)計編碼算法。現(xiàn)在公認的看法是在文本和程序的數(shù)據(jù)壓縮中，除LZ方法之外，不考慮其他方法。當然，現(xiàn)有的字典壓縮算法工作效率仍存在提升的空間，本文提出了一種基于LZSS和LZW的聯(lián)合壓縮算法，并結(jié)合Huffman編碼進行優(yōu)化，以提高數(shù)據(jù)壓縮效率。

1LZSS和LZW壓縮算法原理

1.1LZSS壓縮算法

——LZLZSS77的基礎(chǔ)上的一種改進算法是在J.Ziv和A.Lempel提出的字典壓縮算法[1]。在壓縮率上LZSS算法相較于其他壓縮算法而言并不擁有優(yōu)勢，但其在壓縮與解壓縮的速度上卻非常快，因此，LZSS算法往往應用于速度優(yōu)先的場景之下?；谒惴ǖ倪@個特點，LZSS算法被廣泛應用于日常生活中exe與，expand例如微軟早年通過.exe兩個程序LZSS。LZSS算法實現(xiàn)了算法的原理非常簡compress.潔，利用樹結(jié)構(gòu)搜索目前未壓縮的數(shù)據(jù)是否在前面出現(xiàn)過，如果出現(xiàn)過則利用前面出現(xiàn)的位置和長度代替現(xiàn)在的未壓縮數(shù)據(jù)[2]。在算法實現(xiàn)的過程中，通過利用一個長度為N個字節(jié)的滑動窗口在文本中前后滑動，N字節(jié)窗口的最后F個字節(jié)作為一個前向緩沖區(qū)，那么位于滑動窗口前半部分的N-F個字節(jié)內(nèi)容是已處理的文本，后F個字節(jié)內(nèi)容則是待處理的文本，其結(jié)構(gòu)如圖1所示。

LZSS算法在工作的過程中，用前向緩沖區(qū)中F個字節(jié)的文本與前面N-F個長度為F字節(jié)的文本進行依次比較。如圖1中當F=10，前向緩沖區(qū)中的內(nèi)容為qrstabcdfk，LZSS算法在壓縮時前向緩沖區(qū)的內(nèi)容依次與前面zqrstabcdf、yzqrstabcd、xyzqrstabc、wxyzqrstab……總共N-10個串進行比較，尋找與之匹配的最長串。可以看到最長匹配串出現(xiàn)在qrstuvwxyz的位置，其匹配長度為4、具體匹配子串為qrst。此時，壓縮算法會以一個二元組的形式記錄下匹配串的具體信息，即（匹配位置，匹配長度），在圖1的例子中為（N-20，4），并將其寄存于輸出緩沖區(qū)中。然后，將滑動窗口向后滑動，原窗口中后F字節(jié)長度的文本滑入N-F字節(jié)區(qū)域中，同時從文件的后續(xù)文本中補充相應長度的內(nèi)容到窗口的后F字節(jié)區(qū)中，隨后重復上述步驟進行壓縮處理直至文件結(jié)束。當然也有特例，如果最長匹配串的長度小于二元組存放空間時，例如F字節(jié)區(qū)域與前區(qū)匹配到的最大串長度僅為1，此時用二元組記錄匹配串位置時顯然會造成空間浪費，在這種情況下直接將匹配字符存入輸出緩沖區(qū)中。

1.2LZW壓縮算法

1984年，T.Welch給出了LZ78算法的實用修正LZW[3]。LZW壓縮算法的工作原理基于任何具有某種預見性的數(shù)據(jù)，都可以通過某種標記來表示這種預見性而使得數(shù)據(jù)變短[4]，這里所謂的具有預見性的數(shù)據(jù)即字符串的排列順序是否有過重復。LZW壓縮算法的工作流程如圖2所示。

在初始化的步驟里約定一個數(shù)據(jù)壓縮后生成的代碼流中的每個代碼長度不超過N位，換句話說壓縮算法可以表示的數(shù)據(jù)范圍是0～2N-1，串表的數(shù)據(jù)容量為2N項，輸入數(shù)據(jù)流中待壓縮的每個元素占一個字節(jié)，所能代表的取值范圍是0～255。在字符讀取的步驟中，每次從輸入的文本中讀取一個字節(jié)，并用兩個緩沖區(qū)進行存儲，即當前前綴碼和當前串。壓縮算法開始時前綴碼與當前串兩個緩沖區(qū)均為空，在運行的過程中，前綴碼緩沖區(qū)存放上一輪處理所得代碼，當前串緩沖區(qū)存放前綴碼所代表的字符以及本輪運算剛讀取的字符。對于讀取到的一個字節(jié)，壓縮算法就會到串表中查找是否存在當前串，同時讀取下一個字節(jié)，并將其添加到當前串的后面，此時當前串成為雙字節(jié)，并重復上一個步驟進行串表的匹配。顯然匹配結(jié)果為空，因為串表中不存在雙字節(jié)項，這時算法會在串表中創(chuàng)建第256項，以對應此時兩個字節(jié)長度的當前串，然后將前綴碼輸出得到所需的壓縮代碼。當串表中的2N項將滿，無法容納新串時，通過清除碼清空串表并重新初始化前綴碼緩沖區(qū)與當前串緩沖區(qū)，然后重復上述步驟進行新一輪的數(shù)據(jù)壓縮運算。

從壓縮速度上來看，LZW算法具備更快的處理速度；從壓縮效果上來看，當所需處理的文本具有一定穩(wěn)定性、前后具備一定的關(guān)聯(lián)性時，LZW算法的壓縮效果會隨著文本長度的增長而趨近于最佳壓縮效果，這一點在理論上也已經(jīng)得到了證明。

2LZSS和LZW聯(lián)合壓縮算法

2.1算法的設(shè)計

通過測試不同長度的文本，LZSS壓縮算法與LZW壓縮算法在壓縮效果上的差異如表1所示。

從對9個樣本的測試結(jié)果中可以看到，文本長度在10kb以內(nèi)時，LZSS算法與LZW算法的壓縮時間相差不大，這主要受串匹配基本操作的限制，但LZSS算法的總體壓縮效果略優(yōu)于LZW算法；當文本長度在10kb～90kb之間時，LZSS算法的壓縮比明顯高于LZW算法，在壓縮時間上LZW算法略有優(yōu)勢；當文本長度超過90kb甚至更大時，LZW算法的壓縮比要高于LZSS算法，同時所需的時間僅為LZSS算法的一半，此時其壓縮效果要明顯超出LZSS算法很多。

在LZSS算法與LZW算法的基礎(chǔ)上，如何優(yōu)化壓縮技術(shù)使得壓縮算法能夠兼具兩種算法的優(yōu)點，既能提高壓縮比例，又能縮短壓縮時間，主要有兩種嘗試途徑：一是在LZSS算法基礎(chǔ)上進行的改進，采用多叉樹的結(jié)構(gòu)，通過LZSS算法的滑動窗口進行遍歷，期望通過一次遍歷將整個文本直接插入字典中，省去字符逐個匹配所耗費的時間，例如LZFG壓縮算法，但該算法的數(shù)據(jù)結(jié)構(gòu)顯然過于復雜，且實現(xiàn)算法的步驟也過于煩瑣；二是在LZW算法基礎(chǔ)上進行的改進，通過加速串表的生成來提高壓縮比，這可以明顯提高固定碼位LZW算法的壓縮比效果，但這也帶來新的問題，即串表生成過快會使得字典碼表的更新時間縮短，從而降低新算法對于較長文件的壓縮比。

鑒于單純以LZSS算法或LZW算法進行改進都存在一定的缺陷，本文提出的方案是將LZSS算法與LZW算法進行疊加，其算法描述如下：

（1）讀入文件，若文件結(jié)束則轉(zhuǎn)（7）

（2）利用LZSS算法進行壓縮并輸出

（3）若LZSS的滑動窗口未滿，則轉(zhuǎn)（1）

（4）若LZSS的滑動窗口已滿則進行兩步操作：

①清空LZSS的滑動窗口

②利用原空間和數(shù)據(jù)結(jié)構(gòu)將窗口轉(zhuǎn)換為LZW匹配串表

（5）繼續(xù)讀入，若文件結(jié)束則轉(zhuǎn)（7）

（6）利用LZW算法進行壓縮并輸出，然后轉(zhuǎn)（5）

（7）壓縮完成

從表1的測試結(jié)果中可以看到，對于短文本LZSS壓縮算法具有優(yōu)勢，當文本超過一定長度時LZW算法的優(yōu)勢則會突顯出來，因此新算法的核心思路是先使用LZSS算法進行壓縮，當被壓縮的文本超過LZSS算法的優(yōu)勢邊界時，換句話說即是滑動窗口填滿時，壓縮算法則改為LZW算法，直至需要壓縮的文本結(jié)束。

表1的測試結(jié)果表明，LZSS算法的優(yōu)勢邊界在90kb左右，因此可以將LZSS的滑動窗口大小控制在90kb以內(nèi)，此時可以跳過LZW算法壓縮比例較低的階段，同時發(fā)揮LZSS算法壓縮比例高、壓縮時間短的優(yōu)勢，其后使用LZW算法則使得其后期高壓縮比的優(yōu)勢得到充分發(fā)揮。另一方面，由于窗口容量不大，在從LZSS滑動窗口轉(zhuǎn)化到LZW串表的過程中所需的時間較短，這亦保證了算法的高效性。當然，窗口容量并不是越小越好，在實際測試中，窗口容量在70kb～80kb最佳。新算法中涉及的LZSS算法與LZW算法所使用的字典采用相同的結(jié)構(gòu)，其具體結(jié)構(gòu)如下：

structdictionary

{intlarger_codevalue;

intparent_stringcodeintsmall_character;;

}dictionary[table_banks]

#defineDICT（i）dictionary[igt;gt;8][iamp;0xFF]

在壓縮的過程中，當LZSS的滑動窗口已填滿而所需壓縮的文本尚未結(jié)束時，重新初始化公用字典，并對窗口采用LZW算法的掃描，并完成如下操作：DICTDICT（（ii）.）.larger_codevalue=next_code++parent_stringcode=string_code;;DICTLZSS（搜索樹內(nèi)容即可轉(zhuǎn)換為i）.small_character=characterLZW;搜索樹，搜索樹的轉(zhuǎn)換過程變得較為簡單，且不會增加壓縮算法的運算時間。

2.2算法的優(yōu)化

從算法的時間與空間效度上來看，新算法是一種較高效率的算法，但在實際的使用過程中仍有可以改進之處，為使其達到更高的壓縮比，可以通過結(jié)合熵編碼的方式以進一步提高壓縮效果。最常用的熵編碼為Huffman編碼[5]。

Huffman編碼的方式主要通過改變編碼的長度，對于給定的字符概率分布，Huffman編碼就可以計算出每個字符的具體編碼形式[6]。Huffman編碼通過自下而上的方式來構(gòu)造Huffman樹，算法首先為每個字符創(chuàng)建一個葉節(jié)點，同時在這個葉節(jié)點中必須包含該字符出現(xiàn)的概率值，然后將葉節(jié)點按照概率值的大小依次排序，選擇概率值最小的兩個葉節(jié)點連接成為兄弟節(jié)點并產(chǎn)生其父節(jié)點，父節(jié)點的概率值是其兩個子節(jié)點概率值的和，忽略已連接的子節(jié)點，將其父節(jié)點納入到原來的序列中并按照概率值的大小排序，再次選擇概率值最小的兩個節(jié)點重復先前的連接操作直至所有節(jié)點連接成樹。在實際的壓縮應用中，Huff?man編碼對于已知出現(xiàn)概率的無前綴字符，產(chǎn)生的編碼可以實現(xiàn)較好的壓縮效果。

利用Huffman編碼進行新壓縮算法改進時，所用的數(shù)據(jù)結(jié)構(gòu)為兩棵Huffman樹，一棵用來表示字符和匹配長度，另一棵用來表示字符的偏移量。經(jīng)過壓縮算法處理后的數(shù)據(jù)暫時不輸出，依據(jù)兩棵Huffman樹中的內(nèi)容再進行一次Huffman編碼的操作。在Huff?man編碼的過程中引入匹配長度區(qū)間的概念，區(qū)間大小由滑動窗口的大小決定，用M個葉節(jié)點表示，再根據(jù)匹配長度區(qū)間大小用0～L（2Lgt;=M）個額外的比特來表示匹配長度在每個長度區(qū)間的偏移。在窗口不斷滑動的過程中Huffman樹的結(jié)構(gòu)勢必越來越復雜，為了簡化其結(jié)構(gòu)采用周期性重建樹結(jié)構(gòu)的方式，設(shè)置更新標志位Flag，初始值根據(jù)窗口大小決定，每編碼一個字符則Flag進行減1操作，同時更新相應節(jié)點的概率值，當Flag為0時根據(jù)各個節(jié)點的概率值重建一次Huffman樹。根據(jù)這樣的思路，新算法的描述可以改進為：

（1）讀入文件，初始化匹配長度Huffman樹和偏移量Huffman樹，若文件結(jié)束則轉(zhuǎn)（11）

（2）進行LZSS壓縮，將字符、匹配長度、偏移量記錄到相應Huffman樹中

（3）若窗口未滿，則轉(zhuǎn)（1）

（4）若窗口已滿

①清空LZSS搜索樹

②利用原空間和數(shù)據(jù)結(jié)構(gòu)將窗口轉(zhuǎn)換為LZW搜索樹

（5）繼續(xù)讀入，若文件結(jié)束，則轉(zhuǎn)（7）

（6）進行LZW壓縮，將字符、匹配長度、偏移量記錄到相應Huffman樹中，轉(zhuǎn)（5）

（7）設(shè)置Flag，根據(jù)字符匹配長度的偏移量初始化或重建Huffman樹

（8）讀入暫存字符，以匹配長度在每個長度區(qū)間的偏移L為權(quán)值并根據(jù)字符概率構(gòu)建Huffman樹，F(xiàn)lag減1

（9）若暫存字符結(jié)束則轉(zhuǎn)（11）

（（1011））若輸出字符匹配長度的Flag=0轉(zhuǎn)（7）否則轉(zhuǎn)（8Huffman）樹和偏移量Huffman樹

2.3算法的驗證

在實驗室環(huán)境下，通過對不同長度的隨機英文文本樣本進行壓縮測試，LZSS壓縮算法、LZW壓縮算法以及Huffman編碼新算法在壓縮效果上的差異如表2所示。

測試結(jié)果表明，Huffman編碼的新算法，相較于LZSS壓縮算法與LZW壓縮算法在壓縮比率上有明顯的提高。

3結(jié)束語

從不同長度的樣本文件的壓縮測試結(jié)果中，我們不難發(fā)現(xiàn)，對LZW壓縮算法而言，聯(lián)合壓縮算法既保持了其快速性和對較長樣本文件具有的較高壓縮比的優(yōu)點，又較好地克服了對較短樣本文件的壓縮比不高的缺點；而與LZSS壓縮算法相比較，聯(lián)合壓縮算法對樣本文件在壓縮速度和壓縮比上都有較大的提高。在對壓縮結(jié)果引入Huffman編碼后，樣本文件的壓縮比得到再次的提高，取得了令人滿意的壓縮效果。

本文主要從壓縮算法的角度對如何提高文件的壓縮率進行了研究，提出了一種基于Huffman編碼的LZSS和LZW聯(lián)合壓縮算法，并在實驗的環(huán)境下獲得了一定的數(shù)據(jù)，實驗結(jié)果表明該算法在壓縮率和壓縮速度方面均有提升。當然，實驗測試環(huán)境沒有考慮實際使用中的具體情況，后續(xù)研究中將針對不同類型的數(shù)據(jù)進行算法參數(shù)優(yōu)化、探索其他熵編碼方法與字典壓縮算法的結(jié)合。

參考文獻：

[1]王平，茅忠明.LZSS文本壓縮算法實現(xiàn)與研究[J].計算機工程，2001（8）：22-24.

[2]王平，茅忠明.中文文本的LZSS算法實現(xiàn)及研究[J].微電子學與計算機，2001，18（2）：14-17.

[3]王平.LZW無損壓縮算法的實現(xiàn)與研究[J].計算機工程，2002，28（7）：98-99，150.

[4]楊小軍.LZW壓縮算法解析及應用設(shè)計[J].火控雷達技術(shù)，1998，27（4）：66-69.

[5]劉金嶺，劉國香.Huffman編碼的優(yōu)化[J].河北師范大學學報，2006，30（1）：29-32.

[6]李曉飛.Huffman編解碼及其快速算法研究[J].現(xiàn)代電子技術(shù)，2009，32（21）：102-104，108.

【通聯(lián)編輯：李雅琪】