针对QSP算法的研究与分析

• 作者: 李莉 林劼 江育娥
• 来源期刊: 计算机系统应用
• 关键词: 模式匹配 QS算法 QSP算法 跳转期望值差
• 年，卷（期）: 2016,（3）
• 页码范围: 28-33
• 页数: 6页
• 字数: 5364字
• 语种: 中文

摘要

BM算法是经典的单模式匹配算法,QS算法是基于BM算法的改进算法,由于QS算法仅仅分析下一字符T[j+m]计算右移量,整体的匹配效率并不高,因此在QS算法的基础上提出一种改进算法(QSP).QSP算法在预处理阶段从左向右找出模式串中出现1次以上的单字符,计算出这些字符的跳转期望值差,得到最大差值和相对应的字符位置maxPos,并修改skipp2数组的值;在匹配阶段,首先比较P[maxPos]与T[j+maxPos]是否相等,然后再利用两个数组skipp1和skipp2进行右移,保证每次右移的距离达到最大.通过实验证明,该算法总的比较次数和运行时间都低于QS算法,匹配效率得到明显的提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李莉	福建师范大学软件学院	47	104	5.0	7.0
2	林劼	福建师范大学软件学院	25	138	6.0	11.0
3	江育娥	福建师范大学软件学院	11	65	4.0	8.0