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

Graph matching algorithm based on edge map's connection

作　　者：曹春萍[1] 何佳[1] 

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093

出　　处：《计算机应用研究》2013年第9期2697-2699,2703,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61074087);上海市教育委员会科研创新基金资助项目(12ZZ144)

摘　　要：针对面向语义网络图匹配的特殊性,在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法,利用语义网络图的有向性,将图匹配问题转换为对搜索路径的规划,并采用深度优先算法形成搜索步,同时对目标图的所有边建立索引,加快以边匹配为中心形成边映射表的过程,最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明,该算法具有较高的执行效率。Aiming at the semantic network graph matching problem＇ s particularity, this paper proposed a new matching algo- rithm 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.

关 键 词：语义网络 图匹配 边映射表 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]