摘要
提出一种改进的AC_BMH算法。该算法利用双字符进行跳跃,可以在增大模式串失配概率的同时跳过更大的距离,通过结合QS算法进一步增加模式串匹配失败时的跳跃距离,并借助压缩存储机制降低内存的使用量。实验结果表明,相比原AC_BMH算法,改进算法的字符串匹配速度提高了29%~52%,在模式串较多时,内存使用量可减少90%。
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 oattern strings exist.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第22期160-162,共3页
Computer Engineering
基金
国家青年基金资助项目(60904023)
关键词
模式匹配
模式串
入侵检测
AC—BMH算法
pattern matching
pattern string
intrusion detection
Aho-Corasick_Boyer-Moore-Horspool(AC_BMH) algorithm