基于时态的大规模SVG格式GIS数据快速比对技术

摘要

目前，时态GIS数据的存取主要采用的是关系数据库，通过在数据库中添加时间特性达到时态管理的目的，并通过数据库引擎实现和应用的接口，这种传统的时态GIS数据的存取方式效率低下。以SVG格式研究大规模时态GIS数据的增量存取是一种新途径，突破了传统的数据库存取的管理方式，但其难点之一是解决不同时间戳大规模SVG格式GIS数据的快速比对问题。本发明专利在国家自然科学基金的支持下，研究小组经过多年的研究和改进实现了不同级别数据量、不同时间戳的大规模SVG格式GIS数据的快速比对技术，比对结果的差异脚本仅包含两种类型的差异函数，实验验证该技术具有很好的应用价值和前景。

说明书

一、技术领域

本发明技术是计算机技术领域和地理信息技术领域的交叉，通过计算机及其算法技术研究解决了不同时间戳的大规模(5M以上)SVG格式的时态GIS数据的快速比对问题，比对结果的差异脚本仅包含两种类型的差异函数，即通过这些差异函数来记录GIS数据从一个时间戳到另一个时间戳的变化。

二、背景技术

空间数据和属性数据构成的GIS称为静态GIS(Static GIS)，是现实世界的一个“快照”，而对现实世界变化过程及其规律进行研究则要求GIS具有时间特性，如，对环境监测、天气预报、交通管理、测绘、土地调查等领域随时间变化的GIS进行研究，则称为时态GIS(temporal GIS)【1，2-3】，时态GIS除具有时间特性外，往往还具有数据量大的特点，即数据是海量的。目前，时态GIS数据管理通常的做法是扩展关系型的时空数据库，将时间作为一般属性，根据时间序列组织时空数据库，但存在瓶颈和不足【1】，如，不适应海量数据的管理，需要引擎支持且影响系统性能等等。面向对象的数据模型在一定程度上解决了时态GIS数据模型的某些不足，但是OODB(面向对象数据库)仍未在市场以及关键应用领域被广泛接受，因为OODB作为一个DBMS(数据库管理系统)也还不太成熟，如，缺少完全非过程性的查询语言以及视图、授权、动态方式更新和参数化性能协调等【4】，且OODB与RDB(关系数据库)之间缺少应有的兼容性，因而使得大量已建立起来的庞大的RDB客户不敢轻易地去选择OODB【1】。

因此，有必要从其他方面研究时态GIS数据的存取管理。SVG(Scalable Vector Graphics，可缩放的二维矢量图形)格式的推出为GIS的发展带来了无限生机。SVG作为W3C(World Wide Web Consortium，国际互联网标准组织)制定的一种二维矢量图形格式、一个开放、通用的标准。它具有以下特点：

1)SVG是完全矢量格式。SVG支持矢量图形的所有操作【5，6】。

2)SVG是XML的一个应用标准。以文本格式来描述地理信息内容，易于编辑、容易实现非常高效的图形搜索引擎【7，8】。

3)具备较好的兼容性。SVG容易集成在Web页中，通过浏览器可以方便的显示SVG格式的地图。

4)提供交互图形功能。可以用脚本控制用户与图形的交互，可以通过脚本编程实现对图形显示参数的调整，改变图形外观。

5)SVG支持GZIP压缩。压缩后的SVGZ可减少75％～80％，从而减轻了网络传输负载，加快了地图的显示速度。

目前，基于SVG格式的研究和应用已经非常广泛，但主要集中在表现层和中间层(见说明书附图1)，在时态数据库方面涉及的少【9，10-13】。在文章【5】、【14】、【15】、【16】和【17】中作者提到版本增量的时态GIS数据管理概念、SVG格式数据的提取以及不同的SVG格式数据之间比对等思想，为使用SVG存取时态GIS数据奠定了基础。以SVG格式研究大规模时态GIS 数据的增量存取是一种新途径，突破了传统的数据库存取的管理方式，但其难点之一是解决不同时间戳大规模SVG格式GIS数据的快速比对问题，能否合理并有效地解决该问题是研究SVG格式的时态GIS数据增量存取的关键。

