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

Improved pattern matching algorithm based on partition

作　　者：黄勇[1] 平玲娣[1] 潘雪增[1] 陈健[1] 

机构地区：[1]浙江大学计算机科学与技术学院,杭州310027

出　　处：《大连海事大学学报》2008年第1期41-44,共4页Journal of Dalian Maritime University

基　　金：国家"八六三"高技术研究发展计划资助项目(2006AA01Z431);浙江省科技重点资助项目(2006C21028);澳门科技基金资助项目(005/2006/A);浙江省重大科技专项重点项目(2006C11105)

摘　　要：为提高基于划分窗口的字符串匹配算法（SKIP和KMPSKIP算法）的性能，结合QS算法的优点，通过提前预览下一窗口最后一个字符的移动信息跳过尽可能多的字符进行下一轮匹配，减少了匹配次数，提高了匹配效率．理论分析及实验结果均表明，改进算法在平均时间复杂度方面优于原始算法，在模式较短的情况下，ISKIP算法的平均运行时间仅为BMH算法的65％～85％．ISKIP and IKMPSKIP algorithms were developed combining quick search（QS） algorithm to improve performance of SKIP and KMPSKIP algorithms using partition window. The shift information of the last character of next window was looked ahead to increase the shift distance, and the times of matching were reduced efficiently. Theoretical analysis shows that two improved algorithms are superior to the original ones in respect of average time complexities. Experimental results also demonstrate its effectiveness. Especially in case of small patterns, ISKIP algorithm takes only 65 % -85 % of time of BMH algorithm.

关 键 词：模式匹配 快速搜索算法 划分窗口 时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]