改进的Sunday模式匹配算法的设计与实现  

Design and Realization of the Improved Sunday Pattern Matching Algorithm

作　　者：巫喜红[1] 凌捷[1,2] 

机构地区：[1]嘉应学院计算机学院,广东梅州514015 [2]广东工业大学计算机学院,广东广州510006

出　　处：《哈尔滨理工大学学报》2013年第6期52-57,共6页Journal of Harbin University of Science and Technology

基　　金：国家十二五科技支撑计划项目(2012BAH27F05);广东省自然科学基金(S2012020011071);广东省战略性新兴产业核心技术攻关项目(2012A010701004)

摘　　要：针对Sunday模式匹配算法低效率问题,研究了它的改进算法I-Sunday算法.依据模式匹配算法的跳跃思想,I-Sunday算法在遇到坏字符时,不但考虑当前匹配窗口的下一位字符,而且也考虑了下一位字符之后长度为模式串长度的那个字符,这就跳跃了更大的距离.另外,匹配时采用双向并行方式进行匹配.为了验证I-Sunday算法的性能,在同等条件下,在匹配次数和比较的字符个数两方面对I-Sunday算法进行实验.实验结果表明,由于I-Sunday算法能够跳过大量的坏字符,大大地减少匹配次数和字符的比较,从而缩短匹配时间,有效地提高模式匹配速度.In order to improve the efficiency of Sunday pattern matching algorithm, this paper studies an im- proved Sunday （ I _ Sunday） algorithm. According to the thought of jumping, when encountering bad characters, the I Sunday algorithm not only considers the next character of the current matching window, but the character whose length equals the pattern strings＇ after the next character of the current matching window. All these decide that I _ Sunday algorithm can jump a greater distance. In addition, when matching the I _ Sunday algorithm, we use the mode of bidirectional parallel matching. In order to verify the performance of the I _ Sunday algorithm, in the same condition, some experiments are clone from two aspects which are matching times and compared characters＇ numbers. The experimental results show that the I_ Sunday algorithm is more efficient than the Stmday algorithm because it can jump over a large number of bad character and greatly reduce the match number times and the char- acter comparison so as to shorten the matching time. The I _ Sunday algorithm effectively improves the speed of pat- tern matching.

关 键 词：Sunday算法 Sunday算法改进 双向并行 模式匹配 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]