北京林業(yè)大學(xué)理學(xué)院 鄧富博 李墨豪 溫愷林 張朝璇 陳 晨

?

基于不同信源的三種常用無損壓縮算法的研究

北京林業(yè)大學(xué)理學(xué)院 鄧富博 李墨豪 溫愷林 張朝璇 陳 晨

【摘要】隨著社會的發(fā)展和科技的進步，數(shù)據(jù)壓縮越來越受到人們的重視。壓縮算法可分為有損壓縮和無損壓縮。本文基于不同信源對常用的三種無損壓縮算法（霍夫曼編碼、游程編碼及LZW編碼）進行了研究與總結(jié)。對它們各自的原理進行了簡單的介紹，并在最后歸納了它們的優(yōu)缺點、適用范圍及大體壓縮率情況。

【關(guān)鍵詞】霍夫曼；LZW； 游程；優(yōu)缺點；適用范圍

0 引言

數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，以最小的數(shù)碼表示信源所發(fā)出的信號，或按照一定的算法對數(shù)據(jù)進行重新組織，減少數(shù)據(jù)的冗余和存儲的空間的一種技術(shù)方法［1］。總的來說數(shù)據(jù)壓縮包括有損壓縮和無損壓縮。

隨著社會的發(fā)展和科技的進步，無損壓縮算法的種類越來越多，效果也越來越好。主要有霍夫曼算法、游程編碼、LZ系列等等。本文主要對霍夫曼算法、游程編碼以及LZW算法進行了研究與討論，并總結(jié)了它們在不同信源下的效果，優(yōu)缺點及壓縮率等。

1 霍夫曼壓縮算法

1.1 基本原理

霍夫曼算法是D.A.Huffman 在1952 年發(fā)現(xiàn)的一種基于信號概率的數(shù)據(jù)無損壓縮算

法［2］。它的壓縮思想的核心是構(gòu)建霍夫曼樹，又稱為最優(yōu)二叉樹。通過“葉子”和分支的權(quán)重，來尋找?guī)?quán)路徑最小的二叉樹［3］。

比如有五個權(quán)重分別為1，1，2，2，4的符號，構(gòu)建最優(yōu)二叉樹步驟如圖1所示：

圖1 構(gòu)建最優(yōu)二叉樹步驟圖

最后，根據(jù)構(gòu)建好的二叉樹按左0右1的規(guī)則進行編碼，易懂且簡單方便。

1.2 算法結(jié)果分析

霍夫曼編碼與其它的壓縮算法相比，速度還是較快的。它主要針對統(tǒng)計結(jié)果的字符進行編碼［4］，可以說是完全根據(jù)字符出現(xiàn)的頻率來進行編碼的，形式靈活多變。它對不同的信源編碼效率是不同的，對于有些信源可達(dá)到100%的編碼效率；可若信號源符號的概率相等時，則編碼效率最低［5］。還有就是編出的碼并不唯一，但平均碼長相等。

2 游程壓縮算法

2.1 信源

信源就是信息的來源，信息的發(fā)生或傳播者。信源發(fā)出信息的時候，一般以某種訊息的方式表現(xiàn)出來，可以是符號也可以是信號，比如文字，圖像等。

2.2 基本原理

游程編碼（RLC，Run Length Coding），又稱”運行長度編碼”或”行程編碼”，是一種統(tǒng)計編碼，該編碼屬于無損壓縮編碼。

用一個符號值或串長代替具有相同值的連續(xù)符號，使符號長度少于原始數(shù)據(jù)的長度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時，一次記錄該代碼及相同代碼重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。

例如：55555555 777 99999 666666，變?yōu)椋?，8）（7，3）（9，5）（6，6），這樣編碼位數(shù)遠(yuǎn)小于原始數(shù)據(jù)的位數(shù)。

2.3 算法結(jié)果分析

