字符串匹配的Boyer-Moore算法

作者: 阮一峰

日期: 2013年5月 3日

上一篇文章,我介绍了KMP算法

但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的"查找"功能(Ctrl+F),大多采用Boyer-Moore算法

Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。

下面,我根据Moore教授自己的例子来解释这种算法。

1.

假定字符串为"HERE IS A SIMPLE EXAMPLE",搜索词为"EXAMPLE"。

2.

首先,"字符串"与"搜索词"头部对齐,从尾部开始比较。

这是一个很聪明的想法,因为如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

我们看到,"S"与"E"不匹配。这时,"S"就被称为"坏字符"(bad character),即不匹配的字符。我们还发现,"S"不包含在搜索词"EXAMPLE"之中,这意味着可以把搜索词直接移到"S"的后一位。

3.

依然从尾部开始比较,发现"P"与"E"不匹配,所以"P"是"坏字符"。但是,"P"包含在搜索词"EXAMPLE"之中。所以,将搜索词后移两位,两个"P"对齐。

4.

我们由此总结出"坏字符规则"

  后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

如果"坏字符"不包含在搜索词之中,则上一次出现位置为 -1。

以"P"为例,它作为"坏字符",出现在搜索词的第6位(从0开始编号),在搜索词中的上一次出现位置为4,所以后移 6 - 4 = 2位。再以前面第二步的"S"为例,它出现在第6位,上一次出现位置是 -1(即未出现),则整个搜索词后移 6 - (-1) = 7位。

5.

依然从尾部开始比较,"E"与"E"匹配。

6.

比较前面一位,"LE"与"LE"匹配。

7.

比较前面一位,"PLE"与"PLE"匹配。

8.

比较前面一位,"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"(good suffix),即所有尾部匹配的字符串。注意,"MPLE"、"PLE"、"LE"、"E"都是好后缀。

9.

比较前一位,发现"I"与"A"不匹配。所以,"I"是"坏字符"。

10.

根据"坏字符规则",此时搜索词应该后移 2 - (-1)= 3 位。问题是,此时有没有更好的移法?

11.

我们知道,此时存在"好后缀"。所以,可以采用"好后缀规则"

  后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

举例来说,如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5(从0开始计算,取最后的"B"的值),在"搜索词中的上一次出现位置"是1(第一个"B"的位置),所以后移 5 - 1 = 4位,前一个"AB"移到后一个"AB"的位置。

再举一个例子,如果字符串"ABCDEF"的"EF"是好后缀,则"EF"的位置是5 ,上一次出现的位置是 -1(即未出现),所以后移 5 - (-1) = 6位,即整个字符串移到"F"的后一位。

这个规则有三个注意点:

  (1)"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。

  (2)如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1。比如,"EF"在"ABCDEF"之中只出现一次,则它的上一次出现位置为-1(即未出现)。

  (3)如果"好后缀"有多个,则除了最长的那个"好后缀",其他"好后缀"的上一次出现位置必须在头部。比如,假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B",请问这时"好后缀"的上一次出现位置是什么?回答是,此时采用的好后缀是"B",它的上一次出现位置是头部,即第0位。这个规则也可以这样表达:如果最长的那个"好后缀"只出现一次,则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB",即虚拟加入最前面的"DA"。

回到上文的这个例子。此时,所有的"好后缀"(MPLE、PLE、LE、E)之中,只有"E"在"EXAMPLE"还出现在头部,所以后移 6 - 0 = 6位。

12.

可以看到,"坏字符规则"只能移3位,"好后缀规则"可以移6位。所以,Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。

更巧妙的是,这两个规则的移动位数,只与搜索词有关,与原字符串无关。因此,可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时,只要查表比较一下就可以了。

13.

继续从尾部开始比较,"P"与"E"不匹配,因此"P"是"坏字符"。根据"坏字符规则",后移 6 - 4 = 2位。

14.

从尾部开始逐位比较,发现全部匹配,于是搜索结束。如果还要继续查找(即找出全部匹配),则根据"好后缀规则",后移 6 - 0 = 6位,即头部的"E"移到尾部的"E"的位置。

(完)

珠峰培训

简寻

留言(57条)

本科的时候看算法课本就这里不明白,现在终于弄懂了。

太赞了,看了上一篇意犹未尽。

通俗易懂的解释,如果教科书能按照这样编写,计算机会更有趣一些。

受教了,阮兄每篇都很值得我輩細讀。

我也受教了,不过我想知道下面两处的来源:

