改进的近似模式匹配算法

摘要

In order to improve the efficiency of approximate pattern 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 patternmatching algorithms in the case of matching for several times.So IMP-DP is proven to be effective.%为了提高近似模式匹配算法在多次匹配情况下的效率,借鉴了文本快速过滤算法的思想,分析了平均情况下改进的动态规划算法(DP算法),并在此基础上设计实现了一种改进的DP算法,称为IMP-DP.该算法在匹配过程中,将上一次运算的结果存储起来,与上次相同的匹配可在原有成功匹配结果的基础上进行运算,忽略将不可能产生成功匹配的区域,只关注剩余的区域.由算法时间复杂性和实验对比分析结果表明,该算法在多次匹配情况下,效率远远高于其它算法,从而验证了该算法改进的有效性.