一种改进的Sunday字符串匹配算法  

An Imporved Sunday String Matching Algorithm

作　　者：刘雨心[1] 孟亮[1] 窦银科[2] 

机构地区：[1]太原理工大学计算机科学与技术学院,太原030024 [2]太原理工大学电气与动力工程学院,太原030024

出　　处：《太原理工大学学报》2013年第5期604-607,共4页Journal of Taiyuan University of Technology

基　　金：国家自然科学基金资助项目(41176080);山西省自然科学基金资助项目(2010011023-2)

摘　　要：针对Sunday匹配算法在首字符和正文存在大量重复,使得其平均执行效率降低这一问题,提出了一种改进的Sunday算法。首先将重复的首字符压缩为一个字符,然后使用压缩后的字符串和正文进行匹配,若匹配成功,对成功匹配的位置信息前的字符和首字符进行循环匹配;如果匹配位数和模式串相同,则返回成功,否则返回失败。改进后的算法大大减少了匹配次数,使执行速度有了明显的提高。Aiming at a large number of repeated characters in the first character and body with Sunday matching algorithm and the falling of the average execution efficiency, an improved algorithm for Sunday matching algorithm is proposed in this paper. Firstly, the repeated first character is compressed to one character, and then the compressed text strings is used to match the body characters. If the match is successful, we continue the cyclic matching of the character in front of position information of successful match and the first character. If the number and pattern of the two strings match, it returns success, otherwise it returns failure. This can reduce a lot of meaningless matching operations. The experimental result shows that the improved algorithm enhances the speed of the algorithm.

关 键 词：SUNDAY 模式匹配 字符串 算法 马尔科夫链 

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