一种基于标签图的模式匹配子图查找方法

摘要

本发明公开一种基于标签图的模式匹配子图查找方法，该方法将模式匹配子图查找问题定义成标签图模型，从全局角度求解标签图中的模式匹配子图，通过剪枝优化和深度优先搜索算法等策略获取可行解空间。所述标签图中模式匹配子图的查找问题描述如下：设给定一个包含一组标签的标签图，再给定包含一组标签的查询图，基于标签图的模式匹配子图查找方法找到和查询图模式匹配的子图。假定标签图为G＝(V,E,l)，查询图为Q＝(V_q,E_q,l_q)，标签图G＝(V,E,l)中每个顶点看作待查询的对象，图中每个顶点都具有一个标签；标签图和查询图均为有向图。我们的目标是从标签图G＝(V,E,l)中寻找到所有和查询图Q＝(V_q,E_q,l_q)满足模式匹配条件的子图。

主权项

一种基于标签图中的模式匹配子图查找方法，其特征在于该方法包括以下步骤：步骤1)根据用户输入的信息，构建网络图中的模式匹配子图查找问题的标签图G＝(V,E,l)，所述V是顶点集合，E是边集合，l是顶点到标签的映射；所述映射，是指两个元素集合之间元素相互对应的关系；所述标签图G＝(V,E,l)在建立后，每个顶点均对应一个标签；步骤2)采用剪枝优化和深度优先搜索算法，获得模式匹配子图查找问题在标签图模型G＝(V,E,l)上的解空间，具体步骤如下：步骤21)定义目标解空间S_olution，表示与查询图Q＝(V_q,E_q,l_q)模式匹配的所有子图构成的集合，初始化步骤22)定义目标可行匹配集合m_atches，初始化步骤23)定义临时匹配集合Φ₀，求解查询图Q＝(V_q,E_q,l_q)中，每个顶点u_q对应的可行匹配集合Φ(u_q)，其中u_q∈V_q，Φ₀表示由每个可行匹配集合Φ(u_q)构成的集合；|V_q|表示查询图中的顶点个数，则顶点u₀对应的可行匹配集合为Φ(u₀)，将Φ(u₀)加入到Φ₀中，同理将顶点u₁对应的可行匹配集合Φ(u₁)加入到Φ₀中，继续操作，直至将顶点对应的可行匹配集合加入到Φ₀中，从而得到最终的可行匹配集合构成的集合Φ₀；24)执行剪枝算法DualSim(G,Q,Φ₀)，对临时匹配集合中的元素进行筛选，更新Φ₀＝DualSim(G,Q,Φ₀)，所述DualSim()即为剪枝优化算法，用来缩小查询过程中的搜索空间，通过以下两个限制条件对临时匹配集合Φ₀中的元素进行剪枝：对于使得(v,v′)∈E；对于使得(v,v′)∈E；步骤25)执行深度优先搜索算法S_earch(G,Q,Φ₀,d_epth)，引入变量d_epth表示遍历的深度并初始化d_epth＝0，求解目标解空间S_olution；步骤26)确定最终目标解空间S_olution，该解空间中包含与查询图Q＝(V_q,E_q,l_q)模式匹配的所有子图。