字符串匹配算法（二）BM

本文介绍另一款字符串匹配算法，BM算法，此种算法的优化点在于，pattern 的往后位移量，更大步，而且，原文越大，该算法的优势越明显，因为 BM 算法的瓶颈在于对 pattern 的初始化。

一、简介

上文中我们介绍了一款字符串匹配的算法，此文会介绍另一款更高效的算法，据称会教KMP算法而言，效率提高了3~5倍。

该算法由 Bob Boyer 和J Strother Moore 共同创建，故称为 Boyer-Moore 字符串搜索算法，简称 BM 算法。

我们在文本文档编辑的时候，常用的搜索功能（Ctrl + F），底层算法其实就是该 BM 算法。

</p>

二、名词定义

以下摘自 wikipedia

被检索的字符，也就是原文，称为 text，用符号 T 表示
检索的字符串，也就是你需要搜索的字符串，称为模式串，也称为 pattern，用符号 P 表示
P 的长度记为 n
T 的长度记为 m
S[i] 为字符串 S 从1开始计数的第 i 个字符
S[i..j] 为字符串 S 的一个子串，始于i，终于j
S 的前缀定义为 S[1..i]，其中 i 小于S 的长度
S 的后缀定义为 S[i..n]，其中n 为 S 的长度
k 表示字符串P 的最后一位在 T 中的位置
当发生匹配时，P 在 T 中的位置记为 T[(k-n+1)..k]
坏字符：T 和 P 中不匹配的字符（下文的案例中会详细介绍）
好后缀：T 和 P 中相匹配的后缀（下文的案例中会详细介绍）

三、原理简析

下面以图示的方式，来简单阐述 BM 算法的匹配步骤。

首先，相较于朴素的算法，朴素算法是从 P 的首字符开始匹配，直至出现不一致，然后再将 P 后移一定的位数。而 BM 算法的变通之处主要出现在两点上：

①BM 算法从 P 的末字符开始，依次往前进行匹配，直至出现不一致；

②此时 P 需要右移，那么右移多少位呢？该位数由两个子算法共同构成，即坏字符算法和好后缀算法，两者分别进行计算右移的位数，谁算得的右移位数多，最终 P 右移的位数便会采用。

其实，坏字符和好后缀计算的右移位数的计算，都是查询相应的表而得到的，而这两张表，就是 BM 的核心，即，该算法需要对 P 进行预处理，从而得出这两张表。

四、简明图示案例

BM 算法核心：找到一个后缀，让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐。

案例一：T 为 0123456789 ， P为 MOORE

常规的匹配是先将0和M开始匹配，不一样，然后后移一位，再将1和M进行匹配，依次类推，总共需要匹配10次，或者先进一点，需要匹配6次，

而我们的 BM 算法，如果利用坏字符规则，则只需要匹配两次：

第一次直接将4和E进行匹配，出现不一致，此时我们需要将P后移，此时的4即为坏字符，那么后移多少位呢？此处根据核心：找到一个后缀，让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐，而此处，由于已匹配过的后缀是4，但是这个4并没有出现在P中，所以将整个P往后移，直至P的首字符M位于4的后面，即将P往后移动5个字符，也就是往后移P的长度个字符。

另外，坏字符移动规则公式为：后移位数 = 坏字符位数 - 坏字符在P中上次出现的位置

而此处：后移位数 = 5 - 0 = 5，所以后移5位

第二次匹配的话，同理。所以，最后仅仅匹配了2次便查找完毕了，效率很高。

上述案例的运行模式可以见下图：

案例二：T为 HERE IS A SIMPLE EXAMPLE ， P为 EXAMPLE

这个案例取自 BM 算法的创始人之一 Moore 教授自己言传身教的例子。

先来说说什么是好后缀以及好后缀的一些移动规则：

T 和 P 进行匹配的时候，从P 的尾部开始，匹配出的相同的字符串（包括单个字符）即为好后缀，

如 ABCDAB 和 BACD，首次匹配时，首字符对齐，从尾开始匹配，发现有相同的字符串 “CD”，此时的好后缀有 “CD”和“D”，

知道了好后缀的定义，那么根据好后缀计算而得的右移位数的计算方式呢？ 右移位数 = 好后缀的位置 - 好后缀在模式串P中上一次出现的位置。

此处需要注意三点：

① 好后缀的位置，以好后缀的最后一个字符为准，即假设“BACD”的 CD 是好后缀，则好后缀的位置以“D”为准，即4（从1开始计算）；

② 如果好后缀在模式串中只出现过一次，比如：假设“BACD”的 CD 是好后缀，而 CD 仅出现了一次，则上一次出现的位置记做 0（即未出现过）；

③ 如果好后缀有多个，计算上次出现位置时，此时除了最长的那个好后缀，其余的好后缀上次出现的位置必须是在头部（即起始位置）。比如：假设“DCDBACD”的好后缀为 ACD，同样，好后缀还有 CD，D，总共三个好后缀，我们依次来计算上次出现的位置，“ACD”仅出现一次，为0，当没有其它有效的好后缀的时候，便用这个；“CD”上次出现位置不在头部，不计算；“D”这个字符正好和头部相同，故“D”的上次出现位置为1，所以好后缀在模式串P中上一次出现的位置为1。

说完了规则，那么我们正式看案例，见下图：

原理讲明白了，那么我们就该搞清楚其中最为核心的《坏字符规则表》和《好后缀规则表》的生成原理了。

五、代码实现

