|
|
|
| Graph-Based Algorithm for Pattern Matching with Bounded Length Gaps and One-off Constraint |
| HU Xuegang, WANG Haiping, GUO Dan, LI Peipei |
| School of Computer Science and Information, Hefei University of Technology, Hefei 230009 |
|
|
|
|
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.
|
|
Received: 03 April 2015
|
| About author:: 胡学钢,男,1961年生,博士，教授,主要研究方向为数据挖掘、知识工程.Email:jsjxhuxg@hfut.edu.cn.
王海平,男,1986年生,博士研究生,主要研究方向为模式识别、数据挖掘.Email:hpwang.hfut@gmail.com. 郭丹,女,1983年生,博士,副教授,主要研究方向为模式识别、智能地理信息系统.Email:guodan@hfut.edu.cn.李培培(通讯作者),女,1982年生,博士,讲师，主要研究方向为概念漂移检测、数据流分类.Email:peipeili@hfut.edu.cn. |
|
|
|
|
|
|
2016, Vol. 29 
