基于Huffman編碼的LZSS與LZW聯合壓縮算法研究

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

關鍵詞：LZSS；LZW；Huffman；壓縮

中圖分類號：TP311

文獻標識碼：A

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

0引言

隨著計算機技術、多媒體技術的高速發展，各種媒體的數據量越來越大，給信息存儲特別是網絡數據傳輸帶來諸多的困難，并已成為有效獲取和使用信息的瓶頸。為了節省信息的存儲空間，提高信息的傳輸效率，必須對大量的實際數據進行壓縮，而壓縮的實際數據以文本和圖片為主。實踐中采用數據壓縮技術，通常可以節省80％以上的開銷，并且使得一些困難的問題轉而在技術上能夠實現。

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

1LZSS和LZW壓縮算法原理

1.1LZSS壓縮算法

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

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

1.2LZW壓縮算法

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

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

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

2LZSS和LZW聯合壓縮算法

2.1算法的設計

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

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

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

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

（1）讀入文件，若文件結束則轉（7）

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

（3）若LZSS的滑動窗口未滿，則轉（1）

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

①清空LZSS的滑動窗口

②利用原空間和數據結構將窗口轉換為LZW匹配串表

（5）繼續讀入，若文件結束則轉（7）

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

（7）壓縮完成

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

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

structdictionary

{intlarger_codevalue;

intparent_stringcodeintsmall_character;;

}dictionary[table_banks]

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

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

2.2算法的優化

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

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

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

（1）讀入文件，初始化匹配長度Huffman樹和偏移量Huffman樹，若文件結束則轉（11）

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

（3）若窗口未滿，則轉（1）

（4）若窗口已滿

①清空LZSS搜索樹

②利用原空間和數據結構將窗口轉換為LZW搜索樹

（5）繼續讀入，若文件結束，則轉（7）

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

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

（8）讀入暫存字符，以匹配長度在每個長度區間的偏移L為權值并根據字符概率構建Huffman樹，Flag減1

（9）若暫存字符結束則轉（11）

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

2.3算法的驗證

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

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

3結束語

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

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

參考文獻：

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

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

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

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

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

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

【通聯編輯：李雅琪】