期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Hash函数对WM算法性能的影响 被引量：1

Effect of Hash Function on the Performance of Wu-Manber Algorithm
下载PDF
导出
摘要 针对软件多模式匹配问题,对现有匹配算法做了介绍,分析了Wu-Manber算法的特点,发现采用不同的Hash函数和Hash空间大小可能会得到不同的实际性能.通过试验验证了该结果的正确性.同时指出要提高WM算法的性能,应该采用合适的Hash函数和Hash空间大小. The paper introduces the existing multi-pattern matching algorithms implemented by software,and analysizes the Wu-Manber Algorithm in emphases.According to t h e analysis＇s result,the paper points out that we will gain different performai nce when we adopt different hash function or domain.This conclusion is proved b y experiments,which show that we shall adopt appropriate hash functions or doma in to improve the performance of Wu-Manber algorithm.
作者 张速 王锐利
机构地区 华北水利水电学院 济源职业技术学院
出处 《华北水利水电学院学报》 2011年第3期111-113,共3页 North China Institute of Water Conservancy and Hydroelectric Power
关键词 算法 多模式匹配 WU-MANBER算法 HASH函数 Hash空间 algorithm multi-pattern matching Wu-Manber algorithm Hash function Hash do main
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献11

  • 1Charras C,Lecroq T T. Handbook of Exact String Matching Algorithms[ M ]. London : King' s College London Publica- tions ,2004.
  • 2LIU Ping, LIU Yan-bing, TAN Jian-long. A partition-based efficient algorithm for large scale multiple-strings matching[ C ]//The 12th Symposium on String Processing and Infor- mation Retrieval. Argentina, 2005.
  • 3贺龙涛,方滨兴,余翔湛.一种时间复杂度最优的精确串匹配算法[J].软件学报,2005,16(5):676-683. 被引量：25
  • 4Knuth D E,Morris J H ,Pratt V R. Fast pattern matching in strings[ J]. SIAM Journal on Computing, 1977:323 - 350.
  • 5Aho A V,Corasick MJ. Efficient string matching:an aid to bibliographic search [ J ]. Communication of the ACM, 1975,18(6) :333 -340.
  • 6Boyer R S, Moore J S. A fast string searching algorithm [J]. Communications of the ACM, 1977,20 (10) : 762 - 772.
  • 7Cantone D, Faro S. Fast-search:a new efficient variant of the Boyer-Moore string matching algorithm [ C ]//In : Alberto A,Massimo M, eds. Proc. of the 2nd International Work2 shop on Experimental and Efficient Algorithms (WEA 2003). Lecture Notes in Computer Science 2647, Heidel- berg : Springer-Verlag ,2003:47 - 58.
  • 8Sunday D M. A very fast substring search algorithm [ J ]. Communications of the ACM, 1990,33 ( 8 ) : 132 - 142.
  • 9Wu S, Manber U. A fast algorithm for multi-pattern search- ing[ R]. Report TR-94-17, Department of Computer Sci- ence, University of Arizona, Tucson, AZ, 1994.
  • 10Crochemore M, Rytter W. Text Algorithms[ M ]. Oxford : Ox- ford University Science Press, 1994.

二级参考文献16

  • 1Charras C, Lecroq TT. Handbook of Exact String Matching Algorithms. London: King's College London Publications, 2004.
  • 2Knuth DE, Jr. Morris JH, Pratt VR. Fast pattern matching in strings. SIAM Journal on Computing, 1977,6(1):323-350.
  • 3Baeza-Yates RA, Gonnet GH. A new approach to text searching. Communications of the ACM, 1992,35(10):74-82.
  • 4Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM, 1977,20(10):762-772.
  • 5Sunday DM. A very fast substring search algorithm. Communications of the ACM, 1990,33(8):132-142.
  • 6Cantone D, Faro S. Fast-Search: A new efficient variant of the Boyer-Moore string matching algorithm. In: Alberto A, Massimo M, eds. Proc. of the 2nd Int'l Workshop on Experimental and Efficient Algorithms (WEA 2003). Lecture Notes in Computer Science 2647, Heidelberg: Springer-Verlag, 2003.47-58.
  • 7Crochemore M, Rytter W. Text Algorithms. Oxford: Oxford University Press, 1994.
  • 8Lecroq T. A variation on the Boyer-Moore algorithm. Theoretical Computer Science, 1992,92(1):119-144.
  • 9Crochemore M, Hancart C. Automata for matching patterns. In: Rosenberg G, Salomaa A, eds. Handbook of Formal Languages,volume 2: Linear Modeling: Background and Application. Heidelberg: Springer-Verlag, 1997. 399-462.
  • 10Yao AC. The complexity of pattern matching for a random string. SIAM Journal on Computing, 1979,8(3):368-387.

共引文献24

同被引文献9

引证文献1

二级引证文献1

华北水利水电学院学报
2011年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部