字符串模式匹配算法的改进

Improved matching algorithm of string pattern

字符串模式匹配算法是入侵检测系统中的一种重要算法。通过对两种著名的匹配算法KMP和BM算法以及现有的各种改进算法的分析,提出一种简单实用、易于理解的字符串匹配改进算法。该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离。实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率。

String pattern matching is an important algorithm in intrusion detection system. Based on the analysis of two famous KMP and BM algorithms, and of the existing various improved algorithms, an improved string matching algorithm which is simple, practical and easy to understand is proposed. In this algorithm, the possible distance that a pattern backward moves is obtained through the inspi- ration of the characters of special position in the case of each mismatch of string pattern. Each of inspiration distance is calculated from the definition of a unified function, and the maximum one is taken as the actual movement distance of a string pattern shifting backward. The experimental results show that the algorithm reduce the number of times of attempts and comparisons of pattern matching and improve the efficiency of it.