LZW算法在DEM數(shù)據(jù)壓縮中的應(yīng)用研究

摘 要：在虛擬地形環(huán)境領(lǐng)域，數(shù)據(jù)壓縮是解決海量DEM數(shù)據(jù)的存儲(chǔ)、傳輸、處理難題的直接有效辦法。在實(shí)時(shí)漫游中，DEM數(shù)據(jù)的高效壓縮和傳輸變得越來(lái)越重要，已經(jīng)成為影響系統(tǒng)性能的關(guān)鍵技術(shù)之一。文章主要研究了數(shù)據(jù)壓縮算法在DEM數(shù)據(jù)壓縮中的應(yīng)用問(wèn)題。首先分析了DEM數(shù)據(jù)的概念及數(shù)據(jù)特點(diǎn)，通過(guò)對(duì)比各類壓縮算法壓縮性能，選用無(wú)損的LZW算法對(duì)DEM數(shù)據(jù)進(jìn)行壓縮。并分析了評(píng)價(jià)DEM數(shù)據(jù)壓縮算法的指標(biāo)。在實(shí)現(xiàn)對(duì)DEM數(shù)據(jù)的無(wú)損壓縮時(shí)，介紹了LZW算法的編碼原理和執(zhí)行步驟，分析了LZW算法的優(yōu)缺點(diǎn)，提出了對(duì)LZW算法的改進(jìn)方法，實(shí)說(shuō)現(xiàn)了改進(jìn)后的LZW算法對(duì)DEM數(shù)據(jù)的壓縮。通過(guò)實(shí)驗(yàn)測(cè)試，分析評(píng)價(jià)了LZW算法的壓縮性能。

關(guān)鍵詞：DEM數(shù)據(jù)；LZW算法；數(shù)據(jù)壓縮

1 DEM數(shù)據(jù)壓縮研究的現(xiàn)狀（Actuality of the Research）

近年來(lái)，DEM數(shù)據(jù)的壓縮存儲(chǔ)成為當(dāng)前國(guó)內(nèi)外計(jì)算機(jī)科學(xué)研究與應(yīng)用的前沿課題，歸結(jié)起來(lái)，共分為兩類。一類是用不同的DEM表示模型來(lái)化簡(jiǎn)DEM格網(wǎng)，達(dá)到去除冗余數(shù)據(jù)的目的。另一類是直接利用各類數(shù)據(jù)壓縮算法實(shí)現(xiàn)對(duì)DEM數(shù)據(jù)的壓縮。

文章的研究目標(biāo)：在DEM精度無(wú)損的條件下實(shí)現(xiàn)對(duì)DEM的無(wú)損壓縮和解壓縮；文章選用的壓縮算法要求具有良好的壓縮效能，以供實(shí)用參考。

2 DEM數(shù)據(jù)壓縮算法的選擇

文章選擇DEM壓縮算法的LZW算法的總體壓縮效能較高，無(wú)論是壓縮的比率，還是壓縮、解壓縮的執(zhí)行效率都較為優(yōu)越。

DEM數(shù)據(jù)壓縮評(píng)價(jià)指標(biāo)

數(shù)據(jù)壓縮機(jī)制的設(shè)計(jì)需要在壓縮能力、失真度、所需計(jì)算資源以及其它需要考慮的不同因素之間進(jìn)行折衷。具體標(biāo)準(zhǔn)如下。

采用無(wú)損壓縮算法標(biāo)準(zhǔn)：壓縮比和編碼復(fù)雜度。同時(shí)，文章引申一個(gè)新的評(píng)價(jià)指標(biāo)——壓縮效率。

壓縮效率（W）：W=原數(shù)據(jù)量？鄢（1-R）/t，很顯然R越小，t越小，相應(yīng)的壓縮效率W越大。

3 基于改進(jìn)的字典型LZW算法的DEM數(shù)據(jù)壓縮

3.1 LZW算法分析

LZW算法與其他算法相比具有自適應(yīng)的特點(diǎn)，即可以根據(jù)壓縮內(nèi)容不同來(lái)建立不同字典，以減少冗余度，提高壓縮比；并且解壓時(shí)這個(gè)字典無(wú)需與壓縮代碼同時(shí)傳送，而是在解壓過(guò)程中逐步建立與壓縮時(shí)完全相同的字典。因此，LZW算法是一種解碼速度與壓縮性能較好的壓縮算法。

