摘要：

提出一种改进的AC_BMH算法。该算法利用双字符进行跳跃，可以在增大模式串失配概率的同时跳过更大的距离，通过结合QS算法进一步增加模式串匹配失败时的跳跃距离，并借助压缩存储机制降低内存的使用量。实验结果表明，相比原AC_BMH算法，改进算法的字符串匹配速度提高了29%~52%，在模式串较多时，内存使用量可减少90%。

关键词: 模式匹配, 模式串, 入侵检测, AC_BMH算法

Abstract:

This paper proposes an improved Aho-Corasick_Boyer-Moore-Horspool(AC_BMH) algorithm, which utilizes double-character skip for both larger pattern strings mismatching possibility and further jumping distance, and combines Quick Search(QS) algorithm for even longer jumping distance when pattern strings matching fails. Compact storage mechanism is employed to decrease the amount of memory usage. Experimental results show that the matching speed of string is improved about 29%~52% with the improved algorithm, and the amount of memory used reduces about 90% when many pattern strings exist.

Key words: pattern matching, pattern string, intrusion detection, Aho-Corasick_Boyer-Moore-Horspool(AC_BMH) algorithm

中图分类号: 

• TP301.6