基于大字典的LZW壓縮算法的降熵改進

陸振龍　張　箐

1(中國科學院遙感與數(shù)字地球研究所　北京 100094)2(中國科學院大學　北京 100094)

?

基于大字典的LZW壓縮算法的降熵改進

陸振龍1,2張箐1*

1(中國科學院遙感與數(shù)字地球研究所北京 100094)2(中國科學院大學北京 100094)

摘要在分析壓縮算法LZW的基礎上，針對LZW算法在字典規(guī)模增大時出現(xiàn)的壓縮后數(shù)據(jù)平均信息熵快速增大的不足，提出一種改進的壓縮算法。利用數(shù)據(jù)中普遍存在的空間相關性，在保存大字典的同時縮小每次壓縮實際使用的字典范圍，以此減小壓縮后數(shù)據(jù)的信息熵。給出改進算法與LZW壓縮算法的性能對比，實驗結(jié)果表明改進算法在減小壓縮后數(shù)據(jù)的信息熵方面取得了2%～16.9%的優(yōu)化。

關鍵詞數(shù)據(jù)壓縮算法信息熵數(shù)據(jù)相關性

0引言

遙感技術增強了人類觀察和探索世界的能力，擴展了人類可以觀測的范圍，縮短了觀察宏觀現(xiàn)象所需的時間，同時使得因自然條件惡劣無法實地觀察的環(huán)境也能用遙感技術得以觀察。人以眼睛進行觀察活動時，可以快速處理觀察到的圖像并作出響應。應用遙感技術時，若能提高快速響應能力，將大大增強遙感技術的效果。但是，提高系統(tǒng)響應速度的一個巨大挑戰(zhàn)來源于在帶寬一定的條件下不斷增大的遙感數(shù)據(jù)量和遠距離的傳輸。數(shù)據(jù)壓縮技術在發(fā)送端通過去除數(shù)據(jù)冗余而減少實際傳輸?shù)臄?shù)據(jù)量，從而縮短了數(shù)據(jù)傳輸時間。

基于字典的數(shù)據(jù)壓縮算法在許多應用領域取得了良好的壓縮效果。文獻[1]提出的TCP自適應壓縮傳輸方案中自適應壓縮器采用基于字典的壓縮方法與Huffman編碼相結(jié)合的壓縮編碼方案。文獻[2]對三大類共10種壓縮的全文自索引方法進行了分析和比較，基于字典的LZ壓縮算法的全文自索引算法在索引建立、定位和提取幾個方面有明顯的優(yōu)勢。

基于字典的數(shù)據(jù)壓縮算法是一類無損壓縮算法，其基本思想是，在數(shù)據(jù)中普遍存在著結(jié)構(gòu)冗余，數(shù)據(jù)中的某些“詞組”會重復出現(xiàn)。因此，基于字典的壓縮算法使用滑動窗口或者顯式的字典，用于存儲已經(jīng)壓縮的數(shù)據(jù)中可能會在將來重復出現(xiàn)的“詞組”，當發(fā)現(xiàn)再次出現(xiàn)的詞組時，就發(fā)送字典的索引代表詞組本身。當用于表示字典索引的數(shù)據(jù)量少于表示詞組所需的數(shù)據(jù)量時，能夠取得好的壓縮效果。在基于字典的數(shù)據(jù)壓縮算法中，字典容量大小與壓縮效果有著密切的聯(lián)系。本文對此進行研究，并提出了改進方法。

1基于字典的壓縮算法LZW及相關改進算法分析

1.1應用LZW算法的數(shù)據(jù)壓縮系統(tǒng)介紹

應用LZW算法[3]的壓縮系統(tǒng)的編碼過程一般可以用圖1所示。

圖1應用LZW的壓縮系統(tǒng)編碼流程

LZW

壓縮部分(即Ⅰ過程)在編碼端完成兩項工作：其一是在字典中查找當前的詞組是否存在。如果存在，則繼續(xù)查找是否存在更長的詞組；否則，用對應字典索引替代當前詞組作為編碼輸出。其二是將當前字典不存在的詞組作為新詞組加入字典，完成字典的更新。傳統(tǒng)

