Boyer Moore算法怎么用

共计 3349 个字符，预计需要花费 9 分钟才能阅读完成。

Boyer Moore 算法怎么用，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

简介

对于字符串的搜索算法，我曾经讨论过 KMP 算法的思路和实现。KMP 算法的实现思路是基于模式串里面的的前缀和后缀匹配，这种算法的效率已经足够快了。没想到的是，这里我们要讨论的 Boyer Moore 算法效率更加惊人。

思路分析

在之前的算法里，我们是通过从模式串的开头到结尾这么一个个的去和目标串比较，这种方式在碰到匹配的元素时则继续比较下一个，在没有匹配的时候，则通过查找模式表构建的匹配表来选择模式串里后面的第几个元素来继续进行比较。这样目标串里的索引就不用往回挪。但是，这里比较的顺序恰好相反。假设目标串长度为 n, 模式串长度为 m。那么，首先我们就从两个串的 m – 1 索引位置开始比较，如果相同，则一直向前，如果不同，则需要根据这个不同的字符的情况来判断。

根据比较字符的不同，我们可能有两种情况，一种是这个不同的字符不在模式串里。那么很显然，模式串里任何一个字符都不可能和它匹配的，我们只需要跳到这个字符的后面那个位置开始继续比较就可以了。还有一种情况就是这个字符是在模式串里的，那么，我们就需要找到和这个字符匹配的最后一个出现在模式串里的字符。这样，我们可以在模式串中从最后匹配的位置开始继续往后比较。

前面的这部分描述显得比较抽象，我们可以结合一个具体的示例来讨论。假设我们有字符串 s 和 p，s 的值为：FINDINAHAYSTACKNEEDLEINA, p 的值为: NEEDLE。我们分别用 i, j 来表示 s, p 当前的位置。那么，他们比较的过程如下图：

结合上图来说，他们最开始比较的位置是从索引 5 开始。这个时候 s 在这个位置的元素是 N，而 p 在这个位置的字符是 E。那么他们并不匹配。我们就需要跳到后面进行比较。而这个字符 N 在 p 里面是存在的，对应 p 里最后出现 N 的位置就是索引 0。所以我们就从 N 的这个位置开始到 p 最末尾的位置作为比较的点，又从 p 的末尾和对应的 s 的位置进行比较。这个时候 i 的索引位置为 10 的时候它和 p 最末尾的字符 E 并不匹配，而且这个字符是 S，在 p 串里也找不到对应的字符。那么这时候，我们就需要从 S 后面的元素开始和 p 的第一个元素对齐，然后我们再从 p 的最后一个元素以及 s 串的索引 i + j 进行比较。这时候一直比较到开头，发现有匹配的串。于是返回 i = 15。

概括

经过上述的讨论，我们发现，要实现这个算法需要考虑的就是怎么用一种比较简单的方法将字符串的匹配和不匹配场景给统一起来。这样在每次比较到匹配或者不匹配的时候能够对应的调整。对于前面的场景我们来仔细看一下。

当比较的字符和当前 p 模式串里的字符不匹配时，如果这个不匹配的字符也不在模式串里，那么这种情形的调整如下图：

因为这种情况下，无论取模式串里的那个元素都不可能和这个元素匹配的，所以相当于要将整个模式串挪到这个元素的后面的那个位置对齐再来比较。这个时候，相当于将 j 重置到 m – 1 的值，而这个时候 i 的值也调整到 i + j + 1。

还有一种情况就是这个当前不匹配的字符在模式串里，如下图：

在这个示例里，因为不匹配的字符是 N，但是 N 存在于模式串中。所以我们需要将 i 所在的位置移动到这个不匹配元素的位置。而这个时候模式串里的位置是 j，如果我们可以找到 N 所在的索引位置，就可以通过 j – right[N] 来实现了。