1.文本编辑器的"查找"功能大多采用Boyer-Moore算法。

2.Boyer-Moore算法效率高于KMP。(KMP的时间复杂度是 O(n + k),但是Boyer-Moore是多少呢?)

阮兄,

后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
计算时,位置的取值以"好后缀"的最后一个字符为准。

这里 "好后缀"的最后一个字符 不就只会是搜索词的最后一个字符吗?也就是说公式里的 好后缀的位置 就是 搜索词的长度-1(因为从0开始编号) 吧?

“好后缀的位置”和“搜索词中的上一次出现位置”这两个我总是会弄混。。。

引用funnyfan的发言:

“好后缀的位置”和“搜索词中的上一次出现位置”这两个我总是会弄混。。。

“搜索词中的上一次出现位置”这个博主没解释清楚

引用t.k.的发言:

我想知道下面两处的来源:

……

可以参见这个链接

引用HCocoa的发言:

“搜索词中的上一次出现位置”这个博主没解释清楚

我加了两个例子,是不是好一点了?

学习了,想到一个问题,如果从后面往前找这个算法该如何实现呢,规则还一样吗?

有效Boyer-Moore algorithm實現的難點在于好後綴的計算,樸素的方法時間復雜度是O(m^2)的,O(m)的計算還需要用到Manacher algorithm。

另外,请教阮老师,贵博客的留言系统是自己做的定制开发还是用了哪个第三方的系统?感觉交互上比市面上常见的友言要好。多谢指导;)

确实相当的巧妙!

此时,所有的"好后缀"(MPLE、PLE、LE、E)之中,只有"E"在"EXAMPLE"之中出现两次,所以后移 6 - 0 = 6位。

所以个啥?

觉得英文版更清楚

要是在来一篇字符串模糊匹配算法就好了~

看得感觉还不是特别懂..................

说一下 "3."这张图的到"4."这一步计算我的理解

以"3."为例


坏位置为重"example"对应的长字符串从后面开始查找,与上面位置对应不匹配的字第一次出现的位置.

比如图"3."以为例,经过前面的位移后,"example"的最后一位"e"对应长字符串的"p";

因为p != e;所以:

坏位置 = "example"中"e"的位置(也就是6)

但是p在"example",所以:

搜索词中的上一次出现位置 = p在"example"中的位置(也就是4)


不知道我的理解是否正确?

同求:字符串模糊匹配算法

看了楼主两篇文章受益匪浅,,之前看了好多关于KMP与BM的文章和书都是一知半解,楼主解释的很清晰,,不知啥时候写下KMP和BM的实现,,网上许多写的都乱七八糟的

阮老师写的真好。
看的过程中只有一点迷糊了下:所有的"好后缀"(MPLE、PLE、LE、E)之中,是先选最长的“好后缀”MPlE,去找它在"搜索词中的上一次出现位置",没有才选短一点的PLE,以此类推,直到最短的好后缀?是这样吧?

@hancy:

对,就是这样。

因为“好后缀规则”比较麻烦,有些实现就只部署“坏字符规则”。

这个算法设计比较精巧。
看阮兄的一系列文章,收益匪浅,尤其是《TF-IDF与余弦相似性的应用》系列,让大家明白其实算法和实际应用结合后,并不是那么的令人生畏。

关于坏字符的上一次位置,可能让人不理解。
上一次位置:如果有多个坏字符,指搜索词的最后一个坏字符的位置。这样是不是好点?

关于好后缀,如果有多个好后缀,则选择位于搜索词的头部,即第0位的那个,否则就是-1,我是这样理解的。
“除了最长的那个"好后缀"”,这句有点不理解。

这个怎么和linuxeden开源社区新浪微博上的文章是一样的。

也是关于“上一次出现位置”。我想可不可以当作“最后一次出现位置”?
以“坏字符”为例,就是在搜索词里从后往前找到的第一个“坏字符”的位置。这在搜索词中包含多个“坏字符”时,能够保证不会后移太多。

坏字符规则表和《好后缀规则表怎么生成?
它们都要根据字符在搜索词中出现的位置,怎么说和原字符(被搜索词?)无关?

引用navono的发言:

坏字符规则表和《好后缀规则表怎么生成?
它们都要根据字符在搜索词中出现的位置,怎么说和原字符(被搜索词?)无关?

明白了。

