一种改进的Sunday模式匹配算法

摘要：

字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能.在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进.改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置.每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数.在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配.实验结果表明改进算法的效率比Sunday算法有一定提高.

关键词：字符串、模式匹配、倒序字符匹配、Sunday算法

所属期刊栏目：26

分类号：TP301.6(计算技术、计算机技术)

资助基金：中国地质调查局地质调查工作项目1212011085536

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

页数：共4页

页码：78-81