BM算法概念

格式：doc
大小：138.50 KB
文档页数：7

下载文档原格式

/ 7

AC算法BM算法

AC算法BM算法AC算法（Aho-Corasick Algorithm）AC算法是一种字符串算法，通常用于在一段文本中查询多个模式串的出现情况。

它是由Alfred V. Aho和Margaret J. Corasick于1975年提出的，并以他们的名字命名。

AC算法的原理是构建一个有限状态机（FSM），该状态机能够同时处理多个模式串的匹配。

该算法具有高效的时间和空间复杂度，并且能够在一次扫描内找到所有模式串的匹配位置。

下面将介绍AC算法的详细步骤：1. 构建Trie树（前缀树）：根据给定的模式串集合，构建一个Trie树。

Trie树是一种特殊的字典树，它能够实现快速的字符串匹配。

Trie树的根节点为一个空节点，每个节点都有多个子节点，每个子节点都代表一个字符。

从根节点到叶子节点的路径上的所有字符组成一个模式串。

2. 构建失败指针（Fail Pointer）：在Trie树中，每个节点的失败指针指向它的最长后缀节点，该后缀节点也是Trie树的节点。

如果一个节点的当前字符在其最长后缀节点的子节点中不存在，则将失败指针指向最长后缀节点的失败指针指向的节点。

如果没有最长后缀节点，则将失败指针指向根节点。

3. 在文本中匹配模式串：从文本的第一个字符开始，按照Trie树的路径进行匹配。

如果在一些节点匹配失败，则通过失败指针转移到下一个节点进行匹配，直到匹配成功或到达文本的末尾。

当匹配成功时，可以通过沿着失败指针回溯，找到其他可能的匹配位置。

4.输出匹配结果：对于每个文本字符，记录匹配的模式串。

使用一个结果链表，其中每个节点包括一个指向匹配的模式串的指针和该模式串在文本中的位置。

AC算法的时间复杂度为O(n+m)，其中n是文本的长度，m是模式串的总长度。

空间复杂度为O(m)，即模式串的长度。

BM算法（Boyer-Moore Algorithm）BM算法是一种字符串和匹配算法，通过对模式串的后缀进行预处理，实现在文本中的快速。

BM算法详解

BM算法详解BM算法后缀匹配，是指模式串的⽐较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮⼒匹配算法的改进。

为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利⽤好后缀和坏字符可以⼤⼤加快模式串的移动距离，不是简单的++j，⽽是j+=max (shift(好后缀), shift(坏字符)) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个字符，继续⽐较，如下图：坏字符出现在模式串中，这时可以把模式串第⼀个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图：此处配的图是不准确的，因为显然加粗的那个b并不是”最靠右的”b。

⽽且也与下⾯给出的代码冲突！我看了论⽂，论⽂的意思是最右边的。

当然了，尽管⼀时⼤意图配错了，论述还是没有问题的，我们可以把图改正⼀下，把圈圈中的b改为字母f就好了。

接下来的图就不再更改了，⼤家⼼⾥有数就好。

为了⽤代码来描述上述的两种情况，设计⼀个数组bmBc['k']，表⽰坏字符‘k’在模式串中出现的位置距离模式串末尾的最⼤长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。

如下图：数组bmBc的创建⾮常简单，直接贴出代码如下：1 void preBmBc(char *x, int m, int bmBc[]) {23 int i;45 for (i = 0; i < ASIZE; ++i)67 bmBc[i] = m;89 for (i = 0; i <= m - 1; ++i)1011 bmBc[x[i]] = m - i - 1;1213 } 代码分析：ASIZE是指字符种类个数，为了⽅便起见，就直接把ASCII表中的256个字符全表⽰了，哈哈，这样就不会漏掉哪个字符了。

BM立体匹配算法的参数详解

BM立体匹配算法的参数详解1. 最小视差（Minimum Disparity）：表示在计算深度图时允许的最小视差值，即物体最近处的深度差异。

