謝亦才　鐘劍

摘要：在分析矢量數(shù)據(jù)以及SVG的結(jié)構(gòu)特點(diǎn)、多線程和Huffman算法原理的基礎(chǔ)上，提出了用多線程和Huffman算法對(duì)矢量數(shù)據(jù)進(jìn)行壓縮的流程，大大縮短了壓縮時(shí)間。

關(guān)鍵詞：多線程；Huffman算法；矢量數(shù)據(jù)壓縮

中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）30-7332-03

隨著網(wǎng)絡(luò)GIS快速發(fā)展，需要傳輸?shù)目臻g數(shù)據(jù)量急劇增長(zhǎng)，而網(wǎng)絡(luò)帶寬的提速相對(duì)滯后。因此，為了提高網(wǎng)絡(luò)GIS效率，對(duì)空間數(shù)據(jù)的壓縮技術(shù)的研究越來(lái)越受到重視。

對(duì)數(shù)據(jù)的壓縮分為無(wú)損壓縮和有損壓縮，常見(jiàn)的無(wú)損壓縮方法有Huffman編碼和LZW等，這些無(wú)損壓縮方法同樣適用于對(duì)空間數(shù)據(jù)的壓縮。本文提出綜合應(yīng)用多線程和Huffman編碼壓縮空間矢量數(shù)據(jù)以提高壓縮效率，減少壓縮時(shí)間。

1 矢量數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)

矢量數(shù)據(jù)通常由兩種數(shù)據(jù)模型表示：拓?fù)鋽?shù)據(jù)結(jié)構(gòu)和簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（又稱無(wú)拓?fù)鋽?shù)據(jù)結(jié)構(gòu)）。其中簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)通過(guò)點(diǎn)、線、面來(lái)表示地理實(shí)體，而地理實(shí)體坐標(biāo)用其邊界的坐標(biāo)的X和Y值來(lái)表示。點(diǎn)由一個(gè)（X，Y）表示；線由多個(gè)（X，Y）排列在一起表示；面則由閉合的一系列（X，Y）表示。每個(gè)地理實(shí)體自成一體，各自維護(hù)自己的坐標(biāo)和屬性信息，沒(méi)有相鄰或相離等拓?fù)湫畔1]。比如SVG格式的空間矢量數(shù)據(jù)等。

2 多線程原理

計(jì)算機(jī)中運(yùn)行的程序稱為進(jìn)程，每個(gè)進(jìn)程都有獨(dú)立的一塊內(nèi)存空間和一組系統(tǒng)資源。而一個(gè)進(jìn)程可以有多個(gè)線程同時(shí)執(zhí)行。線程是進(jìn)程的最小執(zhí)行單元。多線程之間相互獨(dú)立，各自完成自己的任務(wù)，可有效提高進(jìn)程的執(zhí)行速度。

在 Java 中，有兩種創(chuàng)建線程的方法[2]：

第一種是通過(guò)繼承classThread實(shí)現(xiàn)多線程

classThread中有兩個(gè)最重要的函數(shù)run（）和start（）。其中run（）函數(shù)必須把要在多個(gè)線程中并行處理的代碼放入其中。通過(guò)調(diào)用start（）函數(shù)來(lái)調(diào)用run（）函數(shù)。在調(diào)用start（）的時(shí)候，start（）函數(shù)會(huì)首先進(jìn)行與多線程相關(guān)的初始化（這也是為什么不能直接調(diào)用run（）函數(shù)的原因），然后再調(diào)用run（）函數(shù)。

第二種是通過(guò)實(shí)現(xiàn) Runnable 接口的類(lèi)來(lái)實(shí)現(xiàn)。

如果有一個(gè)類(lèi)，它已繼承了某個(gè)類(lèi)，又想實(shí)現(xiàn)多線程，那就可以通過(guò)實(shí)現(xiàn)Runnable接口來(lái)實(shí)現(xiàn)。Runnable接口只有一個(gè)run（）函數(shù)。把一個(gè)實(shí)現(xiàn)了Runnable接口的對(duì)象作為參數(shù)產(chǎn)生一個(gè)Thread對(duì)象，再調(diào)用Thread對(duì)象的start（）函數(shù)就可執(zhí)行并行操作。如果在產(chǎn)生一個(gè)Thread對(duì)象時(shí)以一個(gè)Runnable接口的實(shí)現(xiàn)類(lèi)的對(duì)象作為參數(shù)，那么在調(diào)用start（）函數(shù)時(shí)，start（）會(huì)調(diào)用Runnable接口的實(shí)現(xiàn)類(lèi)中的run（）函數(shù)。

3 Huffman編碼壓縮思想

霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統(tǒng)計(jì)編碼。屬于無(wú)損壓縮編碼?；舴蚵幋a的碼長(zhǎng)是變化的，對(duì)于出現(xiàn)頻率高的信息，編碼的長(zhǎng)度較短；而對(duì)于出現(xiàn)頻率低的信息，編碼長(zhǎng)度較長(zhǎng)。這樣，處理全部信息的總碼長(zhǎng)一定小于實(shí)際信息的符號(hào)長(zhǎng)度。

