改进的近似模式匹配算法  

Improved approximate pattern matching algorithm

作　　者：张丽霞[1] 宋鸿陟[1] 

机构地区：[1]华南农业大学信息学院人机交互研究中心,广东广州510642

出　　处：《计算机工程与设计》2011年第5期1820-1823,共4页Computer Engineering and Design

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

摘　　要：为了提高近似模式匹配算法在多次匹配情况下的效率,借鉴了文本快速过滤算法的思想,分析了平均情况下改进的动态规划算法(DP算法),并在此基础上设计实现了一种改进的DP算法,称为IMP-DP。该算法在匹配过程中,将上一次运算的结果存储起来,与上次相同的匹配可在原有成功匹配结果的基础上进行运算,忽略将不可能产生成功匹配的区域,只关注剩余的区域。由算法时间复杂性和实验对比分析结果表明,该算法在多次匹配情况下,效率远远高于其它算法,从而验证了该算法改进的有效性。In order to improve the efficiency of approximate pattem matching algorithm in the case of matching for several times, the dynamic programming and the text quick filter algorithm are introduced in detailed. DP algorithm is analyzed then, on this basis, an improved algorithm named IMP-DP is designed and implemented drawing on the idea of text quick filter. In the process of matching, the results of the previous operation will be stored, so the same matching can be calculated on the basis of the previous successful matching. The algorithm will ignore the region which could not process the successful matching, and only concern with the remaining region. Through time complexity analysis and experimental comparison, it is found that IMP-DP algorithm is far more efficient than other pattern matching algorithms in the case of matching for several times. So IMP-DP is proven to be effective.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]