因為游程算法更適用于圖像數(shù)據(jù)的壓縮，所以本文對幾種不同類型的圖像的壓縮結(jié)果進行了討論。

2.3.1 GIF和PNG類型的圖像

對于這兩種信源的壓縮，游程編碼不能很完美的實現(xiàn)無損壓縮，壓縮后的效果不是很好。

2.3.2 JPG類型的圖像

JPG圖像壓縮后，信源有時會存在一定的損傷，但是其正確率較高，壓縮效果較好。但有時會出現(xiàn)越壓越大的現(xiàn)象，這是由于JPG圖像是一種以文件犧牲圖像質(zhì)量為代價的壓縮比可以達(dá) 到100：1的圖像冗余度很小的圖像格式。而對于原始的，未經(jīng)壓縮的，冗余度大的JPG圖像游程編碼并不太適用。

圖2 JPG圖像壓縮前

圖3 JPG圖像壓縮后

2.3.3 bmp圖像

對于冗余度較高的bmp圖像，壓縮前后差距很小，幾乎是一樣的，正確率比上面兩種情況要高出很多。而對于冗余度相對較低的bmp圖像，正確率也是很高，但有時會出現(xiàn)越壓越大的情況，此時壓縮率約為111%左右。

圖4 bmp圖像壓縮前

圖5 bmp圖像壓縮后

3 LZW算法

3.1 基本原理

LZW算法是1984年Welch提出的基于LZ78算法的一個變種壓縮算法［2］。

LZW算法壓縮時，按順序判斷數(shù)據(jù)序列是否存在于詞典中，用詞典索引字符替代一部分字符串，以達(dá)到壓縮目的；解壓時，根據(jù)壓縮后的數(shù)據(jù)，還原出所用詞典，并進一步還原出原文。

3.2 算法結(jié)果分析

它的主要優(yōu)勢是對于大多數(shù)數(shù)據(jù)，能提供較好的壓縮率；某種特定實現(xiàn)方法僅需隨壓縮后數(shù)據(jù)傳輸一個相對較小的詞典，另一種實現(xiàn)方法不需要隨數(shù)據(jù)發(fā)送詞典，可以通過壓縮后數(shù)據(jù)還原。不足之處就是注重實現(xiàn)速度，按順序執(zhí)行壓縮的過程，沒有對數(shù)據(jù)進行分析［6］。

總的來說，它適用于大多數(shù)一般數(shù)據(jù)的壓縮，較為好用。

4 三種算法小結(jié)

表1 三種算法總結(jié)表

5 結(jié)語

本文對常用的三種無損壓縮算法的原理及適用情況進行了研究與總結(jié)。根據(jù)信源的不同，這三種算法的壓縮效果不同?；舴蚵陀纬趟惴▔嚎s速度較快，LZW的適用范圍最為廣闊，并且有較好的壓縮率?？傊鶕?jù)信源的不同可以選擇不同的壓縮算法，以達(dá)到想要的效果。

參考文獻

［1］葉倩，張俊蘭，馮雄偉.淺析數(shù)據(jù)壓縮技術(shù)［J］.延安大學(xué)學(xué)報（自然科學(xué)版），2008，27（4）﹕29-33.

［2］鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究［J］.計算機技術(shù)與發(fā)展，2011，21（9）﹕73-76

［3］時國平.關(guān)于霍夫曼編碼數(shù)據(jù)壓縮效果［J］.池州學(xué)院學(xué)報，2008，22（5）﹕46-48

［4］李雷定，馬鐵華，尤文斌.常用數(shù)據(jù)無損壓縮算法分析［J］.電子設(shè)計工程，2009，17（1）﹕49-50，53.

［5］任維政，徐連明，鄧中亮.民用GPS數(shù)據(jù)準(zhǔn)無損壓縮算法［J］.數(shù)據(jù)采集與處理，2010，25（2）﹕245-249.

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

指導(dǎo)教師：汪沛，副教授。