構(gòu)造Huffman編碼的算法：

1）將需壓縮文件的字符按照出現(xiàn)頻率遞減的順序排列。假設(shè)每個(gè)字符出現(xiàn)的頻率作為權(quán)重值 wi（i=1，2……n），將w1、w2、…，wn看成是有n 棵樹(shù)的森林（每棵樹(shù)僅有一個(gè)結(jié)點(diǎn)）；

2）在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)重值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)重值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)重值之和。在合并運(yùn)算時(shí)，權(quán)重值大的字符用編碼0表示，權(quán)重值小的符號(hào)用編碼1表示；

3）從森林中刪除剛被選取的兩棵樹(shù)，并將新樹(shù)加入森林；

4）重復(fù)2）、3）步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)；

5）每個(gè)字符的Huffman編碼就是從根節(jié)點(diǎn)到該字符節(jié)點(diǎn)路徑上的0、1序列。

4 應(yīng)用多線程和Huffman編碼壓縮SVG矢量空間數(shù)據(jù)

4.1 可行性分析

1）SVG與地圖。

SVG能為地圖提供標(biāo)準(zhǔn)的矢量方法，而不是特定的插件或Javaapplet等，同時(shí)提供高

質(zhì)量的圖形和很強(qiáng)的交互功能。地圖符號(hào)可以由SVG的形狀元素進(jìn)行描述；注記由SVG的文本元素表示；圖層由SVG的組元素表示【3】（圖1）。

2）SVG的特點(diǎn)

SVG（可縮放矢量圖形，Scalable Vector Graphics）是基于可擴(kuò)展標(biāo)記語(yǔ)言（XML）的，用于描述二維矢量圖形的一種圖形格式；它采用文本格式描述圖形對(duì)象；SVG完全支持DOM （Document Object Model，文檔對(duì)象模型，DOM可以以一種獨(dú)立于平臺(tái)和語(yǔ)言的方式訪問(wèn)和修改一個(gè)文檔的內(nèi)容和結(jié)構(gòu)。DOM定義了表示和修改文檔所需的對(duì)象、這些對(duì)象的行為和屬性以及這些對(duì)象之間的關(guān)系。可以把DOM認(rèn)為是文件中數(shù)據(jù)和結(jié)構(gòu)的一個(gè)樹(shù)形表示）。

3）多線程同步壓縮分析

DOM把SVG文件以樹(shù)形結(jié)構(gòu)存入內(nèi)存，空間中的一個(gè)面在SVG中可以用“polygon”表示，或者用“path”存儲(chǔ)面的邊界坐標(biāo)，用閉合的“path”表示一個(gè)不規(guī)則的面。Path作為SVG中的一個(gè)元素，在DOM中是SVG文件樹(shù)的一棵子樹(shù)。這樣的特點(diǎn)為多線程壓縮提供了可能性：把對(duì)一個(gè)path元素中的空間坐標(biāo)的壓縮分配給一個(gè)線程，這樣對(duì)SVG文件中N個(gè)path元素中的空間坐標(biāo)的壓縮可以分配給N個(gè)線程同步并行壓縮，可以大大縮短壓縮時(shí)間。

4.2 壓縮算法

根據(jù)SVG的特點(diǎn)，利用多線程技術(shù)壓縮SVG空間數(shù)據(jù)的流程如圖2所示。

其中P1、P2、...Pn表示各個(gè)線程調(diào)用Huffman算法壓縮空間坐標(biāo)。

5 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)所用的硬件環(huán)境為 Intel CPU，2.9Hz，內(nèi)存2G；軟件環(huán)境為：Windows xp系統(tǒng)，Java1.6編程語(yǔ)言，DOM接口和Eclipse3.2開(kāi)發(fā)平臺(tái)。通過(guò)實(shí)驗(yàn)驗(yàn)證了本算法的可行性。

本文實(shí)驗(yàn)數(shù)據(jù)采用廣東省行政界線的SVG矢量數(shù)據(jù)，實(shí)驗(yàn)的壓縮時(shí)間結(jié)果如表1所示。從表1可知采用本文的多線程壓縮思想后，壓縮時(shí)間縮短了30%左右。

6 結(jié)論

本文充分利用多線程和Huffman算法的特點(diǎn)，應(yīng)用在空間數(shù)據(jù)的壓縮中，有效的大幅縮短了壓縮時(shí)間。

參考文獻(xiàn)：

[1] 薛勝，潘懋，王勇.多邊形疊置分析算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（2）：57-60.

[2] Bilevis Daniel J. Berg.深入學(xué)習(xí)：Java 多線程編程[M].北京：電子工業(yè)出版社，2000.

[3] 尹章才.地圖表達(dá)機(jī)制及其基于可擴(kuò)展標(biāo)記語(yǔ)言的描述[D].武漢大學(xué)，2005.