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

Graph-Based Algorithm for Pattern Matching with Bounded Length Gaps and One-off Constraint

作　　者：胡学钢[1] 王海平[1] 郭丹[1] 李培培[1] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009

出　　处：《模式识别与人工智能》2016年第5期400-409,共10页Pattern Recognition and Artificial Intelligence

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]