A New Start

字符串匹配算法(二)BM

一、简介

       上文中我们介绍了一款字符串匹配的算法,此文会介绍另一款更高效的算法,据称会教KMP算法而言,效率提高了3~5倍。

       该算法由 Bob Boyer 和J Strother Moore 共同创建,故称为 Boyer-Moore 字符串搜索算法,简称 BM 算法。

       我们在文本文档编辑的时候,常用的搜索功能(Ctrl + F),底层算法其实就是该 BM 算法。

二、名词定义

    以下摘自 wikipedia

  • 被检索的字符,也就是原文,称为 text,用符号 T 表示

  • 检索的字符串,也就是你需要搜索的字符串,称为模式串,也称为 pattern,用符号 P 表示

  • P 的长度记为 n

  • T 的长度记为 m

  • S[i] 为字符串 S 从1开始计数的第 i 个字符

  • S[i..j] 为字符串 S 的一个子串,始于i,终于j

  • S 的前缀定义为 S[1..i],其中 i 小于S 的长度

  • S 的后缀定义为 S[i..n],其中n 为 S 的长度

  • k 表示 字符串P 的最后一位在 T 中的位置

  • 当发生匹配时,P 在 T 中的位置记为 T[(k-n+1)..k]

  • 坏字符:T 和 P 中不匹配的字符(下文的案例中会详细介绍)

  • 好后缀:T 和 P 中相匹配的后缀(下文的案例中会详细介绍)

三、原理简析

       下面以图示的方式,来简单阐述 BM 算法的匹配步骤。

       首先,相较于朴素的算法,朴素算法是从 P 的首字符开始匹配,直至出现不一致,然后再将 P 后移一定的位数。而 BM 算法的变通之处主要出现在两点上:

            ①BM 算法从 P 的末字符开始,依次往前进行匹配,直至出现不一致;

            ②此时 P 需要右移,那么右移多少位呢?该位数由两个子算法共同构成,即坏字符算法好后缀算法,两者分别进行计算右移的位数,谁算得的右移位数多,最终 P 右移的位数便会采用。

       其实,坏字符和好后缀计算的右移位数的计算,都是查询相应的表而得到的,而这两张表,就是 BM 的核心,即,该算法需要对 P 进行预处理,从而得出这两张表。

四、简明图示案例

        BM 算法核心:找到一个后缀,让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐。

       案例一T 0123456789  , PMOORE

        常规的匹配是先将0和M开始匹配,不一样,然后后移一位,再将1和M进行匹配,依次类推,总共需要匹配10次,或者先进一点,需要匹配6次,

        而我们的 BM 算法,如果利用坏字符规则,则只需要匹配两次:

            第一次直接将4和E进行匹配,出现不一致,此时我们需要将P后移,此时的4即为坏字符,那么后移多少位呢?此处根据核心:找到一个后缀,让已匹配过的后缀与P中从后往前最近的一个相同的子串对齐,而此处,由于已匹配过的后缀是4,但是这个4并没有出现在P中,所以将整个P往后移,直至P的首字符M位于4的后面,即将P往后移动5个字符,也就是往后移P的长度个字符。

            另外,坏字符移动规则公式为:后移位数 = 坏字符位数 – 坏字符在P中上次出现的位置

            而此处:后移位数 = 5 – 0 = 5,所以后移5位

            第二次匹配的话,同理。所以,最后仅仅匹配了2次便查找完毕了,效率很高。

        上述案例的运行模式可以见下图:

        BM01.png

       案例二THERE IS A SIMPLE EXAMPLE   , PEXAMPLE

            这个案例取自 BM 算法的创始人之一 Moore 教授自己言传身教的例子。

            先来说说什么是好后缀以及好后缀的一些移动规则:

                T 和 P 进行匹配的时候,从P 的尾部开始,匹配出的相同的字符串(包括单个字符)即为好后缀,

                如 ABCDAB 和 BACD,首次匹配时,首字符对齐,从尾开始匹配,发现有相同的字符串 “CD”,此时的好后缀有 “CD”和“D”,

                知道了好后缀的定义,那么根据好后缀计算而得的右移位数的计算方式呢? 右移位数 = 好后缀的位置 – 好后缀在模式串P中上一次出现的位置

                此处需要注意三点:

                    ① 好后缀的位置,以好后缀的最后一个字符为准,即假设“BACD”的 CD 是好后缀,则好后缀的位置以“D”为准,即4(从1开始计算);

                    ② 如果好后缀在模式串中只出现过一次,比如:假设“BACD”的 CD 是好后缀,而 CD 仅出现了一次,则上一次出现的位置记做 0(即未出现过);

                    ③ 如果好后缀有多个,计算上次出现位置时,此时除了最长的那个好后缀,其余的好后缀上次出现的位置必须是在头部(即起始位置)。比如:假设“DCDBACD”的好后缀为 ACD,同样,好后缀还有 CD,D,总共三个好后缀,我们依次来计算上次出现的位置,“ACD”仅出现一次,为0,当没有其它有效的好后缀的时候,便用这个;“CD”上次出现位置不在头部,不计算;“D”这个字符正好和头部相同,故“D”的上次出现位置为1,所以好后缀在模式串P中上一次出现的位置为1。

            说完了规则,那么我们正式看案例,见下图:

            BM02.png

            原理讲明白了,那么我们就该搞清楚其中最为核心的 《坏字符规则表》和《好后缀规则表》 的生成原理了。

            

五、代码实现

六、资料

1、源码地址:传送门

2、有一篇文章可以参考,很不错,传送门

点赞

发表评论

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