LZW

算法每次形成并加入長度增加一個符號的新詞組；

LZMW

[4]

和

LZAP

等算法

[5]

在如何形成新詞組方面做出改進，改進算法使字典適應輸入數(shù)據(jù)的速度加快。

1.2應用LZW的壓縮系統(tǒng)前后數(shù)據(jù)特性分析

如圖1所示，應用LZW算法的壓縮系統(tǒng)有過程Ⅰ和過程Ⅱ兩個處理階段。過程Ⅰ將值域為[Pmin,Pmax]的待壓縮數(shù)據(jù)X處理形成值域為[Vmax-1]的數(shù)據(jù)Y，其中Vmax是LZW的字典容量大小。例如，用8bit表示一個像素點的灰度圖像使用字典容量為216的LZW算法經(jīng)過程Ⅰ處理，是將值域為[0,28-1]的數(shù)據(jù)流X處理形成值域為[0,216-1]的數(shù)據(jù)流Y。

過程Ⅱ?qū)?shù)據(jù)流Y用信道符號集{α1,α2,…,αr}編碼成適應信道傳遞的符號流Z。例如，二元離散信道符號集為{0,1}，即α1=0，α2=1。則過程Ⅱ?qū)⒅涤驗閇0,216-1]的數(shù)據(jù)流Y按照單一可譯的原則編碼成{0,1}的比特流。

(1)

其中，H(S)表示信源信息熵，即數(shù)據(jù)流Y的信息熵，r表示信道符號種類。這里以符號集為{0,1}的信道為例，因此上式改寫為：

(2)

對于單一可譯碼平均碼長的下界，可以通過擴展信源或采用優(yōu)秀的編碼算法如Huffman，算術編碼的方式使平均碼長接近這個下界[6]。Gzip壓縮軟件的一個核心部分就是LZ壓縮算法與Huffman編碼的組合。因此，本文用數(shù)據(jù)流Y(經(jīng)過程Ⅰ處理后的數(shù)據(jù))的信息熵作為衡量指標來比較在待壓縮數(shù)據(jù)源X相同的情況下，過程Ⅰ使用不同的壓縮算法產(chǎn)生的數(shù)據(jù)流Y可以達到的最短平均碼長。

1.3LZW改進算法分析

DTLZW算法[8]提出傳統(tǒng)LZW是基于平穩(wěn)遍歷信源的假設，但是實際信源多為局部平穩(wěn)。因此提出雙串表，也可以看作是雙字典的改進算法，利用信源是局部平穩(wěn)的特點，在當前字典不能很好符合當前局部時(表現(xiàn)為在當前串表中找到匹配的概率降低)，快速切換至另一個串表，從而保證壓縮效率能維持在較高的水平上。

LZSWH算法[9]利用LZ77和LZ78兩類壓縮算法對于不同類型的數(shù)據(jù)壓縮性能不同，將這兩類算法的代表LZSS和LZW結(jié)合，并加入了H參數(shù)，控制LZSWH向LZSS和LZW的偏向程度，得到了對于不同類型數(shù)據(jù)比單一算法更好的適應性。

文獻[10]提出一種綜合了LZW遠距離記憶性好和LZSS對于信源特性的快速適應特性優(yōu)點的壓縮算法，每輪壓縮均先后使用LZW與LZSS進行編碼，并采用能搜索到更長匹配的編碼方式進行輸出，同時用1bit來標示采用的編碼方式是LZW還是LZSS。另外因為小序號字典項輸出時占用bit數(shù)少，但是常常被命中率低的字典項占用，提出將命中率低的字典項，主要是生成較長的字典項過程中產(chǎn)生的中間字典項，逆序加入字典，分配較大的字典序號，從而提高小序號字典項的命中率，增加了壓縮效率。

