| 基于划分的模式匹配改进算法 |
| |
| 引用本文： | 黄勇,平玲娣,潘雪增,陈健. 基于划分的模式匹配改进算法[J]. 大连海事大学学报(自然科学版), 2008, 34(1): 41-44 |
| |
| 作者姓名： | 黄勇 平玲娣 潘雪增 陈健 |
| |
| 作者单位： | 浙江大学,计算机科学与技术学院,杭州,310027;浙江大学,计算机科学与技术学院,杭州,310027;浙江大学,计算机科学与技术学院,杭州,310027;浙江大学,计算机科学与技术学院,杭州,310027 |
| |
| 基金项目： | 国家“八六三”高技术研究发展计划资助项目(2006AA01Z431)，浙江省科技重点资助项目(2006C21028)，澳门科技基金资助项目(005/2006/A)，浙江省重大科技专项重点项目(2006C11105) |
| |
| 摘 要： | 为提高基于划分窗口的字符串匹配算法(SKIP和KMPSKIP算法)的性能,结合QS算法的优点,通过提前预览下一窗口最后一个字符的移动信息跳过尽可能多的字符进行下一轮匹配,减少了匹配次数,提高了匹配效率.理论分析及实验结果均表明,改进算法在平均时间复杂度方面优于原始算法,在模式较短的情况下,ISKIP算法的平均运行时间仅为BMH算法的65%~85%.
|
| 关 键 词： | 模式匹配 快速搜索算法 划分窗口 时间复杂度 |
| 文章编号： | 1006-7736（2008）01-0041-04 |
| 收稿时间： | 2007-10-18 |
| 修稿时间： | 2007-10-18 |
Improved pattern matching algorithm based on partition |
| |
| HUANG Yong,PING Ling-di,PAN Xue-zeng,CHEN Jian. Improved pattern matching algorithm based on partition[J]. Journal of Dalian Maritime University, 2008, 34(1): 41-44 |
| |
| Authors: | HUANG Yong PING Ling-di PAN Xue-zeng CHEN Jian |
| |
| Abstract: | |
| |
| Keywords: | pattern matching quick search algorithm partition window time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