坏字符规则中如何算出后移的位数呢?我在开源中国博客(http://www.oschina.net/question/12_23429)中看到了计算坏字符移动数组BmBc的方法:
"BmBc数组的定义,分两种情况。

1、 字符在模式串中有出现。如下图,BmBc[‘k’]表示字符k在模式串中最后一次出现的位置,距离模式串串尾的长度。

我对这个也有疑惑:情况1中为什么BmBc[‘k’]是表示字符k在模式串中最后一次出现的位置,距离模式串串尾的长度。如果有多个k出现呢?

假设:

T:abcdbccg

P: abcdbecg

现在c和e不匹配,按照你的上面的方法计算的BmBc[‘c’]等于1,显然不对啊!

引用花生的发言:

关于坏字符的上一次位置,可能让人不理解。
上一次位置:如果有多个坏字符,指搜索词的最后一个坏字符的位置。这样是不是好点?

我觉得定义靠谱点,开源中国这篇将BM的代码你看了没,我觉得计算坏字符的上一次位置数组的代码有问题(如果这个字符重复多次的话,它取的是最靠右的那个位置的)。

引用t.k.的发言:

Boyer-Moore算法效率高于KMP。(KMP的时间复杂度是 O(n + k),但是Boyer-Moore是多少呢?)

效率是o(N/M)

这个bm算法的好后缀部分和kmp算法的前缀函数一模一样吧?
猜测:bm算法是在kmp算法基础上发展的,而且效率略高。

阮老师 太厉害了, 新的偶像诞生了!

有个地方想的不是很明白
12 里面说,“ Boyer-Moore算法的基本思想是,每次后移这两个规则之中的较大值。”
您能举个例子说明一下“坏字符规则”移位更大的情况吗?

谢谢了

BM算法不是最高效的,还可以提升,关键是第二步,如果是坏字符,BM算法是从下一个字母开始,如果是个好后缀,则要做适当的平移。实际无论是否是好后缀还是坏后缀,下一个字符都得参与下一次匹配,所以可以从下一个字符开始匹配,本例中下一个字符是个空格,显然是个坏字符,则第二次从字符A开始,最后一位不匹配,再看下一个字母E,则做平移,以此类推。显然会比BM算法更高效。

得把“好后缀”和“上一次出现位置”的定义说明白吧,阮大

引用freeboy1015的发言:

坏字符规则中如何算出后移的位数呢?我在开源中国博客(http://www.oschina.net/question/12_23429)中看到了计算坏字符移动数组BmBc的方法:
"BmBc数组的定义,分两种情况。

1、 字符在模式串中有出现。如下图,BmBc[‘k’]表示字符k在模式串中最后一次出现的位置,距离模式串串尾的长度。

我对这个也有疑惑:情况1中为什么BmBc[‘k’]是表示字符k在模式串中最后一次出现的位置,距离模式串串尾的长度。如果有多个k出现呢?

假设:

T:abcdbccg

P: abcdbecg

现在c和e不匹配,按照你的上面的方法计算的BmBc[‘c’]等于1,显然不对啊!

我想知道坏字符规则怎么预处理
我还看过是bmbc['k']取离结尾最长的,也就是第一个出现的
但不管哪种都不符合“上一次出现的位置”
也就是说 对于一个字符'k',bmbc['k']与它不匹配的位置也有关,那么一个一维数组就能解决这个问题么?

好后缀是不是有些问题。按照文中说法,好后缀的位置就是:
最后一个字符的位置-最后一个位置的字符在匹配字符中出现的位置。
比如匹配字符是 errtert,它的好后缀无论怎么样都是:6-3=3.

讲得真好,将整个算法的匹配思路讲得淋漓尽致,谢谢~

认真看了两遍,才算是领悟到了要领。楼主解释清晰透彻!

讲的很赞哦,最常用的东西,还有这么多奥妙

很赞,不知楼主能否写一篇sunday算法

引用花生的发言:

关于坏字符的上一次位置,可能让人不理解。
上一次位置:如果有多个坏字符,指搜索词的最后一个坏字符的位置。这样是不是好点?

怎么会有多个坏字符呢,你说的是不是好字符?比如ABCCCCDAB,那么好字符显然应该是AB而不是你说的最后一个B,我觉得博主讲的在前面补全的方法很好。

好后缀这个地方有点没看懂。

如果好后缀不是一个字母,那么好后缀肯定不止一个对吧。

比如举例说的MPLE,好后缀有MPLE,PLE,LE,E。

但是取哪个后缀进行计算的时候没说清楚,我感觉。

是先看,次长后缀是不是出现在词头,没有,再看次之的,以此类推么????

如果,所有的好后缀都没有出现在词头,那怎么办???

求解释。。。这个地方没看太懂,不过还是谢谢了!

说的挺透彻的!

【(1)"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。】

那么无论是什么搜索词,好后缀的位置一定是(搜索词的长度-1)了?

不是"后移位数",而应该是“移后子首所在位置”

我觉得博主没有把这个算法的核心思想表达出来。其实根本就没有多个好后缀,只有一个好后缀,那就是已经匹配的那个后缀。

其实他和尝试寻找坏字符的在待查找词中最后出现位置的思想是一模一样的:坏字符在尝试寻找一个可以和他吻合的点,然后与其结合匹配,以此来为他的妈妈,即带查找词,重新定位一个可能的匹配位置。

而坏字符串(已经匹配的那一段)也是一样的,他们也在寻找一段和他们吻合的位置,以此来重新定位他妈的位置。根本没有多个而是虚拟的将它们往前移动而已。

这两者的本质思想都是用妈妈身体上已知的信息,来重新定位。其实是不是好后缀根本不重要,只要他们在妈妈身上已经有了信息(就像坏字符表一样)那么就可以利用已经知道的信息来探求适合的位置。

那为什么要用到好后缀呢。其实不是这样的,是因为只有好后缀的信息妈妈才知道,才能被利用。

没明白《坏字符规则表》和《好字符规则表》是怎么生成的,那些数字是怎么计算出来的?难道是一步步比较出来的??还是不会啊。。明晚就要考试了,,,可以马上回复我吗?谢谢啦。

通熟 易懂 !

引用花生的发言:

关于好后缀,如果有多个好后缀,则选择位于搜索词的头部,即第0位的那个,否则就是-1,我是这样理解的。
“除了最长的那个"好后缀"”,这句有点不理解。

请问这个理解了吗?我现在还不太理解

利用好后缀规则比较过之后应该先比较好后缀的前面还是后面呢

阮老师的博客通俗易懂而又不失深度,怒赞!

引用左德军的发言:

请问这个理解了吗?我现在还不太理解

引用左德军的发言:

请问这个理解了吗?我现在还不太理解

看图8,搜索词为"EXAMPLE",已经匹配的为:MPLE,那么好后缀为MPLE、PLE、LE、E,按以下步骤处理:
1)在搜索词"EXAMPLE"里从右往左寻找下一个MPLE,如果存在按寻找的位置处理
2)如果不存在,依次在搜索词"EXAMPLE"的头部(最左边)匹配PLE、LE、E