LZC算法將字典的初始容量預設得較小，因此初始階段，Y的平均碼長將比較小。當字典裝滿時，將字典容量動態(tài)增長為2倍，此時生成數(shù)據(jù)Y的平均碼長也增加1。如此重復，直至字典的大小達到預設的最大容量。LZC對字典采用動態(tài)增長的手段，降低了Y數(shù)據(jù)流的平均碼長。例如，最大字典容量為216的LZW和LZC算法，LZW產(chǎn)生的數(shù)據(jù)流Y采用定長編碼的平均碼長為16bit，LZC字典中項數(shù)少于初始容量512項時，產(chǎn)生的數(shù)據(jù)平均碼長為9bit；當字典逐漸裝滿，達到512項時，字典容量增長為2倍，產(chǎn)生數(shù)據(jù)的平均碼長為10bit；如此重復，直至字典達到216項，產(chǎn)生數(shù)據(jù)的平均碼長為16bit。因此LZC產(chǎn)生的數(shù)據(jù)Y的平均碼長短于LZW產(chǎn)生的數(shù)據(jù)的平均碼長。

LZT算法的一個特點是對數(shù)據(jù)流Y用phased-in碼[11]進行編碼，這將節(jié)約開始階段的bit數(shù)，降低平均碼長，但隨著字典的裝滿，這部分的作用將逐漸變小。

通過實驗結(jié)果分析，如表1所示，LZW或現(xiàn)有的各改進算法在字典容量增大時都會出現(xiàn)對數(shù)據(jù)流Y進行過程Ⅱ編碼時平均碼長快速增大的現(xiàn)象，這是不利于使用LZW的壓縮系統(tǒng)的壓縮效果的。字典容量越大，數(shù)據(jù)流Y的信息熵越大，使平均碼長的下限越長。

表1　不同字典大小的LZW及其改進算法產(chǎn)生的數(shù)據(jù)Y的

但同時也不能過度限制字典容量的大小，因為大字典可以保存更多的詞組，從而能找到更多的匹配，有利于壓縮。因此，需要在保持大字典容量的情況下，在降低數(shù)據(jù)流Y的信息熵方面改進，以取得更低的平均碼長。

2改進算法的提出

LZW算法的大字典容量能保存更多詞組，找到更多的匹配，所以，需要在保持大字典容量的前提下降低經(jīng)過程Ⅰ處理的數(shù)據(jù)流Y的信息熵。

對不同圖像進行觀察，發(fā)現(xiàn)圖像內(nèi)部普遍存在空間周期性，即某個圖像特征往往會重復出現(xiàn)，如圖2所示。圖3所示為某圖像按行掃描后的像素曲線圖，圖中B段圖像曲線與已經(jīng)發(fā)生的A段曲線極為相似，說明這兩段圖像代表相似的圖像模式。若B中當前的一個詞組在A中F處找到匹配，說明當前區(qū)域B與區(qū)域A中有一部分特征相同，則B與A將以高概率屬于相似的圖像模式，即B中下一個詞組也將以高概率落在這個圖像模式中。因此在每次找到較長的字典項匹配后，我們可以記錄下此次匹配的位置，即區(qū)域A中的F處，下輪搜索時就在F處的附近進行。

圖2　圖像的空間周期性

圖3　圖像像素曲線圖

因此，本文提出以下改進處理。首先，將字典設計成能夠保存圖像空間周期性的結(jié)構(gòu)，即空間上相鄰的詞組在字典中的位置也相鄰。為了使字典具有這種性質(zhì)，在將新詞組寫入字典時，用下式確定寫入字典的位置：

Indexi=[(Index(i-1)+1)MOD(Vmax)]+Vstart

(3)

其中Indexi代表第i個詞組加入字典的位置，MOD為模運算，Vmax代表大字典的容量，Vstart代表LZW改進算法中不能被新字典項覆蓋的部分，一般用字典的[0,Vstart-1]寫入所有可能的單個信源符號，對于用8bit表示一個像素點的灰度圖像來說，Vstart為256。式(3)可以簡單解釋為“循環(huán)寫入”，例如，對于字典容量為216項的改進字典，若上一項詞組位置為4096，則下一項寫入位置4097；若上一項位置為65 535，則下一項寫入位置256。

這種改進字典中各項的相對位置如實反映了數(shù)據(jù)中存在的空間相關性。改進算法利用這種保存在字典中的空間相關性做如下操作，在每次搜索及輸出之前，結(jié)合上次在字典中找到匹配的位置，做出是使用全部字典還是使用局部字典的決定，相應的處理如下：

