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

Models for Pattern Matching with Wildcards and Length Constraints

讨论了带有通配符和长度约束的模式匹配(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.