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

?

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

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

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

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

0 引言

數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，以最小的數(shù)碼表示信源所發(fā)出的信號(hào)，或按照一定的算法對(duì)數(shù)據(jù)進(jìn)行重新組織，減少數(shù)據(jù)的冗余和存儲(chǔ)的空間的一種技術(shù)方法［1］?？偟膩?lái)說(shuō)數(shù)據(jù)壓縮包括有損壓縮和無(wú)損壓縮。

隨著社會(huì)的發(fā)展和科技的進(jìn)步，無(wú)損壓縮算法的種類越來(lái)越多，效果也越來(lái)越好。主要有霍夫曼算法、游程編碼、LZ系列等等。本文主要對(duì)霍夫曼算法、游程編碼以及LZW算法進(jìn)行了研究與討論，并總結(jié)了它們?cè)诓煌旁聪碌男Ч?，?yōu)缺點(diǎn)及壓縮率等。

1 霍夫曼壓縮算法

1.1 基本原理

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

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

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

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

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

1.2 算法結(jié)果分析

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

2 游程壓縮算法

2.1 信源

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

2.2 基本原理

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

用一個(gè)符號(hào)值或串長(zhǎng)代替具有相同值的連續(xù)符號(hào)，使符號(hào)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(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é)果分析

因?yàn)橛纬趟惴ǜm用于圖像數(shù)據(jù)的壓縮，所以本文對(duì)幾種不同類型的圖像的壓縮結(jié)果進(jìn)行了討論。

2.3.1 GIF和PNG類型的圖像

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

2.3.2 JPG類型的圖像

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

圖2 JPG圖像壓縮前

圖3 JPG圖像壓縮后

2.3.3 bmp圖像

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

圖4 bmp圖像壓縮前

圖5 bmp圖像壓縮后

3 LZW算法

3.1 基本原理

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

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

3.2 算法結(jié)果分析

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

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

4 三種算法小結(jié)

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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