原文链接:机器学习中的数值查找算法(5)——字符串查找算法(Boyer-Moore算法) – 每天进步一点点 (longkui.site)
Boyer—Moore算法简称BM算法,它是在字符串查找的方法中桐KMP算法一样重要的字符串匹配算法。BM算法相对于KMP算法效果更高,且实现过程更容易理解和实现。
例如,针对被搜索的字符串”小丽同学忙着在吃巧克力,小张同学不吃巧克力“,搜索的字符串为”不吃巧克力“,过程如下步骤所示。
(1)将被搜索字符串和搜索字符串的头部对齐,如下图所示,但是比较的顺序从尾部开始,这也是BM算法中比较好的一种策略。因为不但在英文中,中文中前缀相似的词语也后缀相似的词语多。因此,从尾部开始比较则只需要一次比较就可以知道前面是否还需要继续进行比较。
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042801.png)
从上图中可以看到 ”忙“和”力“不相等,此刻”在“则称作不匹配字符(Bad Character),由于”忙“也不在所示字符串”不吃巧克力“中,因此可以直接跳过一些匹配,将后续字符”着“和”不“对齐,继续进行比较。
(2)将”着“与”不“对齐之后进行比较,如下下图所示:
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042802.png)
依然从字符串的尾部开始比较,可以发现”克“和”力“不相等,因此”克“输入不匹配字符,但是考虑到”克“在搜索词”不吃巧克力“中也出现,则不能按照上一步直接跳过处理。还在BM算法定义了在遇到不匹配字符时的规则(Bad Character Rule),该规则指定了下一步后移字符的位数,公式如下:
后移字符位数=不匹配字符的位置-搜索词中上一次出现的位置
如果不匹配字符在搜索字符串中不存在,则上一次出现位置视为-1.针对“克”在搜索字符串中也存在的情况,则不匹配字符的位置在第四位(索引号从0开始),在搜索词中出现的位置是3,因此后移位数为1,将搜索字符串进行后移一位操作之后,如下图所示:
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042803.png)
(3)从尾部依次按照“力”、“克”、“巧”、“吃”、“不”进行比较,最终比较到“在”与“不”时,发现二者不相等
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042804.png)
因此“在”则被视为不匹配字符,根据后移规则,不匹配字符的位置在第0位,由于搜索词中并不存在,则搜索词中上一次出现的位置为-1,因此搜索字符串后移一位,得到下图:
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042805.png)
但是按照上述移动也会导致没有必要的比较,因为在比较过程中,上述的后缀“吃巧克力”是属于两者的公共后缀,如下图所示:
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042806.png)
在BM算法依然定义了当遇到共同后缀时的移动规则,公式如下:
后移位数=共同后缀的位置-搜索词中上一次出现的位置
因此,共同后缀的起始位置在1(索引从0开始),结束位置在4,共同后缀位置为4。针对搜索词中上一次出现的位置在-1,按照共同后缀的最后一个词在搜索词中第一次出现的位置计算,如果没有仅出现一次记为-1,因此最终得到的后移位数为1.若本例中“力”在搜索词中多次出现,则移动位数会有相应变化。当基于共同后缀的方式移动位数与基于不匹配字符的移动位数不一致时,选择移动次数中较大的值。
在后移一位之后,不断按照上述方法进行比较查找,最终移动到如下图所示:
![](http://kongkui.oss-cn-qingdao.aliyuncs.com/images/2022042807.png)
依然从字符串的尾部开始逐位进行比较,发现从尾到头都完全匹配,因此字符串的查找过程结束,如果需要进行多个相同字符串的查找,则可以继续后移。后移的位数按照基于共同后缀的移动位数方式。即5-0=5,共向右移5位即可。
在上述过程中,实质已经完成了BM算法的流程,但是流程中也存在可以继续完善内容。例如,在计算基于不匹配字符的移动位数与共同后缀情况下的移动位数时,它们移动次数都与被搜索字符串无关,仅与搜索字符串有关。因此,可以实现生成两项位移规则表,在查找过程中只需要对表进行查询即可。
在很多文本编辑器中的查找方式都是基于BM算法实现,相对于KMP算法,它的用性更高,虽然二者的最坏情况下需要的时间为线性的查找时间,但是BM算法的匹配度比KMP算法快3~5倍。