解决不同时间戳大规模SVG格式GIS数据的快速比对涉及的相关技术及需要解决的问题包括：

1)SVG格式语法的理解及定义的扩充，如，各种地理元素的定义、嵌套的关系等。

2)大规模(5M以上)SVG格式GIS数据对应的倒状结构树的生成及优化。

3)记录不同时间戳SVG格式的GIS数据比对结果的差异脚本文件的生成规则及函数的定义。

4)高效比对算法的实现。

三、附图说明

图1为SVG格式的GIS架构，是基于时态的大规模SVG格式GIS数据的通用框架。

四、发明内容

1.大规模SVG格式的时态GIS数据规则定义及倒状解析结构树的优化方法

由于不同时间戳的大规模SVG格式GIS数据是一种复杂的嵌套结构，且在SVG中各种地理元素的表示复杂多样，首先必须在SVG格式GIS数据的基础上进行规则定义【20】，主要包括：

1)定义节点集元素(即在某时间戳的SVG格式GIS数据对应的倒状解析结构树中，从根节点开始将某特定分支中的元素节点、属性节点和文本节点看成一个整体，减少了比对数组中的元素个数)；

2)定义倒状解析结构树的标识规则(在SVG格式GIS数据中主要包括基本图形元素集，常见框架元素集，和常用属性元素集。总共有26个主要基本元素，可以使用大写字母A-Z与其一一对应。通过定义标识规则，缩短了元素中属性字符串的长度。)

基于以上规则的定义，再对倒状解析结构树进行优化。优化后的结构树的节点数比原结构树减少了55％，比DiffX【16】算法的结构树节点数减少了34％，比DiffS【18，19】算法的优化后的结构树节点数减少了23％。解决了DiffX算法和DiffS算法中的节点数过多、每个元素的属性字符串过长所导致的排序和查找的时间过长问题。

2.数据结构模型的选取及基于优化倒状解析结构树的快速比对方法

核心算法模型【20】由生成比对节点集元素集合的子算法模型和生成差异脚本的子算法模型组成。

生成比对节点集元素集合的子算法模型将两个不同时间戳的SVG格式倒装解析结构树转换成以节点集元素为单元的两个比对数组，并将其中一个数组进行排序，通过遍历另一个数组中的元素，对已排序的数组进行折半查找，生成匹配节点集元素集合。

在生成的匹配节点集元素集合的基础上，首先遍历第一个时间戳的SVG格式GIS数据对应的优化倒状解析结构树，如果有不在匹配节点集元素集合中的节点，则在比对结果的差异脚本文件(XML格式)中添加delete操作；接着遍历第二个时间戳的SVG格式GIS数据对应的优化倒状解析结构树，如果有不在匹配节点集元素集合中的节点，则在比对结果的差异脚本文件中添加insert操作；最终生成由delete和insert两种函数组成的差异脚本文件。该差异脚本文件可以通过与第一个时间戳的SVG格式GIS数据文件相结合，得到第二个时间戳的SVG格式GIS数据文 件。

3.高效算法的实现及验证策略

本发明的核心算法模型对应的算法实现过程主要是以算法模型理论为依据。本算法的时间复杂度为O(n)【20】，低于现有的最优匹配算法DiffS的时间复杂度O(nlogn)，故适合对大规模SVG格式GIS数据进行差异匹配。

本发明专利的验证采用增量模式策略，增量的同时SVG格式GIS数据的数据量也按照一定的数量级进行递增。表1对DIFFX、DIFFS和本发明专利的核心算法I-DIFFS按照5M、10M、15M和20M的数量级进行验证的结果。结果证明本发明专利技术的高效性。

表1三种算法针对不同大小SVG格式GIS数据的比对时间统计(单位：秒)

文件大小 DIFFX DIFFS I-DIFFS 5M 1.658 1.424 1.028 10M 7.108 5.021 2.975 15M 14.522 9.231 5.122 20M 25.898 15.539 8.169

参考文献

