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

北京林業大學理學院 鄧富博 李墨豪 溫愷林 張朝璇 陳 晨

?

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

北京林業大學理學院 鄧富博 李墨豪 溫愷林 張朝璇 陳 晨

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

【關鍵詞】霍夫曼；LZW； 游程；優缺點；適用范圍

0 引言

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

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

1 霍夫曼壓縮算法

1.1 基本原理

霍夫曼算法是D.A.Huffman 在1952 年發現的一種基于信號概率的數據無損壓縮算

法［2］。它的壓縮思想的核心是構建霍夫曼樹，又稱為最優二叉樹。通過“葉子”和分支的權重，來尋找帶權路徑最小的二叉樹［3］。

比如有五個權重分別為1，1，2，2，4的符號，構建最優二叉樹步驟如圖1所示：

圖1 構建最優二叉樹步驟圖

最后，根據構建好的二叉樹按左0右1的規則進行編碼，易懂且簡單方便。

1.2 算法結果分析

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

2 游程壓縮算法

2.1 信源

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

2.2 基本原理

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

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

例如：55555555 777 99999 666666，變為（5，8）（7，3）（9，5）（6，6），這樣編碼位數遠小于原始數據的位數。

2.3 算法結果分析

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

2.3.1 GIF和PNG類型的圖像

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

2.3.2 JPG類型的圖像

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

圖2 JPG圖像壓縮前

圖3 JPG圖像壓縮后

2.3.3 bmp圖像

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

圖4 bmp圖像壓縮前

圖5 bmp圖像壓縮后

3 LZW算法

3.1 基本原理

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

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

3.2 算法結果分析

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

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

4 三種算法小結

表1 三種算法總結表

5 結語

本文對常用的三種無損壓縮算法的原理及適用情況進行了研究與總結。根據信源的不同，這三種算法的壓縮效果不同。霍夫曼和游程算法壓縮速度較快，LZW的適用范圍最為廣闊，并且有較好的壓縮率。總之，根據信源的不同可以選擇不同的壓縮算法，以達到想要的效果。

參考文獻

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

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

［3］時國平.關于霍夫曼編碼數據壓縮效果［J］.池州學院學報，2008，22（5）﹕46-48

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

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

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

指導教師：汪沛，副教授。