一种改进的Wu-Manber多模式串匹配算法

下载PDF

导出

摘要针对Wu-Manber算法在模式串后缀与文本后缀相匹配的情况下,至少需要进行一次查找PREFIX表的比较操作的特点,提出一种改进的Wu-Manber算法,将PREFIX表信息合并到HASH表中,减少匹配过程中的查表比较次数,提高算法性能。

作者刘征宇刘学生

机构地区海军驻上海地区水声导航系统军事代表室江苏自动化研究所

出处《自动化应用》 2015年第5期5-8,共4页 Automation Application

基金国家自然科学基金青年基金项目资助(61305050) 江苏省自然科学基金青年基金项目资助(BK2012236)

关键词 WU-MANBER算法多模式串匹配后缀信息前缀信息

参考文献8

1Knuth D E, Morris H, Pratt V R. Fast pattern matching in strings[J]. SIAM J Comp, 1977, 6(2):323-350.
2Boyer R S, Moore J S. A fast string searching algorithm [J]. Communications of the ACM, 1977, 20(10):762-772.
3Sunday D M. A very fast substring search algorithm [J]. Communications of the ACM, 1990, 33(8): 132-142.
4Aho A V, Corasick M J. Efficient string matching: An aid to bibliographic search [J]. Communications of the ACM, 1975, 18:333-340.
5Wu Sun, Manber U. A Fast Algorithm for Multi-Pattern Searching[R]. Technical Report TR 94-17, University of Arizona at Tuscon, 1994:1-11.
6Beate Commentz-Walter. A string matching algorithm fast on the average[A]. In:Proceedings of the 6th Collo- quium, on Automata, Languages and Programming [C]. Springer-Verlag, London, 1979:118-132.
7杨东红,徐恪,崔勇.改进的Wu-Manber多模式串匹配算法[J].清华大学学报（自然科学版）,2006,46(4):555-558. 被引量：13
8Wu Sun, Manber U. Agrep: A fast approximate pat- tern-matching tool[A]. Proc of the USENIX Technical Conference[C]. San Fransisco, CA, 1992 : 153-162.

1李雪莹,刘宝旭,许榕生.字符串匹配技术研究[J].计算机工程,2004,30(22):24-26. 被引量：26
2Knuth D E,Morris H,Pratt V R.Fast pattern matching in strings[J].SIAM J Comp,1977,6:323-350.
3Boyer R S,Moore J S.A fast string searching algorithm[J].Communications of the ACM,1977,20:762-772.
4Aho A V,Corasick M J.Efficient string matching:An aid to bibliographic search[J].Communications of the ACM,1975,18:333-340.
5WU Sun,Manber U.A Fast Algorithm for Multi-Pattern Searching[R].Technical Report TR 94-17,University of Arizona at Tuscon,May 1994.
6Tuck N,Sherwood T,Calder B,et al.Deterministic memory efficient string matching algorithms for intrusion detection[A].Proceedings of IEEE Infocom[C].Hong Kong,March 2004.
7WU Sun,Manber U.Agrep-A fast approximate pattern-matching tool[A].Proc of the USENIX Technical Conference[C].San Fransisco,CA,1992.153-162.
8Sunday D M.A very fast substring search algorithm[J].Communications of the ACM,1990,33(8):132-142.
9Lecroq T.Experimental results on string matching algorithms[J].Software-Practice & Experience,1995,25(7):727-765.
10Manber U.AGREP,an approximate GREP[OL].http://www.tgries.de/agrep/,2005.

自动化应用

2015年第5期

内容加载中请稍等...