改进的近似模式匹配算法

• 作者: 宋鸿陟 张丽霞
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 模式匹配 近似模式匹配 动态规划 文本快速过滤 IMP-DP
• 年，卷（期）: 2011,（5）
• 所属期刊栏目: 开发与应用
• 页码范围: 1820-1823
• 分类号: TP301
• 字数: 4916字
• 语种: 中文

摘要

为了提高近似模式匹配算法在多次匹配情况下的效率,借鉴了文本快速过滤算法的思想,分析了平均情况下改进的动态规划算法(DP算法),并在此基础上设计实现了一种改进的DP算法,称为IMP-DP.该算法在匹配过程中,将上一次运算的结果存储起来,与上次相同的匹配可在原有成功匹配结果的基础上进行运算,忽略将不可能产生成功匹配的区域,只关注剩余的区域.由算法时间复杂性和实验对比分析结果表明,该算法在多次匹配情况下,效率远远高于其它算法,从而验证了该算法改进的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张丽霞	华南农业大学信息学院人机交互研究中心	14	71	5.0	7.0
2	宋鸿陟	华南农业大学信息学院人机交互研究中心	32	159	6.0	10.0