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

摘要：

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

关键词：近似模式匹配、动态规划算法、匹配时间

所属期刊栏目：40

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61070015;广东省科技计划项目2011B010200039;广州市科技计划项目11C42080722

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：103-108