If(上輪搜索在大字典中F位置找到長度大于2的匹配)

{

本輪搜索時選擇F位置前后L范圍作為局部字典進行搜索

如果在局部字典中找到匹配，則輸出該匹配在局部字典中的相對位置

}

else{

在大字典中搜索

如果在大字典中找到匹配，則輸出該匹配在大字典中的位置

}

因此，利用圖像中的空間周期性，很多數(shù)據(jù)都可以在局部字典中找到；而在局部字典中找到的匹配可以用該匹配在局部字典中的相對位置代替匹配在整個大字典中的絕對位置作為輸出。如果使用LZW，過程Ⅰ輸出匹配在大字典中的絕對位置，因此數(shù)據(jù)流Y的值域為[0,Vmax-1]。而用本文提出的改進算法，如果上個詞組在字典中找到匹配，則輸出當前詞組在局部字典中的相對位置，相對位置的值域為[0,2L-1]。雖然改進算法編碼后產(chǎn)生的數(shù)據(jù)流Y的值域相同，但分布不同。改進算法將一些分散在字典中各位置的輸出集中在一個相對小的范圍中，主要成分變?yōu)榱薣0,Vstart+2L]，各成分概率分布更加不均勻，從而降低了數(shù)據(jù)流Y的信息熵。

綜上所述，本文提出的改進算法的流程如圖4所示。

圖4　基于大字典的壓縮算法LZW降熵改進算法流程圖

3改進算法實驗

本文首先對一948×450的圖像用LZW和本文提出的改進算法分別進行壓縮(即圖1中的過程Ⅰ)，并對使用不同算法產(chǎn)生的數(shù)據(jù)流Y中各符號概率分布進行統(tǒng)計，并對出現(xiàn)頻數(shù)取log得到直方圖對比，即圖5所示。由圖5左側(cè)直方圖可以看出，在過程Ⅰ中用LZW處理后產(chǎn)生的數(shù)據(jù)流Y中各符號近似于均等分布，此時數(shù)據(jù)流Y的信息熵較大；由右側(cè)直方圖看出，若運用本文提出的改進算法，此時數(shù)據(jù)流Y的分布更加集中，因此信息熵更低。因此，用改進算法更加有利于過程Ⅱ取得更短的平均碼長。

圖5　采用LZW和本文改進算法后的數(shù)據(jù)流各符號概率分布對比

然后對此948×450的圖像在圖1的過程Ⅰ中采用不同字典容量，不同算法分別進行壓縮，并計算產(chǎn)生的數(shù)據(jù)流Y的信息熵或最短平均碼長，得到表2所示。從表2看出，改進算法在不同字典容量都能取得比LZW和LZC更加低的信息熵，在大字典容量時取得的降熵效果更加明顯。

表2　相同數(shù)據(jù)采用不同字典容量的算法處理后的數(shù)據(jù)流的信息熵

最后對53幅圖像數(shù)據(jù)分別用相同容量的LZW，LZC和本文實現(xiàn)的改進算法加以壓縮，將壓縮后數(shù)據(jù)的平均信息熵進行比較，得到圖6所示。改進算法相較采用動態(tài)增長字典的LZC取得了7.47%～20.3%的優(yōu)化；相比LZW與熵編碼的組合能取得2%～16.9%的降熵，說明在過程Ⅰ中采用改進算法能取得較好的降熵效果。圖6同時說明改進算法較LZW算法能對不同特性的數(shù)據(jù)取得普遍的降熵效果，說明了本文提出的改進算法的有效性。

圖6　采用LZW和本文改進算法后的數(shù)據(jù)流信息熵曲線對比

4結(jié)語

