LZW算法在DEM數據壓縮中的應用研究

摘 要：在虛擬地形環境領域，數據壓縮是解決海量DEM數據的存儲、傳輸、處理難題的直接有效辦法。在實時漫游中，DEM數據的高效壓縮和傳輸變得越來越重要，已經成為影響系統性能的關鍵技術之一。文章主要研究了數據壓縮算法在DEM數據壓縮中的應用問題。首先分析了DEM數據的概念及數據特點，通過對比各類壓縮算法壓縮性能，選用無損的LZW算法對DEM數據進行壓縮。并分析了評價DEM數據壓縮算法的指標。在實現對DEM數據的無損壓縮時，介紹了LZW算法的編碼原理和執行步驟，分析了LZW算法的優缺點，提出了對LZW算法的改進方法，實說現了改進后的LZW算法對DEM數據的壓縮。通過實驗測試，分析評價了LZW算法的壓縮性能。

關鍵詞：DEM數據；LZW算法；數據壓縮

1 DEM數據壓縮研究的現狀（Actuality of the Research）

近年來，DEM數據的壓縮存儲成為當前國內外計算機科學研究與應用的前沿課題，歸結起來，共分為兩類。一類是用不同的DEM表示模型來化簡DEM格網，達到去除冗余數據的目的。另一類是直接利用各類數據壓縮算法實現對DEM數據的壓縮。

文章的研究目標：在DEM精度無損的條件下實現對DEM的無損壓縮和解壓縮；文章選用的壓縮算法要求具有良好的壓縮效能，以供實用參考。

2 DEM數據壓縮算法的選擇

文章選擇DEM壓縮算法的LZW算法的總體壓縮效能較高，無論是壓縮的比率，還是壓縮、解壓縮的執行效率都較為優越。

DEM數據壓縮評價指標

數據壓縮機制的設計需要在壓縮能力、失真度、所需計算資源以及其它需要考慮的不同因素之間進行折衷。具體標準如下。

采用無損壓縮算法標準：壓縮比和編碼復雜度。同時，文章引申一個新的評價指標——壓縮效率。

壓縮效率（W）：W=原數據量？鄢（1-R）/t，很顯然R越小，t越小，相應的壓縮效率W越大。

3 基于改進的字典型LZW算法的DEM數據壓縮

3.1 LZW算法分析

LZW算法與其他算法相比具有自適應的特點，即可以根據壓縮內容不同來建立不同字典，以減少冗余度，提高壓縮比；并且解壓時這個字典無需與壓縮代碼同時傳送，而是在解壓過程中逐步建立與壓縮時完全相同的字典。因此，LZW算法是一種解碼速度與壓縮性能較好的壓縮算法。

3.2 LZW算法的改進

對LZW算法的改進，主要從提高代碼執行的效率和進一步提高壓縮比例兩個方面進行。

3.3 實現零搜索

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

3.4 動態編碼

使用動態編碼長度進一步提高壓縮率。這種方法允許壓縮代碼長度的更改，即利用不固定長度的代碼存儲壓縮數據。

采用動態編碼長度存儲，編碼是從9位開始的，數據存儲也是從9位開始，直到編碼增加到10位時，存儲代碼才增加到10位。處理的過程的簡單代碼：

//shiftbits： 用于位處理，作臨時位

//runbits： 當前處理位

// code： 存儲的數據

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算法的基礎上實現零搜索和動態編碼，可以進一步提高算法的效率。

3.5 基于相同DEM數據不同壓縮比率的壓縮測試

在壓縮每一份DEM數據時，可以通過控制壓縮比率，進行測試，尋求可能得到的最佳壓縮效率值，供使用參考。

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

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

參考文獻

[1]吳樂南.數據壓縮[M].電子工業出版社，2000.

作者簡介：畢記省（1978-），女，遼寧省大連市人，工作單位：61206部隊，職務：工程師，研究方向：測繪。