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

Improved Matching Algorithm to Different Time Stamp Maps

摘要:

在分析了现有的可伸缩矢量图形（SVG)格式地图差异算法的研究现状和不足的基础上提出了一种改进的SVG格式地图差异匹配算法IDiffS(improved difference of SVG maps).该改进算法定义了节点集元素，即节点集元素可能包含1个或多个元素节点、属性节点和值节点构成的一个路径节点集合，定义了SVG格式解析结构树的标号规则，减少了结构树对应数组的元素个数，也减少了差异脚本中操作类型的数目，缩短了匹配过程.匹配结果为差异脚本，该脚本记录了前一个时间戳到后一个时间戳的更新操作.IDiffS算法相比于现有的最新DiffS算法，时间复杂度更低.应用验证证明了该算法有效.

Abstract:

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(IDiffS). 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 the existing latest DiffS algorithm, this algorithm has lower time complexity. Application validates that DiffS algorithm is effective.