图算法求解带有限长空位和one-off约束的模式匹配问题<sup>*</sup>

doi:10.16451/j.cnki.issn1003-6059.201605003

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (514 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要讨论带有限长空位和one-off约束条件的模式匹配问题，其中限长空位改变单个匹配解结构，one-off条件约束匹配解之间的关系，从而形成规模较大且稀疏的解空间。借鉴约束可满足性问题框架，将PMGO问题转化为图结构下的路径搜索问题，并证明转化的等价性。然后提出图结构下的剪枝和匹配算法(GPM)，根据one-off约束得到节点之间的约束关系，再迭代交互地进行剪枝与搜索。实验中使用匹配解丢失率度量已有启发式算法和GPM的完备性，证明GPM可与已有启发式算法形成互补，有效降低匹配解丢失率。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章

Abstract：The problem of pattern matching with bounded length gaps and one-off constraint (PMGO) is discussed. The structure of individual occurrences is changed by the bounded gaps, and the relation between occurrences is restricted by the one-off constraint. Thus, a large-scale sparse space of all candidate occurrences is generated. Based on the framework of the constraint satisfaction, the PMGO problem is transformed into path search in a directed acyclic graph (DAG) structure. Meanwhile, the equivalence of transformation is proved. Then, a graph-based pruning and matching (GPM) algorithm is presented. In GPM algorithm, a constraint relationship between vertexes is built under the one-off constraint, and then the path search is combined with a pruning procedure in an alternating and iterative manner. The loss rate of occurrences is used to measure existing heuristic algorithms and the completeness of the proposed GPM algorithm. The experimental results demonstrate that the GPM algorithm provides a complementary method for heuristic algorithms and it efficiently reduces the loss rate of occurrences.

收稿日期: 2015-04-03

基金资助:国家自然科学基金项目(No.61305062,61273292)、教育部博士点博导基金项目(No.20130111110011)、安徽省自然科学基金项目(No.1308085QF102)、中国博士后科学基金项目(No.2012M511403)资助

作者简介: 胡学钢，男，1961年生，博士，教授，主要研究方向为数据挖掘、知识工程.Email:jsjxhuxg@hfut.edu.cn.王海平，男，1986年生，博士研究生，主要研究方向为模式识别、数据挖掘.Email:hpwang.hfut@gmail.com.郭丹，女，1983年生，博士，副教授，主要研究方向为模式识别、智能地理信息系统.Email:guodan@hfut.edu.cn.李培培(通讯作者)，女，1982年生，博士，讲师，主要研究方向为概念漂移检测、数据流分类.Email:peipeili@hfut.edu.cn.

引用本文:

胡学钢，王海平，郭丹，李培培. 图算法求解带有限长空位和one-off约束的模式匹配问题^*[J]. 模式识别与人工智能, 2016, 29(5): 400-409. HU Xuegang, WANG Haiping, GUO Dan, LI Peipei. Graph-Based Algorithm for Pattern Matching with Bounded Length Gaps and One-off Constraint. , 2016, 29(5): 400-409.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201605003 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2016/V29/I5/400