public&nbsp;static&nbsp;void&nbsp;boyerMoore(String&nbsp;pattern,&nbsp;String&nbsp;text)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m&nbsp;=&nbsp;pattern.length();
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;text.length();
&nbsp;&nbsp;&nbsp;&nbsp;Map<String,&nbsp;Integer>&nbsp;bmBc&nbsp;=&nbsp;new&nbsp;HashMap<>();
&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;bmGs&nbsp;=&nbsp;new&nbsp;int[m];
&nbsp;&nbsp;&nbsp;&nbsp;//初始化
&nbsp;&nbsp;&nbsp;&nbsp;preBmBc(pattern,&nbsp;m,&nbsp;bmBc);
&nbsp;&nbsp;&nbsp;&nbsp;preBmGs(pattern,&nbsp;m,&nbsp;bmGs);
&nbsp;&nbsp;&nbsp;&nbsp;//开始匹配
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;j&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(j&nbsp;<=&nbsp;n&nbsp;-&nbsp;m)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;m&nbsp;-&nbsp;1;&nbsp;i&nbsp;>=&nbsp;0&nbsp;&&&nbsp;pattern.charAt(i)&nbsp;==&nbsp;text.charAt(i&nbsp;+&nbsp;j);&nbsp;i--)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//用于计数
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count++;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(i&nbsp;<&nbsp;0)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println("one&nbsp;position&nbsp;is:"&nbsp;+&nbsp;j);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;+=&nbsp;bmGs[0];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;+=&nbsp;Math.max(bmGs[i],&nbsp;getBmBc(String.valueOf(text.charAt(i&nbsp;+&nbsp;j)),&nbsp;bmBc,&nbsp;m)&nbsp;-&nbsp;m&nbsp;+&nbsp;1&nbsp;+&nbsp;i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;System.out.println("count:"&nbsp;+&nbsp;count);
}
/**
&nbsp;*&nbsp;坏字符初始化
&nbsp;*/
private&nbsp;static&nbsp;void&nbsp;preBmBc(String&nbsp;pattern,&nbsp;int&nbsp;patLength,&nbsp;Map<String,&nbsp;Integer>&nbsp;bmBc)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;System.out.println("bmbc&nbsp;start&nbsp;process...");
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;patLength&nbsp;-&nbsp;2;&nbsp;i&nbsp;>=&nbsp;0;&nbsp;i--)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!bmBc.containsKey(String.valueOf(pattern.charAt(i))))&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bmBc.put(String.valueOf(pattern.charAt(i)),&nbsp;patLength&nbsp;-&nbsp;i&nbsp;-&nbsp;1);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
}
/**
&nbsp;*&nbsp;好后缀初始化
&nbsp;*/
private&nbsp;static&nbsp;void&nbsp;preBmGs(String&nbsp;pattern,&nbsp;int&nbsp;patLength,&nbsp;int[]&nbsp;bmGs)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;j;
&nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;suffix&nbsp;=&nbsp;new&nbsp;int[patLength];
&nbsp;&nbsp;&nbsp;&nbsp;suffix(pattern,&nbsp;patLength,&nbsp;suffix);
&nbsp;&nbsp;&nbsp;&nbsp;//模式串中没有子串匹配上好后缀，也找不到一个最大前缀
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;patLength;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bmGs[i]&nbsp;=&nbsp;patLength;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;//模式串中没有子串匹配上好后缀，但找到一个最大前缀
&nbsp;&nbsp;&nbsp;&nbsp;j&nbsp;=&nbsp;0;
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;patLength&nbsp;-&nbsp;1;&nbsp;i&nbsp;>=&nbsp;0;&nbsp;i--)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(suffix[i]&nbsp;==&nbsp;i&nbsp;+&nbsp;1)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(;&nbsp;j&nbsp;<&nbsp;patLength&nbsp;-&nbsp;1&nbsp;-&nbsp;i;&nbsp;j++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(bmGs[j]&nbsp;==&nbsp;patLength)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bmGs[j]&nbsp;=&nbsp;patLength&nbsp;-&nbsp;1&nbsp;-&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;//模式串中有子串匹配上好后缀
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;patLength&nbsp;-&nbsp;1;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bmGs[patLength&nbsp;-&nbsp;1&nbsp;-&nbsp;suffix[i]]&nbsp;=&nbsp;patLength&nbsp;-&nbsp;1&nbsp;-&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;System.out.print("bmGs:");
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;patLength;&nbsp;i++)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.print(bmGs[i]&nbsp;+&nbsp;",");
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;System.out.println();
}
private&nbsp;static&nbsp;void&nbsp;suffix(String&nbsp;pattern,&nbsp;int&nbsp;patLength,&nbsp;int[]&nbsp;suffix)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;suffix[patLength&nbsp;-&nbsp;1]&nbsp;=&nbsp;patLength;
&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;q;
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;patLength&nbsp;-&nbsp;2;&nbsp;i&nbsp;>=&nbsp;0;&nbsp;i--)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(q&nbsp;>=&nbsp;0&nbsp;&&&nbsp;pattern.charAt(q)&nbsp;==&nbsp;pattern.charAt(patLength&nbsp;-&nbsp;1&nbsp;-&nbsp;i&nbsp;+&nbsp;q))&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q--;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;suffix[i]&nbsp;=&nbsp;i&nbsp;-&nbsp;q;
&nbsp;&nbsp;&nbsp;&nbsp;}
}
private&nbsp;static&nbsp;int&nbsp;getBmBc(String&nbsp;c,&nbsp;Map<String,&nbsp;Integer>&nbsp;bmBc,&nbsp;int&nbsp;m)&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;//如果在规则中则返回相应的值，否则返回pattern的长度
&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;bmBc.getOrDefault(c,&nbsp;m);
}

六、资料

1、源码地址：传送门

2、有一篇文章可以参考，很不错，传送门