由于毕业设计(入侵检测)的需要,这两天仔细研究了BM模式匹配算法,稍有心得,特此记下。
首先,先简单说明一下有关BM算法的一些基本概念。
BM算法是一种精确字符串匹配算法(区别于模糊匹配)。
BM算法采用从右向左比较 的方法,同时应用到了两种启发式规则,即坏字符规则 和好后缀规则 ,来决定向右跳跃的距离。
BM算法的基本流程: 设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较 ,如下图所示:
若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则 和好后缀规则 ,来计算模式串向右移动的距离,直到整个匹配过程的结束。
下面,来详细介绍一下坏字符规则 和好后缀规则 。
首先,诠释一下坏字符和好后缀的概念。
请看下图:
图中,第一个不匹配的字符(红色部分)为坏字符,已匹配部分(绿色)为好后缀。
1)坏字符规则(Bad Character):
在BM算法从右向左扫描的过程中,若发现某个字符x不匹配,则按如下两种情况讨论:
i. 如果字符x在模式P中没有出现,那么从字符x开始的m个文本显然不可能与P匹配成功,直接全部跳过该区域即可。
ii. 如果x在模式P中出现,则以该字符进行对齐。
用数学公式表示,设Skip(x)为P右移的距离,m为模式串P的长度,max(x)为字符x在P中最右位置。
例1:
下图红色部分,发生了一次不匹配。
计算移动距离Skip(c) = 5 - 3 = 2,则P向右移动2位。
移动后如下图:
2)好后缀规则(Good Suffix):
若发现某个字符不匹配的同时,已有部分字符匹配成功,则按如下两种情况讨论:
i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现,且位置t'的前一个字符与位置t的前一个字符不相同,则将P右移使t'对应t方才的所在的位置。
ii. 如果在P中任何位置已匹配部分P'都没有再出现,则找到与P'的后缀P''相同的P的最长前缀x,向右移动P,使x对应方才P''后缀所在的位置。
用数学公式表示,设Shift(j)为P右移的距离,m为模式串P的长度,j 为当前所匹配的字符位置,s为t'与t的距离(以上情况i)或者x与P''的距离(以上情况ii)。
以上过程有点抽象,所以我们继续图解。
例2:
下图中,已匹配部分cab(绿色)在P中再没出现。
再看下图,其后缀T'(蓝色)与P中前缀P'(红色)匹配,则将P'移动到T'的位置。
移动后如下图:
自此,两个规则讲解完毕。
在BM算法匹配的过程中,取SKip(x)与Shift(j)中的较大者作为跳跃的距离。
BM算法预处理时间复杂度为O(m+s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(m·n)。
最好情况下的时间复杂度为O(n/m),最坏情况下时间复杂度为O(m·n)。
如果有兴趣了解更多有关BM算法的朋友,请关注我的另一篇文章 BM模式匹配算法-实现(C语言)
分享到:
相关推荐
详细介绍了BM字符串匹配的方法及效率问题.
精典的字符串匹配算法--BM算法的实现代码,文件中为VC6工程.已调试通过.
精典的多模式匹配算法,AC-BM算法的实现代码.在VC6中调试通过.文件中代工程文件.
各种字符串匹配算法--BM,KMP等。。。。。。。。。。。。。。。。。。。
IBM模式匹配算法,对中文分析,信息分拣感兴趣的都可以去看看。
单模式匹配算法 BM算法 很经典的单模式算法
Snort入侵检测使用的BM模式匹配算法,单独列出来了。
全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
从网络入侵检测中提炼出的BM算法,已在VC6中调试通过.
多模式匹配算法 AC_BM算法 算法很经典 欢迎下载
不知道是自己的搜索能力太差还是怎么的,在CSDN上多花了6分下载这些资源,这是我上传的不需要分的资源,enjoy it...
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
使用了BM匹配算法计算了左右图像的视差图,本次BM匹配算法是使用python3.7,通过调用opencv库函数实现
BM字符匹配算法是当今简单有效的匹配算法,特别适合搜索匹配应用,这是一个简单的示例代码。
一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
BM3D图像去噪算法原理及代码详解.docx
研究BM串匹配算法,分析国内外各种改进算法,结合其优缺点,增加对模式串串末字符或坏字符的邻接字符在模式串中的首次出现位置、存在性、惟一性的判断。根据判断的结果对移动距离重新设置,增加模式串移动距离,减少...
AC-BM多模式匹配算法的研究与改进 ,张慧,罗守山,随着互联网行业的发展,信息的多渠道获得,信息的安全性得到了社会的广泛关注。本文对作为防火墙核心技术之一的模式匹配算法进行
在分析了目前常用的模式匹配算法的基础上,提出了一种改进的BM算法。实验结果表明改进的模式匹配算法能减少比较次数,有效地提高了匹配速度。