所以总的来说，我们在比较的时候对于目标串的索引 i 和模式串的索引 j 来说，它们比较和调整顺序正好相反。i 是逐步递增的调整，而 j 是递减的进行比较。当 s.charAt(i + j) == p.charAt(j) 的时候，表示它们匹配。所以这时候继续进行个 j – 这个操作进行下一步比较就可以。而 s.charAt(i + j) != p.charAt(j) 的时候，就要调整了。根据前面的讨论，如果 s.charAt(i + j) 不存在于 p 中间，这个时候，我们需要将 i 往右移动 j + 1 个位置。按照前面讨论的，也就是 j – right[s.charAt(i + j)]。这也说明了 right[s.charAt(i + j)] 为 -1。

而如果 s.charAt(i + j) 存在于模式串中，那么我们需要找到这个字符在模式串中间的位置，我们需要移动的距离就是从 j 到这个字符的距离。如果用 j – right[s.charAt(i + j)]，那么这里 right[s.charAt(i + j)] 记录的应该就是字符 s.charAt(i + j) 在模式串中的位置。

这样，我们将 right[] 数组记录的值统一起来了。问题的核心就归结为怎么计算 right 数组。

计算 right

计算 right 数组的过程比较简单，因为只要记录每个字符在模式串里最后出现的位置就可以了。对于不在模式串里的元素呢，只要设置为 - 1 就可以了。所以我们可以用如下一段代码实现：

right = new int[r]; 

for(int c = 0; c   r; c++) 

 right[c] = -1; 

for(int j = 0; j   m; j++) 

 right[pat.charAt(j)] = j;  

最终实现

剩下的就是将整个实现给连贯起来。建立好 right 数组之后，剩下的就是从目标串 i 开始，每次比较 s[i + j] 和 p[j] 的位置。如果相等，就继续比较，直到 j == 0。如果不等，则计算 i 后面要移动的距离 skip，其中 skip = j – right[s[i + j]]。这样，详细的实现如下：

public class BoyerMoore { 

 private int[] right; 

 private String pat; 

 public BoyerMoore(String pat) { 

 this.pat = pat; 

 int m = pat.length(); 

 int r = 256; 

 right = new int[r]; 

 for(int c = 0; c   r; c++) 

 right[c] = -1; 

 for(int j = 0; j   m; j++) 

 right[pat.charAt(j)] = j; 

 } 

 public int search(String txt) { 

 int n = txt.length(); 

 int m = pat.length(); 

 int skip; 

 for(int i = 0; i  = n – m; i+= skip) { 

 skip = 0; 

 for(int j = m – 1; j  = 0; j–) { 

 if(pat.charAt(j) != txt.charAt(i + j)) { 

 skip = j – right[txt.charAt(i + j)]; 

 if(skip   1) skip = 1; 

 break; 

 } 

 } 

 if(skip == 0) return i; 

 } 

 return -1; 

 } 

}  

在上述的代码实现里，还有一个值得注意的小细节，就是计算出 skip 之后，要判断 skip 是否小于 1。因为有可能碰到的当前不匹配字符是存在于模式串里，但是它最后出现的位置要大于当前的值 j 了。这时候，我们要保证 i 最少要移动一位。所以这里要设置为 1。 

还有一个需要注意的地方就是，因为要考虑到为每个字符建立它的映射关系，所以我们需要建立一个有字符集长度那么长的 right 数组。在字符集太大的情况下，它占用的空间会比较多。这里只是针对理想的 256 个字符的情况建立的 right 表。

从该算法的性能来说，它在理想的情况下的时间复杂度为 O(M/N) 其中 M 是目标串的长度，而 N 是模式串的长度。

Boyer Moore 算法是一个在实际中应用比较广泛的算法，它的速度更加快。和其他的字符串匹配方法比起来，它采用从后面往前的比较方式。同时通过建立一个字符映射表来保存字符在当前模式串里的位置，以方便每次比较的时候源串的位置调整。它最大的特点就是不再是一个个字符的移动，而是根据计算一次跳过若干个字符。这样总体的性能比较理想。

看完上述内容，你们掌握 Boyer Moore 算法怎么用的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注丸趣 TV 行业资讯频道，感谢各位的阅读！