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.
胡学钢，王海平，郭丹，李培培. 图算法求解带有限长空位和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.
2016, Vol. 29 
