新的自适应多串匹配算法  

New adapted multiple strings matching algorithm

作　　者：宋云[1] 龙际珍[1] 李峰[1] 刘振海[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,长沙410076

出　　处：《计算机工程与应用》2009年第6期98-100,123,共4页Computer Engineering and Applications

基　　金：国家自然科学基金;湖南省自然科学基金~~

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

关 键 词：串匹配 模式匹配 多模式匹配 SBOM算法 WuManber算法 AhoCorasick算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]