近几天我看到了几个字符串快速匹配的算法,觉得很有意思,就拿来分享一下~

来自 Wikipedia:

在计算机科学里,Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小,但是通常仅为其它算法的一小部分:它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

既然说这个算法对字符串匹配速度快,那快在哪里呢?我们用个例子来了解一下:

首先我们有这样一串文本字符串(TEXT): 

s e a r e f g a b c s e a r c h t a a r c h e r

然后还有这样一串模式字符串(PATTERN):

s e a r c h

现在,我们需要在文本字符串中把模式字符串搜索出来,怎么做比较快呢?

Booyer 和 Moore 用他们的算法给了我们答案。我们来看看BM算法是怎么工作的:

 

最初的TEXT和PATTERN是这样的:

original

 

开始进行第一次比对(从后往前):

1

 

第一次比对时,"h"与"f"不匹配,"f"被称为“坏字符”(Bad Character),PATTERN将使用坏字符移位规则(Bad Character Shift)来进行移位操作。TEXT的下一个字符为"g",然而在PATTERN中并没有"g"这个字符。这时PATTERN直接将头"s"移至"g"的位置,开始进行第二次比对:

2

 

第二次比对,"h"和"e"不匹配,"e"是“坏字符”,PATTERN继续使用坏字符移位规则。TEXT中的下一个字符为"a",PATTERN中还有"a"字符。根据坏字符移位规则,PATTERN中的"a"字符将移到与TEXT中"a"字符相同的位置。然后继续进行第三次比对:

3

 

在第三次比对中,PATTERN中的字符"h"与TEXT中的字符"h"相匹配,于是我们将匹配框向前移动,看前面的字符是否匹配。很显然,在这里字符全部匹配,在TEXT中找到了PATTERN的字段(图中高亮的"search")。

4

 

在第四次比对中,我们可以使用一个新的规则——好后缀移位规则(Good Suffix Shift)。

但是,我们又会发现这里PATTERN的后缀"h","ch","rch","arch","earch"都没有在PATTERN中再次出现过,所以这里不存在好后缀(图中注明了Don't have good suffixs)。那么这里好后缀移位规则的移位位数是6位,就是PATTERN的长度。

进行移位操作后开始第五次比对:

5

 

第五次比对中,PATTERN中的字符"h"与TEXT中的字符"h"相匹配,继续使用好后缀移位规则。第六次比对:

6

 

在第六次比对中发现PATTERN中的"arch"后缀与TEXT中的"arch"相匹配。于是开始第七次匹配:

7

 

第七次比对中,我们发现了问题,PATTERN中的"e"与TEXT中的"a"不再匹配了。由于匹配了后缀"arch",我们使用好后缀移位规则。

但是,我们又发现这里PATTERN的后缀"h","ch","rch","arch"没有在PATTERN中再次出现过,所以这里同样也不存在好后缀(图中注明了Don't have good suffixs)。那么这里好后缀移位规则的移位位数是6位,就是PATTERN的长度。

移位后开始第八次比对:

8

 

第八次比对中发现TEXT字段已经结束,所有比对工作结束。

 

在这个例子中,我们一共在TEXT字段中搜索出了1个PATTERN字段,位置是TEXT中的第10位(从0开始记数)。

坏字符移位规则(Bad Character Shift)和好后缀移位规则(Good Suffix Shift)这两个移位规则是BM算法的核心。这两个规则使得BM算法能最大限度的减少比对次数,从而提高算法的效率。所以BM算法理论上是文本字符串(TEXT)越长,搜索效率提升越明显。

 

这篇文章旨在介绍BM算法的工作原理,有关BM算法的理论基础以及算法实现会在以后的文章中出现(这是坑……待填)。

    分享到:
分类: 算法 | Algorithm

发表评论

电子邮件地址不会被公开。 必填项已用*标注

验证码 *