| 改进的AC-BM字符串匹配算法 |
| |
| 引用本文： | 万国根,秦志光. 改进的AC-BM字符串匹配算法[J]. 电子科技大学学报(社会科学版), 2006, 0(4) |
| |
| 作者姓名： | 万国根 秦志光 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院 成都610054 |
| |
| 基金项目： | 国家信息产业部资助项目(2001-研-0-024) |
| |
| 摘 要： | 提出了改进的AC-BM算法,将待匹配的字符串集合转换为一个类似于Aho-Corasick算法的树状有限状态自动机。匹配时,采取自后向前的方法,并借用BM算法的坏字符跳转和好前缀跳转技术。改进的AC-BM算法借助BMH算法思想,取消了原AC-BM算法的好前缀跳转,并对坏字符跳转部分的计算进行优化。新算法修改了skip的计算方法,不再保留每个节点的好前缀跳转参数及坏字符跳转参数,因此匹配只与当前匹配字符有关,而与当前节点无关,可以实现大小写正文的识别。
|
| 关 键 词： | 算法 字符串匹配 内容分析 入侵检测 |
Improved AC-BM Algorithm for Matching Multiple Strings |
| |
| WAN Guo-gen,QIN Zhi-guang. Improved AC-BM Algorithm for Matching Multiple Strings[J]. Journal of University of Electronic Science and Technology of China(Social Sciences Edition), 2006, 0(4) |
| |
| Authors: | WAN Guo-gen QIN Zhi-guang |
| |
| Abstract: | ACBM is a Boyer-Moore like algorithm applied to a set of 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. |
| |
| Keywords: | algorithm string matching content analysis intrusion detection |
| 本文献已被 CNKI 等数据库收录！ |
|
