基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。

Graph matching algorithm based on edge map's connection

Aiming at the semantic network graph matching problem's particularity, this paper proposed a new matching algorithm based on the state backtracking search method , which called EBGM. This method took use of the semantic network's directional, converting the graph matching problem into a path search planning and used the depth-first algorithm to form a search step set. And at the same time this paper created index for the all edges of the target graph to accelerate the process of forming edge mapping table, finally made connect of the edge mapping table to get the result set. Experiment results on the real dataset show that the algorithm has higher efficiency.