3.2 LZW算法的改進(jìn)

對(duì)LZW算法的改進(jìn)，主要從提高代碼執(zhí)行的效率和進(jìn)一步提高壓縮比例兩個(gè)方面進(jìn)行。

3.3 實(shí)現(xiàn)零搜索

LZW 算法在早期由于內(nèi)存空間的限制，編碼表不能過(guò)大，但這樣導(dǎo)致以字頭碼和字尾碼建立索引時(shí)，要依賴于一個(gè)有效的索引公式。但不同的字頭碼和字尾碼可能產(chǎn)生相同的索引值，字典存放地址也就可能會(huì)被占用，于是還得查找一個(gè)自由的地址空間，這樣使得算法在查找過(guò)程上開(kāi)銷不少。為了使根據(jù)字頭碼和字尾碼建立的索引值不重復(fù)，可以以其本身的值合成為內(nèi)存地址，依靠指針進(jìn)行定位，從而不再需要查找過(guò)程。如今32位操作系統(tǒng)成為主流，其尋址能力可達(dá)4GB，再加上硬件設(shè)施大大提高，使得上述方法成為可能。在標(biāo)準(zhǔn)數(shù)據(jù)處理上采用這種方法，編碼表實(shí)際使用內(nèi)存空間僅為2MB（2^20）。

3.4 動(dòng)態(tài)編碼

使用動(dòng)態(tài)編碼長(zhǎng)度進(jìn)一步提高壓縮率。這種方法允許壓縮代碼長(zhǎng)度的更改，即利用不固定長(zhǎng)度的代碼存儲(chǔ)壓縮數(shù)據(jù)。

采用動(dòng)態(tài)編碼長(zhǎng)度存儲(chǔ)，編碼是從9位開(kāi)始的，數(shù)據(jù)存儲(chǔ)也是從9位開(kāi)始，直到編碼增加到10位時(shí)，存儲(chǔ)代碼才增加到10位。處理的過(guò)程的簡(jiǎn)單代碼：

//shiftbits： 用于位處理，作臨時(shí)位

//runbits： 當(dāng)前處理位

// code： 存儲(chǔ)的數(shù)據(jù)

tempcode= code* 2^shiftbits+ tempcode；

shiftbits= shiftbits+ runbits；

while （shiftbits>= 8）

{

blockbuf（i） = tempcode h00ff；

i= i+ 1；

tempcode= tempcode＼（2^8）；

shiftbits= shiftbits-8；

// loop；

}

在LZW算法的基礎(chǔ)上實(shí)現(xiàn)零搜索和動(dòng)態(tài)編碼，可以進(jìn)一步提高算法的效率。

3.5 基于相同DEM數(shù)據(jù)不同壓縮比率的壓縮測(cè)試

在壓縮每一份DEM數(shù)據(jù)時(shí)，可以通過(guò)控制壓縮比率，進(jìn)行測(cè)試，尋求可能得到的最佳壓縮效率值，供使用參考。

文章隨機(jī)選用了兩份數(shù)據(jù)，在分別控制其壓縮比率為：90%，80%，70%，60%，50%，40%，30%，20%，10%的條件下，進(jìn)行壓縮測(cè)試，得到結(jié)果分別如表1，表2。

從表1、表2可以明顯得出：（1）壓縮時(shí)間與壓縮比例呈負(fù)相關(guān)。即壓縮比值越小（壓縮后的文件越小），所消耗的壓縮時(shí)間越長(zhǎng)，這一點(diǎn)正好符合實(shí)際的預(yù)想。（2）壓縮效率W與壓縮比例呈明顯的負(fù)相關(guān)。即隨著壓縮比值的變小，壓縮效率明顯的增大。盡管在壓縮的過(guò)程中，壓縮時(shí)間有所增加，但并不會(huì)影響到壓縮效率的增大。（3）在實(shí)際應(yīng)用時(shí)，為了得到最大的壓縮效率值，通常應(yīng)將文件進(jìn)行最大化的壓縮。

參考文獻(xiàn)

[1]吳樂(lè)南.數(shù)據(jù)壓縮[M].電子工業(yè)出版社，2000.

作者簡(jiǎn)介：畢記省（1978-），女，遼寧省大連市人，工作單位：61206部隊(duì)，職務(wù)：工程師，研究方向：測(cè)繪。