基于BM算法的无需预处理的双向匹配算法的研究与

摘　要：基于特征匹配技术的入侵检测系统的速率和效率常常依赖于模式匹配算法的精确性，而算法的效率又依赖于算法的选择和实现方式。随着网络技术的发展，匹配算法优劣有可能成为入侵检测系统的瓶颈，因此要提高入侵检测系统的性能必须对原有算法改进或提出新的算法，本文在对经典BM算法分析、研究的基础上，对该算法进行了部分改进，并给出了基于该改进的新的匹配算法。

关键词：入侵检测系统；模式匹配；BM算法

1.引言

入侵检测^{=4，故应继续向右滑动4个字符位置，即从第26个位置开始比较。}

④ VIRIS

HERE/HAVE/A/VIRILEUS/VIRIS

此时，M₅=“S”，T₂₆=“S”，M₅=T₂₆，因为匹配成功，所以继续向左匹配，不难看出，M₄=T₂₅，M₃=T₂₄，M₂=T₂₃，M₁=T₂₂。因此可以得出结论，匹配完全成功，匹配开始位置为T₂₂。

(3)匹配成功，比较结束。

上例中，使用Boyer-Moore算法，只需进行10次比较操作。这是BF算法(BF算法应用在本例中要比较31次)匹配速度的三倍以上。Boyer-Moore算法的预处理阶段的时间复杂度是O(j+δ)，δ是与M、T相关的有限字符集的长度。查找阶段的时间复杂性在最坏情况下是O(j·k)，在最好情况下是O(k/j)。在一般情况下，BM算法的时间复杂度比BF算法和KMP算法有很大的提高。

3.新算法的设计与实现

基于以上对BM的算法的分析，发现BM的预处理比较费时，增加了算法的时间复杂度，为此提出要是能忽略这个预处理阶段并且还能达到快速的匹配速度，那将在很大程度上提高了模式匹配的速度，进而大大提高程序运行的效率，更能进一步提高入侵检测系统的吞吐量；在此思想的指导下，本文给出一个无需预处理的双向搜索的匹配算法，来减少匹配算法的时间复杂度。

3.1 算法设计

在了解了BM算法和其他的模式匹配后，充分理解了模式匹配算法的思想，在这些算法的基础上设计出了自己的模式匹配算法，对于BM算法是非常经典的模式匹配算法，虽是经典的模式匹配算法，但也有不尽完美之处，像在开始字符串模式匹配时，需要对模式串进行预处理，即要算出模式串中每个字符在匹配不成功时所要滑动的距离值，这个预处理使算法的时间复杂度大大增加，在本文给出的算法无需对模式串进行预处理，直接进行模式匹配，在模式匹配时采用双重循环双向匹配的方式，依然采用传统的自左向右进行模式匹配，在匹配过程中主串不进行回溯操作，只对模式串进行回溯（这是匹配算法中所必需要做的操作），从而大大提高收敛速度，一般情况下模式匹配过程的最大时间复杂度为O(((n-m)/2)m)。