基于划分的模式匹配改进算法

• 作者: 平玲娣 潘雪增 陈健 黄勇
• 来源期刊: 大连海事大学学报
• 学科: 工学
• 关键词: 模式匹配 快速搜索算法 划分窗口 时间复杂度
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 自动化
• 页码范围: 41-44
• 页数: 4页
• 分类号: TP301.6
• 字数: 3317字
• 语种: 中文

摘要

为提高基于划分窗口的字符串匹配算法(SKIP和KMPSKIP算法)的性能,结合QS算法的优点,通过提前预览下一窗口最后一个字符的移动信息跳过尽可能多的字符进行下一轮匹配,减少了匹配次数,提高了匹配效率.理论分析及实验结果均表明,改进算法在平均时间复杂度方面优于原始算法,在模式较短的情况下,ISKIP算法的平均运行时间仅为BMH算法的65%～85%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈健	浙江大学计算机科学与技术学院	61	435	11.0	19.0
2	平玲娣	浙江大学计算机科学与技术学院	72	1386	15.0	36.0
3	潘雪增	浙江大学计算机科学与技术学院	89	1318	17.0	34.0
4	黄勇	浙江大学计算机科学与技术学院	34	169	8.0	12.0