Abstract: Pattern matching algorithm is an important method in intrusion detection. The matching efficiency is the bottleneck of intrusion detection, which indirectly affects the real-time performance of the system. By analyzing four pattern matching algorithms, this paper proposes an improved Sunday algorithm. It finds the character-word in the pattern string before matching, and then compares the character-word and the last word of the pattern string with the text. If the matching fails, the character-word will be moved as far as possible. Experiment of result proves that its match efficiency is better than Sunday algorithm.

Key words: character string, pattern matching, character-word, computational complexity

摘要： 在基于模式匹配的检测方法中，匹配效率是检测技术的瓶颈，间接影响入侵检测系统的实时性能。该文对4种模式匹配算法进行分析后，选择最优的Sunday算法进行改进。该算法进行匹配前先找到模式串中的特征字符(出现概率最小的字符)，进行特征字符与尾字符双重匹配，失败则移动尽可能远的距离。实验结果证明匹配效率比Sunday算法有一定的提高。

关键词: 字符串, 模式匹配, 特征字符, 计算复杂度

CLC Number: 

• TP309