不同时间戳的地图差异匹配改进算法  

Improved Matching Algorithm to Different Time Stamp Maps

作　　者：杜庆峰[1] 赵亚男[1] 

机构地区：[1]同济大学软件学院,上海201804

出　　处：《同济大学学报（自然科学版）》2013年第10期1589-1595,1603,共8页Journal of Tongji University:Natural Science

基　　金：国家自然科学基金(41171303)

摘　　要：在分析了现有的可伸缩矢量图形(SVG)格式地图差异算法的研究现状和不足的基础上提出了一种改进的SVG格式地图差异匹配算法I-DiffS(improved difference of SVG maps).该改进算法定义了节点集元素,即节点集元素可能包含1个或多个元素节点、属性节点和值节点构成的一个路径节点集合,定义了SVG格式解析结构树的标号规则,减少了结构树对应数组的元素个数,也减少了差异脚本中操作类型的数目,缩短了匹配过程.匹配结果为差异脚本,该脚本记录了前一个时间戳到后一个时间戳的更新操作.I-DiffS算法相比于现有的最新DiffS算法,时间复杂度更低.应用验证证明了该算法有效.Based on an analysis of the existing research about differences matching algorithms based SVG maps and their insufficiencies, this paper proposes an improved differences matching algorithm improved different of SVG maps（I-DiffS）. The algorithm defines a node set element, which is a set of path node composed by one or several element node, attribute node and value node. It also defines a labeling rule of structured trees based scalable vector graphics （SVG）. Both reduce the number of elements in the arrays related to structured trees and the sum of types of operations in an generated difference script are reduced, which shortens the process of matching. The result of matching is a generated difference script, which records an update operation from the first time stamp map to the second one. Compared with theexisting latest Dills algorithm, this algorithm has lower time complexity. Application validates that DiffS algorithm is effective.

关 键 词：可伸缩矢量图形(SVG) 时间戳 地图 差异匹配算法 标号规则 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]