本文對基于字典的壓縮算法LZW進行了研究。研究結(jié)果顯示：基于大容量字典的LZW壓縮算法的相比基于小字典的LZW算法在壓縮后數(shù)據(jù)的平均信息熵方面顯著增大，這對于后續(xù)進行熵壓縮編碼不利。通過實驗發(fā)現(xiàn)，數(shù)據(jù)中存在普遍的空間周期性，這為提出基于大容量字典的降熵壓縮算法提供了可能性。本文使用在大容量字典中自動選取的局部字典進行實際壓縮和編碼，使壓縮后數(shù)據(jù)流Y中各成分的概率分布更加集中，降低了平均信息熵。經(jīng)實驗驗證，改進后的算法在降低壓縮后數(shù)據(jù)的平均信息熵方面取得了2%～16.9%的優(yōu)化。

今后的研究將集中在以下兩個方面，其一，根據(jù)本文采用的局部字典選擇策略和已有的實驗結(jié)果，對局部字典選擇算法進一步改進，以達到能在選擇出的局部字典中以更大概率找到匹配。再配合以本文提出的改進算法本身具有的低平均信息熵特性，從而取得更好的壓縮效果。其二，針對本改進算法使用局部字典進行搜索和輸出的特性進一步設計字典的數(shù)據(jù)結(jié)構(gòu)，優(yōu)化本改進算法的運行效率。同時進一步分析本改進算法產(chǎn)生的數(shù)據(jù)流的分布特性，為下一步使用其他壓縮算法提供先驗知識，從而提升工程運用本改進算法的系統(tǒng)整體處理速度。

參考文獻

[1] 牟璇,王俊峰,王敏,等.TCP自適應壓縮傳輸方案研究[J].計算機應用與軟件,2013,30(11):279-282.

[2] 路煒,劉燕兵,王春露,等.壓縮的全文自索引算法研究[J].計算機應用與軟件,2014,31(3):11-15,35.

[3]TerryAWelch.ATechniqueforHigh-PerformanceDataCompression[J].IEEEComputer,1984,17(6):8-19.

[4]MillerVSMN.WegmanIEEEInternationalConferenceonDigitalTechnology[C]//SpanningtheUniverse:Communications,1988.Berlin,Springer,1988:131-140.

[5]SalomonDavid,MottaGiovanni.Handbookofdatacompression[M].London:Springer,2010.

[6] 姜丹.信息論與編碼[M].安徽:中國科學技術大學出版社,2004.

[7] 吳樂南.數(shù)據(jù)壓縮[M].北京:電子工業(yè)出版社,2012.

[8] 吳宇新,余松煜.對LZW算法的改進及其在圖象無損壓縮中的應用[J].上海交通大學學報,1998,32(9):112-115.

[9] 華強.LZ77和LZ78在數(shù)據(jù)壓縮中的組合帶參運用[J].小型微型計算機系統(tǒng),2000,21(2):100-104.

[10] 崔業(yè)勤,高建國.基于“虛段”方法的LZ混合無損壓縮算法[J].計算機應用與軟件,2007,24(3):140-141.

[11]BellTimothyC,JohnJCleary,IanHughWitten.TextCompression[M].EnglewoodCliffs:Prentice-Hall,1990.

IMPROVEMENT OF ENTROPY REDUCTION FOR LZW COMPRESSION ALGORITHMBASEDONBIGDICTIONARY

Lu Zhenlong1,2Zhang Jing1*

1(Institute of Remote Sensing and Digital Earth,Chinese Academy of Sciences,Beijing 100094,China)2(University of Chinese Academy of Sciences,Beijing 100094,China)

AbstractBased on the analysis of compression algorithm LZW, this paper puts forward an improved compression algorithm aimed at the deficiency of LZW that the average information entropy block of compressed data grows dramatically along with the increase of dictionary scale. This algorithm utilises the spatial correlation commonly existed in data, while saving the big dictionary it also narrows the range of the dictionary that actually used in each compression, so as to reduce the information entropy of the compressed data. The paper provides performance comparison between the improved algorithm and LZW compression algorithm, the result of experiment indicates that the improved algorithm achieves an optimisation by 2%～16.9% in the aspect of data information entropy after the compression is reduced.

KeywordsData compressionAlgorithmsEntropy of informationData correlation

收稿日期：2015-01-09。陸振龍，碩士，主研領域：數(shù)據(jù)壓縮。張箐，教授級高工。

中圖分類號TP391.7

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.068