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

作者：黄国林; 郭丹; 胡学钢

来源：计算机科学与探索, 2013, (01): 83-91.

• 近似匹配
• 通配符
• 长度约束
• 编辑距离矩阵
• one_off条件 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.9...

• 单位
  合肥工业大学