阮兄受教了,讲解的非常容易理解,我实现了一个C++版本:http://blog.csdn.net/honkhat/article/details/51014720

阮老师讲的很清楚,但是有个地方还是有些疑问:“如果综合考虑坏字符和好后缀可能产生遗漏匹配的情况”
-----------------------------------
设:T="abcabababccc" P="abab"
-----------------------------------
第一步:
abcabababccc
abab

a不等于b,P向右移动1位

-----------------------------------
第二步:
abcabababccc
-abab

c不等于b,存在好后缀"ab"
利用坏字符,向右移动2位
利用好后缀,向右移动4位
取最大的移动4位

-----------------------------------
第三步:
abcabababccc
-----abab

观察字串,发现有遗漏的匹配
所以此时应该移动2位
-----------------------------------
abcabababccc
---abab

不清楚是怎么回事

这里的坏字符、好后缀的算法都完全没有讲清楚。拿好后缀来说,前提是按照:

“搜索词中的上一次出现位置”

来计算。

举例:ABACA,好后缀有 ACA, CA, A,那么按照你的逻辑:
ACA = -1, CA = -1。
但是 A 呢?出现了两次,一次 A = 0,一次 A = 2,取哪个?根本没说清楚取哪个,这种情况咋整?

如果按照“搜索词中的上一次出现位置”的取法,那么 A = 2。这样就完全错了,随便举个例子:
文本:BCACABACA
子串:ABACA
如果取 A = 2,则 shift = 4 - 2 = 2,即后移 2 位,显然不是最优,这里后移 4 位,即取 A = 0 才是最优。

那么到此,坏字符、好后缀(包括那三个注意点),都没有描述清楚,如果按照这个去实现算法,出大问题。

@KJ:

说的很对,实际上“好后缀”不是一张表,而是一个整数值,不同的 pattern 计算一次即可。
而“坏字符”则是 key-value pairs,用于快速查询。

文章并没有说清楚。

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接