【1】吴信才等，空间数据库，科学出版社，2009.

【2】边馥苓.空间信息导论，测绘出版社，2007.

【3】崔铁军.地理空间数据库原理，科学出版社，2007.

【4】Zarine Kemp，Arek Kowalczyk.Incorporating the temporal dimension in GIS，p：89-104，2005.

【5】Li Y，Dong XM，Chi GB.Towards Spatial Information Service with Applied Extension to SVG，2009INTERNATIONAL CONFERENCE ON NEW TRENDS IN INFORMATION AND SERVICE SCIENCE(NISS2009)，VOLS：1AND2，p：474-480，2009.

【6】Kramis，Marc，Gabathuler，Cedric；Fabrikant，Sara Irina；Waldvogel，Marcel.An XML-based infrastrueture to enhance collaborative geographic visual analytics，Cartography and Geographic Information Science，vol：36，p：281-293，July2009.

【7】Li D，Deng LS.Multi-Resolution Mechanism for SVG，2009ASIA-PACIFIC CONFERENCE ON INFORMATION PROCESSING(APCIP2009)，vol：2，p：139-143，2009.

【8】马林.文件系统原理精解与数据恢复最佳实践，清华大学出版社，2009.

【9】Liang JZ.Using SVG Technique to Organize and Display Data of Embedded GIS，20095TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS，NETWORKING AND MOBILE COMPUTING，VOLS：1-8，p：5375-5377，2009.

【10】Huang HS，Li Y.Load Balancing Spatial Analysis in XML/GML/SVG based WebGIS，2009INTERNATIONAL CONFERENCE ON ENVIRONMENTAL SCIENCE AND INFORMATION APPLICATION TECHNOLOGY，VOL：II，p：538-541，2009.

【11】Moreno ED，de Oliveira J.IF.Architectural impact ofthe SVG-based graphical components in web applications，COMPUTER STANDARDS&INTERFACES vol：31，p：1150-1157，NOV2009.

【12】Wang WY，Qiang X.A study on TGIS based on WebGIS in Yulin city，ICEMI2007： PROCEEDINGS OF20078TH INTERNATIONAL CONFERENCE ON ELECTRONIC MEASUREMENT & INSTRUMENTS，VOL：IV，p：683-686，2007.

【13】Yuan，Man.A practical and light integrated webgis based on SVG，2009WRI Intemational Conference on Communications and Mobile Computing，CMC2009，vol：3，p：142-146，2009.

【14】Li，Yangdong，Tong，Xiaohua；Liu，Miaolong；Han，Zhen.A version-based modeling approach for spatio-temporal data，2008International Workshop on Education Technology and Training and2008International Workshop on Geoscience and Remote Sensing，ETT and GRS2008，vol：2，p：89-94，2009.

【15】Kaiyuan，Jiang Zhiyuan，Fang Yuanting，Ge Yu，Zhou.Information retrieval through SVG-based vector images using an original method，IEEE Intemational Conference one-Business Engineering2007，p：298-332，2007.

【16】Raihan Al-Ekram，Archana Adma，Olga Baysal.diffX：An Algorithm to Detect Changes in Multi-Version XML Documents.Proceeding CASCON′05Proceedings of the2005conference of the Centre for Advanced Studies on Collaborative research，p：279-284，2005.

【17】Bai，Shuju，Salam，Abdus；Khosravi，Ebrahim.Metadata extraction from SVG images using A-tree，Proceedings of the2005International Conference on Data Mining，DMIN′05，p：159-165，2005.

【18】Du Qingfeng；Guo ZhiChao；Tang X；″DiffSvg-Matching Algorithm of Different Timestamp Maps Based on SVG″.IEEE International Conference on Computer Science and Service System，2012.】

【19】杜庆峰，郭智超，唐学波.DiffS：不同版本SVG格式地图差异匹配算法，武汉大学学报(信息科学版)，2012(8).

【20】杜庆峰，赵亚男.I-DiffS：不同时间戳SVG格式地图差异匹配改进算法.同济大学学报(自然科学版)，2013。