[1]朱宁洪.字符串匹配算法Sunday的改进[J].西安科技大学学报,2016,(01):111-115.
 ZHU Ning-hong.Improvement of Sunday pattern matching algorithm[J].Journal of Xi'an University of Science and Technology,2016,(01):111-115.
点击复制

字符串匹配算法Sunday的改进(/HTML)
分享到:

西安科技大学学报[ISSN:1672-9315/CN:61-1434/N]

卷:
期数:
2016年01期
页码:
111-115
栏目:
出版日期:
2016-02-28

文章信息/Info

Title:
Improvement of Sunday pattern matching algorithm
文章编号:
10.13800/j.cnki.xakjdxxb.2016.0119
作者:
朱宁洪
西安科技大学 计算机科学与技术学院,陕西 西安 710054
Author(s):
ZHU Ning-hong
College of Computer Science and Engineering,Xi'an University of Science and Technology,Xi'an 710054,China
关键词:
Sunday算法 Zhusunday算法 模式匹配 坏字符
Keywords:
Sunday algorithm Zhusunday algorithm pattern matching bad character
分类号:
TP 391
文献标志码:
A
摘要:
字符串的模式匹配应用十分广泛,在信息的搜索查询等方面具有重要作用,研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,算法从右向左搜索当前文本字符在模式串中出现的位置; 找到当前字符在模式串中的位置后继续再向左匹配模式串字符一次,如果仍不匹配时,模式窗口比Sunday算法多向右移动一个字符。改进的算法提高了模式匹配的执行效率,通过大量对比实验证明了该算法的有效性。最后得出结论:在实际应用中,坏字符大量存在的情况下,改进算法的最优时间复杂度可达O(n/m),在同一时间复杂度下,比Sunday算法效率提高25~50%.
Abstract:
String pattern matching is widely used in information search and query,and it is important to study the efficiency of the string matching algorithm with theoretical value and practical significance.On the basis of the analysis of several classical pattern matching algorithms,the paper puts forward a Zhusunday algorithm which is improved from the most widely used Sunday algorithm.The improved position of the algorithm is:in the matching process from the right of the text string to the left,when the character of the text does not match the character of the pattern string,it is not a bad character,the algorithm searches the position of the current text character from the right to the left in the pattern string.After finding the position,the improved algorithm continues to match the two characters in the left for another time.If there is no match,the pattern window will move to right one step more than the movement of Sunday algorithm.The improved algorithm improves the efficiency of the pattern matching,and the effectiveness of the proposed algorithm is proved by a lot of experiments.Finally the paper draws a conclusion:in practical application there are a large number of the bad characters,the optimal time complexity of the improved algorithm is O(n/m),and at the same time complexity,the improved algorithm is more efficient than the Sunday algorithm by 25~50%.

参考文献/References:

[1] 潘冠桦.单模式字符串匹配算法效率的研究[D].太原:太原理工大学,2013. PAN Guan-hua.Research on the efficiency of single mode string matching algorithm[D].Taiyuan:Taiyuan University of Technology, 2013.
[2] 孙艺珍,季小迪,张京涛.基于.Net的全文搜索引擎设计与实现[J].西安科技大学学报,2014,34(6):701. SUN Yi-zhen,JI Xiao-di,ZHANG Jing-tao.Design and implementation of full text search engine based on.Net[J].Journal of Xi' an University of Science and Technology,2014,34(6):701.
[3] 马 莉,李树刚,肖 鹏,等.云计算环境下煤矿应急管理海量数据存储技术[J].西安科技大学学报,2014,34(5):596. MA Li,LI Shu-gang,XIAO Peng,et al. Mass data storage technology of coal mine emergency management in cloud computing environment[J].Journal of Xi' an University of Science and Technology,2014,34(5):596.
[4] 李军民,李立博.人工鱼群和蒙特卡罗混合算法的应用[J].西安科技大学学报,2014,34(2):224. LI Jun-min,LI Li-bo.Application of artificial fish swarm and Monte Carlo hybrid algorithm[J].Journal of Xi' an University of Science and Technology,2014,34(2):224.
[5] 巫喜红,凌 捷.基于字符频率的字符串模式匹配算法的研究[J].制造业自动化,2013,35(9):11-14. WU Xi-hong,LING Jie.Research on string pattern matching algorithm based on character frequency[J].Manufacturing Automation,2013,35(9):11-14.
[6] 许元飞 基于纹理的图像检索算法研究[J].西安科技大学学报,2013,33(4):470. XU Yuan-fei.Research on texture based image retrieval algorithm[J].Journal of Xi' an University of Science and Technology,2013,33(4):470.
[7] 徐 珊,袁小坊.Sunday字符串匹配算法的效率改进[J].计算机工程与应用,2011,47(29):96-98. XU Shan,YUAN xiao-fang. Efficiency improvement of Sunday string matching algorithm[J].Computer engineering and Application,2011,47(29):96-98.
[8] 潘冠桦,张兴忠.Sunday算法效率分析[J].计算机应用,2012,32(11):3 082-3 084. PAN Guan-hua,ZHANG Xing-zhong.Efficiency analysis of Sunday algorithm[J].Computer Applications,2012,32(11):3 082-3 084.
[9] 冯川放.规则引擎技术的可配置EOS平台的设计与实现[J].西安科技大学学报,2013,33(3):353. FENG Chuan-fang. Design and implementation of configurable EOS platform for rule engine technology[J].Journal of Xi' an University of Science and Technology,2013,33(3):353.
[10]李明月,张善卿,陆剑锋,等.一种改进的Sunday匹配算法[J].杭州电子科技大学学报,2015,35(1):93-97. LI Ming-yue,ZHANG Shan-qing,LU Jian-feng,et al.An improved Sunday matching algorithm[J].Journal of Hangzhou Electronic and Science University,2015,35(1):93-97.

备注/Memo

备注/Memo:
收稿日期:2015-07-29 责任编辑:高 佳 基金项目:国家自然基金(煤炭联合基金)(U1261114) 作者简介:朱宁洪(1969-),男,山东兖州人,讲师,E-mail:zhuninghong@sohu.com
更新日期/Last Update: 1900-01-01