论入侵检测系统的研究与改进，也称好后缀启发。

1 BM算法研究

1977年Boyer和Moore提出了一种全新的算法,即BM算法。它的特点在于匹配过程中,模式从左向右移动,但字符比较却从右向左进行。其基本算法思想是:(1)匹配从右至左进行。(2)若匹配失败发生在Pi≠Ti且Ti不出现在模式P中,则将模式右移直到Pi位于匹配失败位置T的右边第一位(即Ti 1位),若Ti在P中有若干地方出现,则选择j=max{k|Pk=Ti}即通过Skip函数计算文本字符Ti失配时模式向右移动的距离,也称坏字符启发。(3)若模式后面k位与文本T中一致的部分有一部分在P中其他地方出现,则可以将P向右移动,直接使这部分对齐,且要求这一部分尽可能大,Shift函数通过对已经匹配部分的考查决定模式向右移动的距离,也称好后缀启发。

实例分析:

第1次匹配:

Example

here is a simple example

第2次匹配(坏字符启发):

Example

here is a simple example

第3次匹配(坏字符启发):

Example

here is a simple example

第4次匹配(好后缀启发):

Example

here is a simple example

第5次匹配(坏字符启发):

Example

here is a simple example

BM算法预处理时间复杂度为O(m s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(mn)。最坏情况下要进行3n次比较,最好情况下的时间复杂度为O(n/m)。

2 改进BM匹配算法研究

2.1 改进的意义

综合分析会发现虽然BM算法考虑较全面,但它使用了两个数组,预处理时间开销较大,于是在BM算法基础上我们对其进行了简化,使得算法更简单、高效,提出了一种改进的BM算法。通过实验表明改进的模式匹配算法能减少比较次数,有效地提高了匹配效率。

2.2 改进的原理

相关推荐：