一種快速解壓的無損壓縮算法*

王 松，房利國，韓煉冰，劉鴻博

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

在當前的無損壓縮算法領(lǐng)域中，主要存在兩種技術(shù)思路。一種是基于數(shù)學統(tǒng)計的編碼壓縮方法，另一種是基于數(shù)據(jù)查找及匹配的詞典編碼壓縮方法。早期的壓縮方法大都采用基于數(shù)學統(tǒng)計的編碼方法，該編碼方法最早由Shannon 和Fano 在1949 年提出[1]。在此基礎(chǔ)上，1952 年Fano 的學生Huffman 提出了著名的霍夫曼編碼[2]，是一種極為有效的二進制編碼壓縮方法，一直沿用至今?；谠~典編碼的壓縮方法是1977 年在以色列人Jacob Ziv 和Abraham Lempel 發(fā) 表 的 論 文“A Universal Algorithm for Sequential Data Compression”中被首次描述，并提出了基于該方法的LZ77 壓縮算法[3]。在該算法中，待處理數(shù)據(jù)會與前文進行字符串匹配，如果匹配成功，則被壓縮成一個壓縮塊放入壓縮文件。1978 年，他們又提出了改進后的LZ78 算法[4]。LZ77 的特點是將已處理的原始數(shù)據(jù)流作為詞典的輸入?yún)⑴c壓縮運算。LZ78 的特點是將已處理的數(shù)據(jù)編入一個詞典，通過不斷擴充及維護詞典來進行壓縮運算。無論是LZ77 還是LZ78 算法，均可實現(xiàn)比基于統(tǒng)計編碼更快的壓縮和解壓速度。在后來的研究過程中，LZ77 和LZ78 算法又產(chǎn)生了新的算法，主要發(fā)展路徑如圖1 所示。

圖1 詞典編碼方法

1 LZO 壓縮算法

LZO 算法由以色列數(shù)學家A.Lempel、J.Ziv 和B.Oberhumer 共同提出[5]。該算法在壓縮匹配策略及存儲格式上做了許多優(yōu)化，以達到快速解壓的目的，是目前公開算法中解壓速度最快的壓縮算法[6]。LZO 存在許多版本，目前最常用的版本是LZO1X_1。該版本的LZO 算法廣泛應(yīng)用于Linux 內(nèi)核、嵌入式設(shè)備以及網(wǎng)絡(luò)數(shù)據(jù)傳輸。本文使用的正是該版本。

1.1 LZO 算法搜索匹配策略

LZO 算法在進行數(shù)據(jù)壓縮時采用一個哈希表來進行數(shù)據(jù)匹配。哈希表以當前待處理數(shù)據(jù)的雜湊值為索引，讀取上一次該字符串出現(xiàn)的可能位置并進行匹配。當本次匹配失敗時，算法通過二次雜湊的方式跳轉(zhuǎn)到下一位置繼續(xù)進行匹配操作。如果匹配成功，則根據(jù)匹配的距離和長度信息生成相應(yīng)的壓縮編碼。如果兩次匹配均未成功，則認為當前數(shù)據(jù)無法壓縮。哈希表隨著壓縮的進行被不斷更新。該匹配過程如圖2 所示[7]。

字符串的搜索匹配一直是詞典編碼壓縮算法的瓶頸。LZO 算法與LZ77、LZSS 等壓縮算法相比，大大降低了字符串搜索匹配的運算量。雖然匹配結(jié)果并不是最優(yōu)的，但快速的搜索匹配使得該算法更加實用。

圖2 LZO 算法的兩次匹配過程

1.2 LZO 算法的壓縮格式

LZO 算法以字節(jié)為單位設(shè)計壓縮格式。它的壓縮格式根據(jù)匹配字符串的長度分兩大類。當匹配長度大于等于4 Bytes 且小于等于8 Bytes 時，按照第一類壓縮格式進行數(shù)據(jù)壓縮。該類壓縮格式的詳細定義如圖3 所示[8]。

圖3 匹配長度小于等于8 Bytes 時壓縮格式

圖3 中格式一用于存儲匹配距離小于等于2 kB時的壓縮信息，格式二用于存儲匹配距離大于2 kB且小于等于16 kB 時的壓縮信息，格式三用于存儲匹配距離大于16 kB 且小于48 kB 時的壓縮信息。

當匹配長度大于8 Bytes 時，LZO 算法設(shè)計了兩種壓縮格式，如圖4 所示。

圖4 匹配長度大于8 Bytes 時壓縮格式

圖4中格式一用于存儲匹配距離小于等于16 kB 時的壓縮信息，格式二用于編碼匹配距離大于16 kB 字節(jié)且小于48 kB 時的壓縮信息。

1.3 LZO 算法的解壓過程

由于LZO 算法在壓縮格式上的巧妙設(shè)計，使得在解壓過程中壓縮編碼可以很快被解析。從圖3和圖4 中可以分析得出，不同的編碼類型可以從編碼首字節(jié)的取值直接得出。如果首字節(jié)的值大于等于64，則按照圖3 中格式一進行解析。如果首字節(jié)的值大于等于32 且小于64，則按照圖3 第二種或圖4 第一種壓縮格式進行解析。如果首字節(jié)的值大于等于16 且小于32，則按照圖3 第三種或圖4 第二種壓縮格式進行解析。如果首字節(jié)的值小于16，則說明后續(xù)數(shù)據(jù)是未進行壓縮的數(shù)據(jù)。整個解壓程序可以很簡潔地完成，達到快速解壓的目的。

2 快速解壓的新無損壓縮算法

