一种求解近似模式匹配的启发式算法

摘要：

针对带有灵活通配符和长度约束的近似模式匹配问题(APMWL,Approximate Pattern Matching with Wildcards and Length constraint)进行研究,为避免文本字符重复使用造成解的指数级增长,引入一次性使用原则one_off条件,提出一种基于后向构造编辑距离矩阵的BAPM(Backward Approximate Pattern Matching)算法.该算法在one_off条件、灵活通配符以及长度约束条件的基础上,可同时处理插入、替换和删除3种编辑操作.与同类算法Sail_Approx进行了实验对比,结果表明BAPM算法获取解的平均增长率可达18.99％,具备良好的解优势.

关键词： Approximate pattern matching Wildcards Length constraints Edit distance matrix One_off condition

作者: 黄国林 郭丹 胡学钢 吴信东

作者单位: 合肥工业大学计算机与信息学院 合肥230009 合肥工业大学计算机与信息学院 合肥230009;美国佛蒙特大学计算机科学系 佛蒙特州 柏林顿05405

会议类型: 国内会议

会议名称: 第十二届中国Rough集与软计算学术会议、第六届中国Web智能学术研讨会及第六届中国粒计算学术研讨会联合学术会议

会议地点: 合肥

会议语种:中文

页码: 123-123

在线出版日期: 2012-10-13（万方平台首次上网日期，不代表论文的发表时间）