改进的AC-BM字符串匹配算法  

Improved AC-BM Algorithm for Matching Multiple Strings

作　　者：万国根[1] 秦志光[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《电子科技大学学报》2006年第4期531-533,541,共4页Journal of University of Electronic Science and Technology of China

基　　金：国家信息产业部资助项目(2001-研-0-024)

摘　　要：提出了改进的AC-BM算法,将待匹配的字符串集合转换为一个类似于Aho-Corasick算法的树状有限状态自动机。匹配时,采取自后向前的方法,并借用BM算法的坏字符跳转和好前缀跳转技术。改进的AC-BM算法借助BMH算法思想,取消了原AC-BM算法的好前缀跳转,并对坏字符跳转部分的计算进行优化。新算法修改了skip的计算方法,不再保留每个节点的好前缀跳转参数及坏字符跳转参数,因此匹配只与当前匹配字符有关,而与当前节点无关,可以实现大小写正文的识别。ACBM is a Boyer-Moore like algorithm applied to a set of keywords held in an Aho-Corassick like keyword tree that overlays common prefixes of the keywords. The algorithm takes the best characteristics of both the Boyer-Moore and Aho-Corasick. Based on the idea of Boyer-Moore-Horspool, we make an improvement to AC-BM algorithm. In the improved version, the Good Prefix Shift is not performed, the.Bad Character Shift function is improved, the Goto procedure is also modified which do not keep the parameters of Good Prefix Shift and Bad Character Shift.

关 键 词：算法 字符串匹配 内容分析 入侵检测 

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