首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一种改进的Sunday模式匹配算法
引用本文:李映刚.一种改进的Sunday模式匹配算法[J].四川理工学院学报(自然科学版),2013,26(2):78-81.
作者姓名:李映刚
作者单位:成都理工大学管理科学学院,成都,610059
基金项目:中国地质调查局地质调查工作项目
摘    要:字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能。在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进。改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置。每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数。在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配。实验结果表明改进算法的效率比Sunday算法有一定提高。

关 键 词:字符串  模式匹配  倒序字符匹配  Sunday算法

An Improved Sunday Pattern Matching Algorithm
LI Ying-gang.An Improved Sunday Pattern Matching Algorithm[J].Journal of Sichuan University of Science & Engineering:Natural Science Editton,2013,26(2):78-81.
Authors:LI Ying-gang
Institution:LI Ying-gang(School of Management Science,Chengdu University of Technology,Chengdu 610059,China)
Abstract:The efficiency of character matches are the performance bottlenecks of many computer applications,an algorithm which improves the efficiency of the characters match can contribute to enhancing the application performance of the system.Based on the analysis of Sunday pattern mathching algorithm,many improvements have been done.This improved algorithm calculation the mode string's Reverse Eigenvalue before string matching so that it can calculate the reverse position beside themselves for characters of the last s mode string.Every character matching is the descending match and got by the result of it,in which combination the result of the descending match and the Reverse Eigenvalue can directly determine the next displacement number of the mode string.After once character matching,the mode string is traversed to calculate the next displacement number by Sunday algorithm(it uses one character).which can exclude many invalid match by simply increasing the number of traversal characters.Experimental results show that the efficiency improved algorithms to Sunday algorithm has definitely improved.
Keywords:string  pattern matching  descending character matching  Sunday algorithm
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号