Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (6): 98-100.DOI: 10.3778/j.issn.1002-8331.2009.06.028

• 网络、通信、安全 • Previous Articles     Next Articles

New adapted multiple strings matching algorithm

SONG Yun,LONG Ji-zhen,LI Feng,LIU Zhen-hai   

  1. Department of Computer and Communication Engineering,Changsha University of Science & Technology,Changsha 410076,China
  • Received:2008-08-25 Revised:2008-11-07 Online:2009-02-21 Published:2009-02-21
  • Contact: SONG Yun

新的自适应多串匹配算法

宋 云,龙际珍,李 峰,刘振海   

  1. 长沙理工大学 计算机与通信工程学院,长沙 410076
  • 通讯作者: 宋 云

Abstract: AMSM is a new adapted multiple strings matching algorithm,which can search the mass data by one-pass with space-efficient and time-efficient.It can be used for the real-time network information monitoring and DNA sequences matching.A summary about the state of art of exact pattern matching algorithms is introduced in this paper,AMSM is combined of SBOM and WuManber algorithms and it employs two approaches: precise bad block character shift and weakened Oracle shift to improve the original algorithm.From a practical standpoint,the AMSM runs faster than state-of-art algorithm such as WuManber and SBOM in many cases.From a theory point,it is a simulator of WuManber or SBOM algorithm using each argument profile.

摘要: 在不同关键词规模、最短关键词长度和字符集大小等情况下,有效的多串匹配算法是不同的。新提出的自适应多串匹配算法(Adapted Multiple Strings Matching Algorithm,AMSM)改善了SBOM算法中Oracle树存在不精确跳跃计算的缺点,同时采用了WuManber算法的块跳跃策略和压缩形式的Oracle树比较策略,提高了算法的性能,可适用于各种情况,是一种通用多串(多模式)匹配算法。