| 求解近似模式匹配的启发式算法 |
| |
| 引用本文： | 黄国林,郭丹,胡学钢.求解近似模式匹配的启发式算法[J].计算机科学与探索,2013(1):83-91. |
| |
| 作者姓名： | 黄国林 郭丹 胡学钢 |
| |
| 作者单位： | 合肥工业大学计算机与信息学院 |
| |
| 基金项目： | 国家高技术研究发展计划(863) No.2012AA011005;中国博士后科学基金 No.2012M511403;中央高校基本科研业务费专项资金 No.2010HGXJ0714~~ |
| |
| 摘 要： | 研究了带有灵活通配符和长度约束的近似模式匹配问题(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条件 |
Heuristic Algorithm for Approximate Pattern Matching Problem |
| |
| HUANG Guolin, GUO Dan , HU Xuegang.Heuristic Algorithm for Approximate Pattern Matching Problem[J].Journal of Frontier of Computer Science and Technology,2013(1):83-91. |
| |
| Authors: | HUANG Guolin GUO Dan HU Xuegang |
| |
| Affiliation: | School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China |
| |
| 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%. |
| |
| Keywords: | approximate pattern matching wildcards length constraints edit distance matrix one_off condition |
| 本文献已被 CNKI 等数据库收录！ |
