Abstract:

This paper studies APMWL (approximate pattern matching with wildcards and length constraint) problem. In order to avoid the exponential growth of matching patterns, the paper introduces the one_off condition, and proposes a heuristic algorithm BAPM (backward approximate pattern matching) which constructing the edit distance matrix backwardly. Based on one_off condition, flexible wildcards and length constraint, BAPM can simultaneously process three edit operations, namely insertion, replacement and deletion. The experimental results show that BAPM has a significant advantage on matching solutions compared with Sail-Approx, and the average improvement rate of matching is up to 18.99%.

Key words: approximate pattern matching, wildcards, length constraints, edit distance matrix, one_off condition

摘要：

研究了带有灵活通配符和长度约束的近似模式匹配问题（approximate pattern matching with wildcards and length constraint，APMWL）；为避免文本字符重复使用造成解的指数级增长，引入了一次性使用原则one_off条件，提出了一种后向构造编辑距离矩阵的BAPM（backward approximate pattern matching）算法。该算法在one_off条件、灵活通配符和长度约束条件的基础上，可同时处理插入、替换和删除三种编辑操作。与同类算法Sail_Approx进行实验对比，结果表明BAPM算法获取解的平均增长率可达18.99%，具备良好的解优势。

关键词: 近似匹配, 通配符, 长度约束, 编辑距离矩阵, one_off条件