改进的近似模式匹配算法

作     者：张丽霞 宋鸿陟 ZHANG Li-xia;SONG Hong-zhi

作者机构：华南农业大学信息学院人机交互研究中心广东广州510642 

基　　金：国家自然科学基金项目(60875045) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2011年第32卷第5期

页      码：1820-1823页

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

主 题 词：模式匹配 近似模式匹配 动态规划 文本快速过滤 IMP—DP 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2011.05.061

馆 藏 号：203210747...