改进的AC-BM字符串匹配算法
Improved AC-BM Algorithm for Matching Multiple Strings
-
摘要: 提出了改进的AC-BM算法,将待匹配的字符串集合转换为一个类似于Aho-Corasick算法的树状有限状态自动机。匹配时,采取自后向前的方法,并借用BM算法的坏字符跳转和好前缀跳转技术。改进的AC-BM算法借助BMH算法思想,取消了原AC-BM算法的好前缀跳转,并对坏字符跳转部分的计算进行优化。新算法修改了skip的计算方法,不再保留每个节点的好前缀跳转参数及坏字符跳转参数,因此匹配只与当前匹配字符有关,而与当前节点无关,可以实现大小写正文的识别。Abstract: 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.