全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种改进的多模式串匹配算法*

, PP. 47-51

Keywords: 多模式串匹配,BoyerMoore算法,QuickSearch算法,SunWu算法

Full-Text   Cite this paper   Add to My Lib

Abstract:

在对著名的SunWu多模式串匹配算法进行分析之后,结合QS算法的优点,设计了一种较高效的多模式串匹配算法QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.

References

[1]  Tan J L. String Matching Algorithm and Application of Network Content Analysis. Ph.D Dissertation. Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 2003 (in Chinese) (谭建龙. 串匹配算法机器在网络内容分析中的应用.博士学位论文. 中国科学院计算技术研究所,北京, 2003)
[2]  Boyer R S, Moore J S. A Fast String Searching Algorithm. Communications of the ACM, 1977, 20(10): 762-772
[3]  Sunday D M. A Very Fast Substring Search Algorithm. Communications of the ACM, 1990, 33(8): 132-142
[4]  Lecroq T. Experimental Results on String Matching Algorithms. Software-Practice & Experience, 1995, 25(7): 727-765
[5]  Wang Y C, Shen Z, Xu Y Z. Improved Algorithms for Matching Multiple Patterns. Journal of Computer Research and Development, 2002, 39(1): 55-60 (in Chinese) (王永成, 沈 州, 许一震. 改进的多模式匹配算法. 计算机研究与发展, 2002, 39(1): 55-60)
[6]  Aho A V, Corasick M J. Efficient String Matching: An Aid to Bibliographic Search. Communication of the ACM, 1975, 18(6): 333-340
[7]  Wu S, Manber U. A Fast Algorithm for Multi-Pattern Searching. Technical Report, TR-94-17, Department of Computer Science, University of Arizona, Tucson, USA, 1994
[8]  Zhang X, Tan J L, Cheng X Q. An Improved Wu-Manber Multiple Keywords Match Algorithm. Journal of Computer Application, 2003, 23(7): 29-31 (in Chinese) (张 鑫, 谭建龙, 程学旗. 一种改进的Wu-Manber多关键字匹配算法. 计算机应用, 2003, 23(7): 29-31)
[9]  http://www.research.att.com/~lewis/reuters21578.html

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133