选择合适的最小视差值对于过滤无意义的区域非常重要。

2. 最大视差（Maximum Disparity）：表示在计算深度图时允许的最大视差值，即物体最远处的深度差异。

选择合适的最大视差值可以防止视差计算的误差。

3. 视差窗口大小（Disparity Window Size）：表示计算每个像素的视差时，使用的窗口大小。

较大的窗口尺寸可以提供更准确的深度信息，但也会增加计算时间。

通常情况下，窗口大小是一个奇数，最常见的是3、5或74. 匹配代价度量（Matching Cost Metric）：用于计算两个像素之间的匹配代价的度量方法。

最常见的度量方法是灰度差异和绝对差异，也可以根据特定的应用选择适当的度量方法。

5. 匹配代价聚合（Matching Cost Aggregation）：用于减少匹配代价图像中的噪声和不一致性的技术。

常用的方法包括平均代价和双边滤波。

6. 视差图优化（Disparity Map Optimization）：通过优化视差图像，减少错误匹配和噪声，并提高深度估计的准确性。

常用的方法包括视差图扩张、视差图填充和视差图平滑。

7. 左右一致性检查（Left-Right Consistency Check）：用于消除左右图像之间不一致匹配的误差。

该步骤通过检查左右视图之间的匹配来得到更准确的视差图。

8. 剔除无效区域（Invalid Region Exclusion）：根据特定应用需求，去除由于遮挡、反射等原因导致的无效区域。

可以使用其他传感器信息或额外的图像处理技术来实现。

9. 空洞填充（Occlusion Filling）：通过使用图像分割或插值算法填充由遮挡产生的空洞。

这可以提供更完整和连贯的深度图像。

10. 算法效率（Algorithm Efficiency）：BM算法的计算效率对于实时应用很重要。

BM算法-专业文档

BM算法BM算法，即Boyer-Moore算法，是一种被广泛应用于字符串匹配的算法。

它由Robert S. Boyer和J Strother Moore于1977年提出，并在一些文本搜索和字符串匹配的应用中表现出优异的性能。

下面将对BM算法进行详细的介绍。

一、算法概述BM算法是一种自底向上的字符串匹配算法，它通过构建坏字符规则和好后缀规则来决定模式串的移动距离。

相比于朴素的字符串匹配算法，BM算法在匹配失败时能够根据模式串和文本串的已知信息进行跳跃，从而提高了匹配的效率。

二、坏字符规则坏字符规则是指当模式串与文本串的某个字符不匹配时，我们可以根据这个不匹配的字符来确定模式串应该向右移动的距离。

为了实现这个规则，我们需要预先构建一个坏字符表，其中记录了每个字符在模式串中最后一次出现的位置。

当发生不匹配时，我们可以直接将模式串向右移动到坏字符表中对应字符的位置。

三、好后缀规则好后缀规则是指当模式串与文本串的后缀部分匹配成功时，我们可以根据这个好后缀来确定模式串应该向右移动的距离。

为了实现这个规则，我们需要预先构建一个前缀表和后缀表，其中记录了每个前缀或后缀在模式串中第一次出现的位置。

当发生匹配时，我们可以根据前缀表和后缀表中的信息来确定模式串应该向右移动的距离。

四、算法步骤1.预处理阶段：构建坏字符表和前缀表、后缀表。

2.匹配阶段：从左到右依次比较模式串和文本串的字符。

3.如果发生不匹配：根据坏字符规则将模式串向右移动相应的距离。

4.如果匹配成功：根据好后缀规则将模式串向右移动相应的距离。

5.重复步骤2-4直到模式串移动到文本串的末尾位置。

五、算法性能分析BM算法的时间复杂度为O(n)，其中n为文本串的长度。

在最好的情况下，BM 算法的时间复杂度可以达到O(n/m)，其中m为模式串的长度。

相比于朴素的字符串匹配算法，BM算法在处理较长的文本串时具有更好的性能表现。

