带有通配符和长度约束的模式匹配问题求解模型  

Models for Pattern Matching with Wildcards and Length Constraints

作　　者：汪浩[1] 王海平[1] 吴信东[1] 

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

出　　处：《计算机科学》2016年第4期279-283,F0003,共6页Computer Science

基　　金：国家自然科学基金项目(31100956;61173117)资助

摘　　要：讨论了带有通配符和长度约束的模式匹配(PMWL)问题,其中模式由子模式序列集组成,两个相邻子模式的间隔在一定长度范围内。针对PMWL问题,已有工作包括设计启发式求解算法和对特殊情况进行完备性分析,然而还需要构建问题的基础求解模型。借鉴约束可满足问题框架,构建了由变量、值域和约束组成的三元组求解模型,对PMWL问题的基本概念和基本性质给出了形式化描述。最后,给出了算法求解PMWL问题的特定条件下的完备解。For the problem of pattern matching with wildcards and length constraints （PMWL）, the patterns are com- posed of a sequence of sub-patterns,where any two adjacent sub-patterns with flexible gaps are in a specified range of the text. Existing work includes a heuristic strategy and its completeness analysis with constraints, but the PMWL problem still needs systematic studies. We drew on the experience of constraint satisfaction problems（CSPs） and set up a 3-tuple model consisting of variables, domains and constraints. We then derived formal descriptions for the basic con- cepts and properties. Also, a tree-based matching algorithm was presented to solve the PMWL problem under certain conditions.

关 键 词：长度约束 通配符 求解模型 模式匹配 

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