從對LZO 算法的分析中可以看出，LZO 算法解壓時的主要開銷是對壓縮格式的解析。它的最大匹配距離是48 kB，最短匹配長度是4 Bytes。實際測試中發(fā)現(xiàn)，對較短數(shù)據(jù)的壓縮處理會大大增加解壓程序的開銷，卻不會帶來壓縮率的較大提升。同時，在48 kB 匹配空間之外，經(jīng)常會出現(xiàn)較多的匹配數(shù)據(jù)無法被壓縮。針對這一問題，本文提出了一種新的壓縮方法。該方法在放棄部分較短匹配數(shù)據(jù)的同時，在更大的匹配空間進行匹配搜索，在保證壓縮率的同時降低了壓縮文件中壓縮塊的數(shù)量，進一步提高了解壓速度。新算法與LZO 算法的匹配長度與匹配距離對比關(guān)系如圖5 所示。

圖5 新算法與LZO 算法匹配策略對比

從圖5 可以看出，新設(shè)計的壓縮算法在匹配距離大于2 kB 時，放棄了匹配長度小于9 Bytes 的匹配數(shù)據(jù)，匹配距離由48 kB 增加到了256 kB。放棄對小于9 Bytes 匹配長度的數(shù)據(jù)壓縮必然會導致壓縮率的降低，然而由于新算法的匹配距離大大增加，更多匹配長度較長的數(shù)據(jù)將被壓縮，可以彌補壓縮率的損失。

2.1 新算法的搜索匹配策略

新算法匹配距離的大大增加，使得類似LZO 的二次雜湊的匹配策略不再適用。新算法采用了一種可擴展的多頁匹配策略進行匹配，匹配策略如圖6所示。

圖6 新算法的匹配過程

新算法采用可配置的多頁詞典查找方式進行字符串匹配。這種匹配方法與LZO 算法的匹配方法相比，在詞典空間的配置上更加靈活。壓縮程序以當前待處理數(shù)據(jù)的雜湊值為索引，分別在匹配詞典的每一頁讀取上一次該字符串出現(xiàn)的可能位置，并進行匹配。所有的匹配完成后，選取最佳的匹配結(jié)果進行處理。

2.2 新算法的存儲格式

新算法同樣以整字節(jié)為單位設(shè)計壓縮格式，方便解壓程序的處理。與LZO 算法不同，新算法的壓縮格式是按照匹配距離是否小于2 kB 來進行分類的。當匹配距離小于2 kB 時，新算法的壓縮格式的詳細定義如圖7 所示。

圖7 匹配距離小于2 kB 時的壓縮格式

圖7 中格式一用于存儲匹配長度小于等于17 Bytes 時的壓縮信息，格式二用于存儲匹配長度大于 17 Bytes 時的壓縮信息。

當匹配距離大于等于2 kB 時，新算法的壓縮格式的詳細定義如圖8 所示。

圖8中格式一用于存儲匹配長度小于等于18 Bytes 時的壓縮信息，格式二用于存儲匹配長度大于 18 Bytes 時的壓縮信息。

新算法的存儲格式與LZO 算法相比，降低了壓縮塊格式的數(shù)量，使得解壓程序?qū)嚎s格式的判斷更加簡單，有利于提高解壓速度。

3 對比測試

在新算法實現(xiàn)完成并驗證正確性后，本文將其與LZO 算法做了測試對比。

新算法的匹配詞典大小靈活可配，測試時匹配詞典設(shè)置為兩個匹配頁面。此時，新算法的壓縮率與LZO 算法幾乎一致，更利于比較兩個壓縮算法的解壓性能。為了降低操作系統(tǒng)對測試結(jié)果的影響，本次測試在無操作系統(tǒng)的DSP 芯片上進行，DSP 芯片型號為TMS320C6748[9]。測試時，待解壓的數(shù)據(jù)及解壓后數(shù)據(jù)均存放在與DSP 連接的片外存 儲器中。

圖8 匹配距離大于等于2 kB 時的壓縮格式

測試樣本選擇了PPT 幻燈片、PDF 文件、WORD 文檔、圖片、網(wǎng)頁以及EXCEL 表格等各種常見的文件類型。壓縮算法對測試樣本文件的壓縮率如表1 所示。

從表1 中可以看出，當匹配詞典設(shè)置為兩個頁面時，兩個壓縮算法的壓縮率比較接近。但是，在幾乎相同壓縮率的情況下，新算法可降低壓縮文件中20%～50%的壓縮塊數(shù)量，非常有利于提升解壓速度。測試表1 中壓縮后文件的解壓速度，結(jié)果如表2 所示。

表2 的測試結(jié)果表明，在幾乎同等壓縮率情況下，新算法的解壓速度與LZO 算法相比得到了較大提升。這種差別是由二者的匹配策略和存儲格式不同造成的。新算法在更大空間上進行了匹配操作，提升了匹配成功概率，同時放棄了對大量較短匹配字符串的壓縮處理，使得解壓程序需要解析的壓縮編碼大大減少，從而提高了解壓速度得。

表1 新算法與LZO 算法壓縮率比較

表2 新算法與LZO 解壓速度比較

4 結(jié) 語

本文在研究LZO 壓縮算法的基礎(chǔ)上，設(shè)計了一個新的壓縮算法。新算法在放棄對一些小塊數(shù)據(jù)壓縮處理的同時，在更大的空間上進行搜索匹配，可以有效降低壓縮文件中的壓縮塊數(shù)量。測試結(jié)果表明，提出的壓縮算法的解壓速度與目前公開算法中解壓最快的LZO 算法相比具有一定優(yōu)勢，具備較高的實用價值。