应用多线程和Huffman编码压缩SVG矢量空间数据

谢亦才　钟剑

摘要：在分析矢量数据以及SVG的结构特点、多线程和Huffman算法原理的基础上，提出了用多线程和Huffman算法对矢量数据进行压缩的流程，大大缩短了压缩时间。

关键词：多线程；Huffman算法；矢量数据压缩

中图分类号：TP391文献标识码：A 文章编号：1009-3044（2012）30-7332-03

随着网络GIS快速发展，需要传输的空间数据量急剧增长，而网络带宽的提速相对滞后。因此，为了提高网络GIS效率，对空间数据的压缩技术的研究越来越受到重视。

对数据的压缩分为无损压缩和有损压缩，常见的无损压缩方法有Huffman编码和LZW等，这些无损压缩方法同样适用于对空间数据的压缩。本文提出综合应用多线程和Huffman编码压缩空间矢量数据以提高压缩效率，减少压缩时间。

1 矢量数据结构及其特点

矢量数据通常由两种数据模型表示：拓扑数据结构和简单数据结构（又称无拓扑数据结构）。其中简单数据结构通过点、线、面来表示地理实体，而地理实体坐标用其边界的坐标的X和Y值来表示。点由一个（X，Y）表示；线由多个（X，Y）排列在一起表示；面则由闭合的一系列（X，Y）表示。每个地理实体自成一体，各自维护自己的坐标和属性信息，没有相邻或相离等拓扑信息[1]。比如SVG格式的空间矢量数据等。

2 多线程原理

计算机中运行的程序称为进程，每个进程都有独立的一块内存空间和一组系统资源。而一个进程可以有多个线程同时执行。线程是进程的最小执行单元。多线程之间相互独立，各自完成自己的任务，可有效提高进程的执行速度。

在 Java 中，有两种创建线程的方法[2]：

第一种是通过继承classThread实现多线程

classThread中有两个最重要的函数run（）和start（）。其中run（）函数必须把要在多个线程中并行处理的代码放入其中。通过调用start（）函数来调用run（）函数。在调用start（）的时候，start（）函数会首先进行与多线程相关的初始化（这也是为什么不能直接调用run（）函数的原因），然后再调用run（）函数。

第二种是通过实现 Runnable 接口的类来实现。

如果有一个类，它已继承了某个类，又想实现多线程，那就可以通过实现Runnable接口来实现。Runnable接口只有一个run（）函数。把一个实现了Runnable接口的对象作为参数产生一个Thread对象，再调用Thread对象的start（）函数就可执行并行操作。如果在产生一个Thread对象时以一个Runnable接口的实现类的对象作为参数，那么在调用start（）函数时，start（）会调用Runnable接口的实现类中的run（）函数。

3 Huffman编码压缩思想

霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

构造Huffman编码的算法：

1）将需压缩文件的字符按照出现频率递减的顺序排列。假设每个字符出现的频率作为权重值 wi（i=1，2……n），将w1、w2、…，wn看成是有n 棵树的森林（每棵树仅有一个结点）；

2）在森林中选出两个根结点的权重值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权重值为其左、右子树根结点权重值之和。在合并运算时，权重值大的字符用编码0表示，权重值小的符号用编码1表示；

3）从森林中删除刚被选取的两棵树，并将新树加入森林；

4）重复2）、3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树；

5）每个字符的Huffman编码就是从根节点到该字符节点路径上的0、1序列。

4 应用多线程和Huffman编码压缩SVG矢量空间数据

4.1 可行性分析

1）SVG与地图。

SVG能为地图提供标准的矢量方法，而不是特定的插件或Javaapplet等，同时提供高

质量的图形和很强的交互功能。地图符号可以由SVG的形状元素进行描述；注记由SVG的文本元素表示；图层由SVG的组元素表示【3】（图1）。

2）SVG的特点

SVG（可缩放矢量图形，Scalable Vector Graphics）是基于可扩展标记语言（XML）的，用于描述二维矢量图形的一种图形格式；它采用文本格式描述图形对象；SVG完全支持DOM （Document Object Model，文档对象模型，DOM可以以一种独立于平台和语言的方式访问和修改一个文档的内容和结构。DOM定义了表示和修改文档所需的对象、这些对象的行为和属性以及这些对象之间的关系。可以把DOM认为是文件中数据和结构的一个树形表示）。

3）多线程同步压缩分析

DOM把SVG文件以树形结构存入内存，空间中的一个面在SVG中可以用“polygon”表示，或者用“path”存储面的边界坐标，用闭合的“path”表示一个不规则的面。Path作为SVG中的一个元素，在DOM中是SVG文件树的一棵子树。这样的特点为多线程压缩提供了可能性：把对一个path元素中的空间坐标的压缩分配给一个线程，这样对SVG文件中N个path元素中的空间坐标的压缩可以分配给N个线程同步并行压缩，可以大大缩短压缩时间。

4.2 压缩算法

根据SVG的特点，利用多线程技术压缩SVG空间数据的流程如图2所示。

其中P1、P2、...Pn表示各个线程调用Huffman算法压缩空间坐标。

5 实验与结果

实验所用的硬件环境为 Intel CPU，2.9Hz，内存2G；软件环境为：Windows xp系统，Java1.6编程语言，DOM接口和Eclipse3.2开发平台。通过实验验证了本算法的可行性。

本文实验数据采用广东省行政界线的SVG矢量数据，实验的压缩时间结果如表1所示。从表1可知采用本文的多线程压缩思想后，压缩时间缩短了30%左右。

6 结论

本文充分利用多线程和Huffman算法的特点，应用在空间数据的压缩中，有效的大幅缩短了压缩时间。

参考文献：

[1] 薛胜，潘懋，王勇.多边形叠置分析算法研究[J].计算机工程与应用，2003，39（2）：57-60.

[2] Bilevis Daniel J. Berg.深入学习：Java 多线程编程[M].北京：电子工业出版社，2000.

[3] 尹章才.地图表达机制及其基于可扩展标记语言的描述[D].武汉大学，2005.