标签归档:Boyer-Moore

Boyer-Moore 子字符串查找算法

前一篇博文中讨论了子字符串查找的问题,并给出了一个能高效地解决这个问题的算法:KMP 算法。我们知道,KMP 算法仅需在被查找字符串中顺序访问其中每个字符一次,便能找到其中匹配指定模式的子字符串。然而令人惊讶的事实是,KMP 并不是解决子字符串查找问题最快的算法,这意味着有时并不需要完整地扫描被查找字符串中的每一个字符便能完成子字符串查找。

Bob Boyer 和 J Strother Moore 在 1977 年设计了一个比 KMP 更快的字符串查找算法[1]。与 KMP 算法一样,这个算法也以设计者的名字命名,得名 Boyer-Moore 算法。Boyer-Moore 算法的主要思想是,在比对被查找字符串与模式中的字符时,启发式地跳过一些不事实上不需要比较的字符,大大减少了查找过程中比较的次数。更难得的是,Boyer-Moore 算法非常容易理解,实现也很简洁。

为了理解 Boyer-Moore 算法,先考察如下的例子:在字符串 S = “http://luodichen.com/blog/” 中查找模式 R = “luodichen”。像之前讨论过的暴力查找算法一样,先从被查找的字符串 0 索引处开始查找;但匹配字符的方向与暴力查找相反——自右向左匹配模式中的字符。如下图所示,在这个例子中当查找索引 i = 0 时,右边首先匹配的是被查找字符串中的字符 S[8] = ‘u’ 与 模式中的字符 R[8] = ‘n’,结果是这两个字符不相匹配。按照暴力查找的做法,当出现了不匹配的情况时,需要做的是将查找索引的值加 1,重新进行匹配,此时不妨也这样做,将查找索引 i 的值加 1,此时 i = 1。现在应该比较哪两个字符呢?比较 S[8] = ‘u’ 与 R[7] = ‘e’,同样不匹配,重复增加 i 的值,直到 i = 7 时,S[8] = ‘u’ 与 R[1] = ‘u’ 匹配。接着逐字向左匹配剩下的字符,最后会发现子字符串匹配成功了。

bm-ani1图 1  暴力算法的小改动——先匹配右边的字符

然而这并没有比暴力算法更快(与暴力算法一样慢)。仔细回想一下上面的操作,实质上是在不断增加查找索引 i 的同时检查 S[8] 与 R[8 – i] 是否匹配,换句话说,就是在 R 中自右向左寻找第一个字符 S[8]。如果在字符串查找开始之前就对模式 R 做一些处理,记住 R 中每一个字符自右向左第一次出现的位置(上例中 ‘u’ 第一次出现的位置是 R[1]),就可以在发生不匹配的情况时直接推算出 i 应当增加的数值,而不必每次只加 1 地尝试。如下图。

bm-ani2图 2 查表并推算出 i 需要增加的值,直接设置 i

以上的例子便是运用了 Boyer-Moore 算法的思想。将这个思路推广到一般情形,为了描述方便,先假设被查找的字符串为 S 假定 S 足够长,匹配模式为 R,R 的长度为 l;查找索引为 i,i 的初始值是 0;函数 m(c) 表示 R 中自右向左第一次出现字符 c 时 R 的索引,若 c 从未在 R 中出现过,返回 -1。Boyer-Moore 算法由以下几个步骤组成:

  1. 找到模式 R 最右匹配的字符 S[i + l – 1] 与 R[l – 1];
  2. 如果匹配,则继续向左检查,直到找到 S[i + l – n] 与 R[l – n] 不匹配或全部字符都匹配成功;
  3. 如果全部字符匹配成功,则子字符串查找到一个结果;否则调用 j = m(S[i + l – n]),得到 j 表示 S 中不匹配的那个字符在 R 中自右向左第一次出现的索引,然后查找索引向右移动 (l – j – 1),重复步骤 1。

Boyer-Moore 算法在应用中通常能跳过大部分字符,因此具有非常快的速度。并且模式相对越长,查找速度越快。以下的图片演示了 Boyer-Moore 算法的一个经典示例:在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”。

bm-ani3图 3 在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”

本文所提到的所有算法均以 Java 实现,代码托管于 GitHub,查看

(允许转载文本,转载请注明出处:http://luodichen.com/blog/?p=298

参考文献
[1] Wikipedia. Boyer-Moore字符串搜索算法[EB/OL]. http://zh.wikipedia.org/wiki/Boyer-Moore%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95.