Abstract: Pattern matching is an important algorithm, used by most of intrusion detection system at present. On the basis of analyzing some pattern matching algorithms commonly used, an improved algorithm based on BMHS algorithm, N-BMHS algorithm, is presented. The algorithm adopts the way of matching from both ends to the center, and uses a new array s to record the appearing times of each character in the pattern string. When it equals one, the matched information is used to help getting the maximum moving distance of the pattern. Experimental results show that the improved algorithm can reduce the times of comparing and enhance the matching speed effectively.

Key words: pattern matching, intrusion detection, BMHS algorithm, maximum moving distance, times of comparing

摘要： 模式匹配算法是入侵检测系统中使用较多的一种算法。分析几种常用模式匹配算法，提出一种基于BMHS的改进算法——N-BMHS算法。该算法对字符串进行双向模式匹配，引入一个新的数组s记录模式串中字符的出现次数，次数为1时可以利用已匹配的信息来辅助得到模式串的最大移动距离。实验结果表明，改进的模式匹配算法能减少比较次数，有效提高匹配速度。

关键词: 模式匹配, 入侵检测, BMHS算法, 最大移动距离, 比较次数

CLC Number: 

• TP393.08