一种快速近似模式匹配算法

为进一步提升传统的近似模式匹配问题解决方法——动态规划算法的性能,提出了一种新的过滤型近似模式匹配算法.该算法结合动态规划算法,切分模式串得到长度相等且更小的模式片;在此基础上将待匹配的文本串分割成子串,并建立相应的索引;同时设计了一个新的过滤策略来消除匹配检查中的冗余.通过实例将文中方法与现有方法进行对比,结果表明:文中方法的匹配时间较短,匹配性能优于现有方法;随着模式串长度的增加,文中算法的优越性更为明显,模式串长度大于45后,文中算法的匹配时间可比传统动态规划算法缩短一半以上.

A Fast Algorithm for Approximate Pattern Matching

In order to improve the performance of the dynamic programming algorithm,a traditional method of solving the approximate pattern matching problem,a novel filtering-type approximate pattern matching algorithm is proposed,which combines the advantages of the dynamic programming algorithm,splits the pattern string into sma-ller pattern pieces with the same length,divides the text string to be matched into sub-strings and further establishes the corresponding index.Moreover,a new filtering strategy is proposed to eliminate the redundancy of the match examination.Example results show that the proposed algorithm is superior to the existing ones due to its small match time cost and high performance,especially under the condition of long pattern string matching;and that,as compared with the traditional dynamic programming algorithm,the proposed algorithm reduces the match time by more than 50% when the pattern string length is more than 45.