六、总结BM算法是一种经典的字符串匹配算法，它通过结合坏字符规则和好后缀规则来实现高效的字符串匹配。

BM算法讲解

由于毕业设计（入侵检测）的需要，这两天仔细研究了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''后缀所在的位置。

BM算法详解

BM算法详解来源在没有BM算法时，其原始算法是从后往前进⾏匹配，需要两层循环，判断以某个字符为结尾的⼦串是否和模式串相等，这种算法也称作暴搜；贴上代码：void BLS(string s, string p) {int s_len = s.size(), p_len = p.size();int j = 0, i = 0;while (j <= s_len - p_len) {for (i = p_len - 1; i >= 0 && p[i] == s[i + j]; --i) {}if (i < 0) {cout << "match: " << i + j + 1 << endl;j += p_len;}elsej++;}}算法的思想还是⽐较容易理解的，i和j分别指的是，模式串中已经匹配的位数，模式串相对于原串移动的位数；移动规则算法包含了两个重要的内容，分别是好后缀和坏字符的规则；坏字符：当模式串和原串的字符并不匹配时，原串中的字符就称为坏字符；好后缀：模式串和原串的字符相等时所有的字符串，⽐如ABCD和BCD，那么它的好后缀则包括第⼀次匹配的D，和第⼆次匹配的CD，还有第三次的BCD；例⼦：BM算法的向右移动模式串的距离就是取坏字符和好后缀算法得到的最⼤值；这两个内容分别拥有着⼏条规则，需要注意：坏字符1. 坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个位置，继续⽐较；⽐如说，ABC和D，其中D和A对齐，因为不匹配，所以D会移动到和B对齐；2. 坏字符出现在模式串中，这时可以把模式串中第⼀个出现（从后往前数第⼀个出现，也就是从前往后数，最靠右出现的）的坏字符和原串的坏字符对齐；⽐如说，BCCBCAD和AAD，假如其中AAD和BCC对齐，发现D和C⽆法匹配，移动到和BCA匹配，此时同样不匹配，但是A存在于模式串中，所以移动到模式串中坏字符出现的上⼀次位置，也就是向后移⼀位，和CAD对齐；当⾸次⽐较就⽆法匹配时，那么肯定是运⽤坏字符规则，因为并不存在好后缀；所以我们发现坏字符的移动规则公式为：后移位数＝坏字符的位置－模式串中的上⼀次出现位置那⽤代码表⽰则是void preBmBc(string x, vector<int>& bmBc) {int i = 0;int len = (int)x.size();// 全部更新为⾃⼰的长度for (i = 0; i < ASIZE; ++i) {bmBc[i] = len;}// 计算字符串中每个字符距离字符串尾部的长度for (i = 0; i < x.size() - 1; ++i) {bmBc[x[i]] = len - i - 1;}}⾸先应该知道的是，bmBc存储的是坏字符出现的位置距离模式串末尾的最⼤长度；前⼀个循环⽤来处理第⼀种规则，因为遇见不匹配时，直接移动模式串的长度；后⼀个循环处理第⼆种规则，需要注意的是，因为要保证最靠右原则，所以要从头开始循环，从⽽使得当遇见相同的字符，后者可以将前者进⾏覆盖。

AC算法BM算法

AC算法BM算法AC算法（Aho-Corasick Algorithm）和BM算法（Boyer-Moore Algorithm）都是一种用于在一个大文本中查找多个关键词的字符串匹配算法。

它们都具有高效的时间复杂度和较低的内存消耗，适用于很多实际应用场景。

AC算法是由Alfred V. Aho和Margaret J. Corasick于1975年提出的一种多模式匹配算法。

该算法主要用于匹配一个文本中的多个关键词，比如在引擎中匹配用户输入的多个关键词。

AC算法的核心思想是构建一个状态机来匹配关键词，通过一种类似于字典树的数据结构来高效地存储关键词，并利用自动机的转移函数进行匹配操作。

AC算法的具体实现过程如下：1.构建一个关键词集合，将所有关键词插入到一个类似于字典树的数据结构（通常称为AC自动机）中，其中节点表示状态，边表示状态之间的转移。

2.根据插入的关键词构建AC自动机的转移函数，即每个状态的状态转移表。

这个过程主要是通过BFS（广度优先）算法来实现的。

3.根据AC自动机进行文本匹配，也就是遍历待匹配文本的字符，并根据状态转移表进行状态转移，如果遇到一个匹配状态，则找到了一个关键词的匹配。

相比于传统的字符串匹配算法，AC算法的时间复杂度是O(N+M)，其中N是文本长度，M是总的关键词个数。

AC算法的优势主要体现在其高效的多模式匹配能力以及较小的内存消耗。

BM算法是由Robert S. Boyer和J Strother Moore于1977年提出的一种字符串匹配算法。

该算法采用了从左到右的匹配策略，结合了好后缀规则和坏字符规则两种启发式方法进行匹配操作，能够快速定位匹配失败的位置，并进行有效的后移操作。

BM算法的具体实现过程如下：1.从待匹配文本的末尾开始，与关键词的末尾进行匹配。

2.如果遇到不匹配的字符，根据坏字符规则计算出错位数，即将关键词后移一定的距离。

3.如果遇到好后缀，则根据好后缀规则计算正确的后移位数，即将关键词后移一定的距离。

第14讲--BM算法

虑，要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。
4
1、概念简介
设 a (a0., a1,......,aN1) 是GF (2上) 的长度为N的序列，而 f (x) c0 c1x c2 x2 ...... cl xl 是GF (2上) 的多项式，c0=1.
2、规定：0级线性移位寄存器是以f(x)=1为联系多项式的线性移位寄存器，且n长(n=1, 2, …, N)全零序列，仅由0级线性移位寄存器产生。事实上，以f(x)=1为联系多项式的递归关系式是：ak=0，k=0, 1, …, n-1.因此，这一规定是合理的。
3、给定一个N长二元序列a，求能产生a并且级数最小的线性移位寄存器，就是求a的线性综合解。利用B-M算法可以有效的求出。
12
如果序列中的元素满足递推关系：
ak c1ak1 c2ak2 ...... cl akl , k l, l 1, ......, N 1
(2)
则称 f (x),l 产生二元序列a。其中 f (x),l 表示以f(x)为联系
多项式的l级线性移位寄存器。
如果f(x)是一个能产生a并且级数最小的线性移位寄存器的联系多项式，l是该移存器的级数，则称 f (x),l 为序列a的线性综合解。
3
（二）、B-M迭代算法
根据密码学的需要，对线性反馈移位寄存器 (LFSR)主要考虑下面两个问题：
（1）如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列，即固定级数时，什么样的移存器序列周期最长。这是从密钥生成角度考虑，用最小的代价
产生尽可能好的、参与密码变换的序列。
（2）当已知一个长为N序列a时，如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考

字符串匹配算法

字符串匹配算法
字符串匹配算法是指在一个文本串S中查找一个模式串P的算法。

它的目的是在S中找出所有和P匹配的子串。

常用的字符串匹配算法有暴力匹配算法、KMP算法、BM算法和Sunday算法等。

1. 暴力匹配算法：
暴力匹配算法也叫朴素匹配算法，它是一种最简单的字符串匹配算法，它的基本思想是：从文本串S的左端开始，一个一个字符地与模式串P进行比较，直到文本串S中出现和模式串P完全匹配的子串为止。

2. KMP算法：
KMP算法是由Donald Knuth、Vaughan Pratt和James H.
Morris三人于1977年提出的一种改进的字符串匹配算法，它利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

3. BM算法：
BM算法是由Boyer和Moore于1977年提出的一种改进的字符串匹配算法，它的基本思想是：利用匹配失败后的信息，从匹配失败的位置开始逆向查找，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

4. Sunday算法：
Sunday算法是由Udi Manber和Sun
Wu于1992年提出的一种改进的字符串匹配算法，它的基本思想是：利用匹配失败后的信息，从匹配失败的位置开始查找，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

kmp算法bm算法

kmp算法bm算法
KMP算法和BM算法都是字符串匹配算法，用于在一个主串中查找特定的子串。

两者的不同点在于匹配失败时如何利用已匹配成功的信息进行下一次匹配。

KMP算法全称为Knuth-Morris-Pratt算法，是由Donald Knuth、James H. Morris和Vaughan Pratt于1977年联合发表的。

其核心思想是利用已经匹配成功的信息来消除无用的匹配。

具体实现中，KMP算法使用一个前缀函数数组F来记录每个子串的前缀中最长的既是该子串的真前缀又是该子串的真后缀的长度，若在匹配中出现了失配，则可利用前缀函数的信息进行跳转，以避免重复的匹配。

KMP算法在理论和实践中均有很高的效率和广泛的应用，例如在文本编辑器和编译器中常常使用KMP算法来实现查找和替换的功能。

BM算法全称为Boyer-Moore算法，是由Robert S. Boyer和J Strother Moore于1977年发明的另一个字符串匹配算法。

BM算法的核心思想是从模式串的末尾逐个比较主串中的字符，若出现不匹配的字符，则尽可能地利用模式串中已经匹配的字符的关系向后滑动模式串，以尽可能地跳过不符合条件的情况。

BM算法相对于KMP算法的优点是更适合处理大量字符集的情况，并且在某些情况下能够比KMP算法更快地匹配。

BM算法也被广泛地应用在文本搜索和文件压
缩等领域。

两种算法各有优劣，可以针对不同的应用场景选择不同的算法来实现字符串匹配。

在实际使用中，如果主串和模式串的长度都比较小，那么KMP算法相对来说比较简单实用，而如果主串或模式串的长度非常长或者字符集非常大，那么BM算法的效率可能更高，可以采用BM 算法来实现字符串匹配。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

函数：int* MakeSkip(char *, int)
目的：根据坏字符规则做预处理，建立一张坏字符表
参数：
ptrn =>模式串P
PLen =>模式串P长度
返回：
int* -坏字符表
****************************************************************/
目的：根据好后缀规则做预处理，建立一张好后缀表
参数：
ptrn =>模式串P
PLen =>模式串P长度
返回：
int* -好后缀表
****************************************************************/
int* MakeShift(char* ptrn,int pLen)
shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}
int main(int argc, char* argv[])
{
//char test[] = "\0\0\0\0\0\0\0\0\0CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA \0\0";
//char find[] = "CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\0\0";
/*PS:在这里我要声明一句，*sptr =（shift + pLen - sptr）+ p2 - p3;
大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的。因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里*sptr保存的内容，实际是指标要移动距离，而不是字符串移动的距离。我想SNORT是出于性能上的考虑，才这么做的。*/
2）d2:后缀u不出现在p中的任何其他位置。但u的后缀v可能是模式串p的一个前缀，需要对模式串所有的后缀计算第二个函数d2。对于P的每个后缀u,d2(u)表示既是P的前缀，同时也是u的后缀的最长字符串v的长度.
3）d3:在搜索窗口中从后向前搜索时，在文本字符σ处不能成功匹配。保证下一次验证时文本字符σ一定与模式串中的一个字符σ相对应（即：使上次匹配不成功的那个字符能在模式串的第二个X部分匹配成功，在模式串中找到这个字符，该字符是X的前面一个字符），对每个字母表中的每个字符σ，d3(σ)表示σ在模式串的最右出现位置到模式串末尾的距离，如果σ不在P中，d3为m
int* makeskip(char *ptrn, int pLen)
{
int i;
//为建立坏字符表，申请256个int的空间
/*PS:要申请256个空间胡原因，是因为一个字符是8位，所以字符可能有2的8次方即256种不同情况*/
int *skip = (int*)malloc(256*sizeof(int));
if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}
//初始化坏字符表，256个单元全部初始化为pLen
for(i = 0; i < 256; i++)
*(skip+i) = pLen;
//给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋值了
while (pLen != 0)
*(skip+(unsigned char)*ptrn++) = pLen--;
return skip;
}
/****************************************************************
函数：int* MakeShift(char *, int)
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
return 1;
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
p2 = ptrn + pLen - 2;
p3 பைடு நூலகம் p1;
while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环，判断在边界内字符匹配到了什么位置
}while(p3 >= ptrn && p2 >= pptr);
*sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中，以pptr所在字符为边界时，要移动的位置
1）d1:后缀u在模式串p中的另一个位置是最右出现位置是j（不包括在模式串尾的出现）,文本串的窗口安全移动方法是将窗口移动m-j字符，使文本中的u与模式串中最右边的u的出现位置相对齐。对模式中的每个后缀，计算它到它的下一个出现之间的距离，即shift的d1，如果P的后缀u不在P中重复出现，则d1(u)被置为模式串长度m
pptr--;//边界继续向前移动
}
return shift;
}
/****************************************************************
函数：int* BMSearch(char *, int , char *, int, int *, int *)
3、窗口安全移动是指窗口移动意味着读入新的字符，放弃上一个窗口的前面几个字符，要保证放弃的字符确实无法参与匹配。窗口移动方向是从前向后。算法的核心思想是对于模式串，可能至少有2个相同部分，这些部分肯定有一个在模式串的后缀，其它的部分可能在模式串的中间，也可能在模式串的前缀，在后缀搜索时，发现了文本串和模式串的部分匹配X，此时，如果模式串除了后缀外，其它部分还含有X，则使文本串和模式中发生不匹配的读入的字符加上原来的匹配的X形成的部分有可能与模式串其它部分的X发生匹配（如果与模式串所有的X不匹配，则说明这个窗口内不可能发生匹配），安全地向后移动窗口，放弃的部分肯定不会发生匹配了。
移动后如下图：
自此，两个规则讲解完毕。
在BM算法匹配的过程中，取SKip(x)与Shift(j)中的较大者作为跳跃的距离。
BM算法预处理时间复杂度为O（m+s），空间复杂度为O(s)，s是与P, T相关的有限字符集长度，搜索阶段时间复杂度为O(m·n)。
最好情况下的时间复杂度为O(n/m)，最坏情况下时间复杂度为O(m·n)。
BM模式匹配算法-实现C 语言代码
下面是SNORT中提取出的代码。
#include<iostream>
using namespace std;
//#define u_char unsigned char
/* ****************************************************************
4、读入文本字符串u并在字符σ上不匹配时，进行如下几次比较：
1）第一次：取d1(u)和d3(σ)中较大值。
2）第二次:以上面的比较结果与m-d2(u)中的较小者，因为后者是最大的安全移动距离。
5、如果抵达了窗口的起始位置，说明发现阶段一个成功匹配，用d2计算窗口的下一次移动距离，进行继续匹配。
BM算法的基本流程图解
ii.如果x在模式P中出现，则以该字符进行对齐。
用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。
例1：
下图红色部分，发生了一次不匹配。
计算移动距离Skip(c) = 5 - 3 = 2，则P向右移动2位。
移动后如下图：
2）好后缀规则（Good Suffix）：
图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。
1）坏字符规则（Bad Character）：
在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：
i.如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//计算字符串是否匹配到了尽头
若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：
i.如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。
ii.如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。
BM算法概念
BM算法是一种精确字符串匹配算法（区别于模糊匹配）。

BM算法概念

合集下载

AC算法BM算法

BM算法详解

BM立体匹配算法的参数详解

BM算法-专业文档

BM算法讲解

BM算法详解

AC算法BM算法

第14讲--BM算法

字符串匹配算法

kmp算法bm算法

文档推荐

最新文档