不用找了，学习BM算法，这篇就够了（思路+详注代码）

迷南。 2023-05-21 15:29 45阅读 0赞

## 写在前面 ##

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

在学习研究BM算法之前，我是已经掌握了KMP算法，所以建议还没有掌握的同学，先去学习一下，循序渐进的来，可以看我的[KMP算法][KMP]的文章。为什么说循序渐进，是因为BM算法，在大多数情况下，表现的比KMP算法优秀，所以大部分时候，都当做KMP进阶的算法来学习。BM算法从模式串的尾部开始匹配，且拥有在最坏情况下 $O(N) $的时间复杂度。有数据表明，在实践中，比 KMP 算法的实际效能高，可以快大概 3-5 倍，很值得学习。在学习BM算法的时候，找了很多资料，也遇到了很多优秀的文章，不过目前还没有碰到即讲清楚了原理，又实现了代码的文章，java版的更是不容易找。所以我这里打算站在大神的肩膀上学习，写下这篇文章，由于一些图画的比较占用时间，我就直接引用一些博文中的图片。感兴趣的可以直接看大神们的文章。

*  [阮一峰的BM算法文章][BM]
 *  [BM算法的论文][BM 1]
 *  [BM算法创造者的例子][BM 2]
 *  [BM算法讲解中C语言讲解的比较好的文章][BM_C]
 *  [图解BM算法][BM 3]
 *  [Boyer-Moore algorithm][]

## BM算法原理 ##

BM算法定义了两个规则：

*  坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，`移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置`。此外，`如果"坏字符"不包含在模式串之中，则最右出现位置为-1`。
 *  好后缀规则：当字符失配时，`后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置`，且`如果好后缀在模式串中没有再次出现，则为-1`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]

下面举例说明BM算法。例如，给定文本串“`HERE IS A SIMPLE EXAMPLE`”，和模式串“`EXAMPLE`”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

*  首先，“文本串"与"模式串"头部对齐，从尾部开始比较。”`S`“与”`E`“不匹配。这时，”`S`“就被称为"坏字符”（bad character），即不匹配的字符，它对应着模式串的第`6`位。且"`S`“不包含在模式串”`EXAMPLE`“之中（相当于最右出现位置是`-1`），这意味着可以把模式串后移`6-(-1)=7`位，从而直接移到”`S`"的后一位。  
    ![在这里插入图片描述][20200416232645818.png_pic_center]
 *  依然从尾部开始比较，发现"`P`“与”`E`“不匹配，所以”`P`“是"坏字符”。但是，"`P`“包含在模式串”`EXAMPLE`"之中。因为“`P`”这个“坏字符”对应着模式串的第`6`位（从`0`开始编号），且在模式串中的最右出现位置为`4`，所以，将模式串后移`6-4=2`位，两个"P"对齐。  
    ![在这里插入图片描述][20200416232659663.png_pic_center]  
    ![在这里插入图片描述][20200416232705526.png_pic_center]
 *  依次比较，得到 “`MPLE`”匹配，称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"`MPLE`"、"`PLE`"、"`LE`"、"`E`"都是好后缀。  
    ![在这里插入图片描述][20200416232717269.png_pic_center]
 *  发现“`I`”与“`A`”不匹配：“`I`”是坏字符。如果是根据坏字符规则，此时模式串应该后移`2-(-1)=3`位。问题是，有没有更优的移法？  
    ![在这里插入图片描述][20200416232732644.png_pic_center]  
    ![在这里插入图片描述][20200416232738946.png_pic_center]
 *  更优的移法是利用好后缀规则：当字符失配时，`后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置`，且如果好后缀在模式串中没有再次出现，则为`-1`。所有的“好后缀”（`MPLE、PLE、LE、E`）之中，只有“`E`”在“`EXAMPLE`”的头部出现，所以后移`6-0=6`位。可以看出，“坏字符规则”只能移`3`位，“好后缀规则”可以移`6`位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。  
    ![在这里插入图片描述][20200416232805600.png_pic_center]
 *  继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”，根据“坏字符规则”，后移 6 - 4 = 2位。因为是最后一位就失配，尚未获得好后缀。  
    ![在这里插入图片描述][20200416232819406.png_pic_center]

## 好后缀加深理解 ##

由上可知，BM算法不仅效率高，而且构思巧妙，容易理解。坏字符规则相对而言比较好理解，好后缀如果还不理解，我这里再继续举个例子解释一下，这里加深理解。

*  如果模式串中存在已经匹配成功的好后缀，则把目标串与好后缀对齐，然后从模式串的最尾元素开始往前匹配。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]
 *  如果无法找到匹配好的后缀，找一个匹配的最长的前缀，让目标串与最长的前缀对齐（如果这个前缀存在的话）。模式串\[m-s，m\] = 模式串\[0，s\] 。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 4]
 *  如果完全不存在和好后缀匹配的子串，则右移整个模式串。

## 先实现好字符规则 ##

BM算法还是很好理解的，其实如果你之前学习KMP算法你也会有同样的感受，KMP算法理解起来不是很难，但是重点在于怎么去实现next数组。BM算法也是，原理理解起来其实非常的容易，不过怎么去实现，没有一套标准的代码。不过可以研究别人的代码，然后实现一套尽量适合精简的代码。还是一样，一步一步来，我们先来实现好字符规则。好字符规则的代码如下，我会在代码中必要的地方加入注释，辅助理解，代码是最好的老师。

public static void getRight(String pat, int[] right) { 
    	//首先创建一个模式串的字符位置的数组，初始化为-1，就是用于记录模式串
    	//中，每个字符在模式串中的相对位置，这里直接用的是256，也
    	//就是ASCII码的最大值，当然，如果你的字符串中只限制了26个
    	//字符，你也可以直接使用26
        for (int i = 0; i < 256; i++) { 
            right[i] = -1;
        }
        //值得一提的是，通过这种方式，可以你会发现，如果模式串中存在相同的
        //字符，那么right数组中，记录的是最右的那个字符的位置
        for (int j = 0; j < pat.length(); j++) { 
            right[pat.charAt(j)] = j;
        }
    }
    
    public static int Search(String txt, String pat, int[] right) { 
        int M = txt.length();//主串的长度
        int N = pat.length();//模式串的长度
        int skip;//用于记录跳过几个字符
        for (int i = 0; i < M - N; i += skip) { 
            skip = 0;//每次进入循环要记得初始化为0
            for (int j = N - 1; j >= 0; j--) { 
            	//不相等，意味着出现坏字符，按照上面的规则移动
                if (pat.charAt(j) != txt.charAt(i + j)) { 
                    skip = j - right[txt.charAt(i + j)];
                    //skip之所以会小于1，可能是因为坏字符在模式串中最右的位置，可能
                    //在j指向字符的右侧，就是已经越过了。
                    if (skip < 1) 
                        skip = 1;
                    break;
                }
            }
            //注意了这个时候循环了一遍之后，skip如果等于0，意味着没有坏字符出现，所以
            //匹配成功，返回当前字符i的位置
            if (skip == 0)
                return i;
        }
        return -1;
    }

## 完整BM实现 ##

上面的代码不难理解，相信你已经看懂了，那么接下来也不用单独来讲好后缀的实现，直接上完整的实现代码。因为完整的BM实现中，就是比较坏字符规则以及好后缀规则，哪个移动的字符数更多，就使用哪个。老样子，下面的代码中我尽量的加注释。

public static int pattern(String pattern, String target) { 
        int tLen = target.length();//主串的长度
        int pLen = pattern.length();//模式串的长度
    
    	//如果模式串比主串长，没有可比性，直接返回-1
        if (pLen > tLen) { 
            return -1;
        }
    
        int[] bad_table = build_bad_table(pattern);// 获得坏字符数值的数组，实现看下面
        int[] good_table = build_good_table(pattern);// 获得好后缀数值的数组，实现看下面
    
        for (int i = pLen - 1, j; i < tLen;) { 
            System.out.println("跳跃位置：" + i);
            //这里和上面实现坏字符的时候不一样的地方，我们之前提前求出坏字符以及好后缀
            //对应的数值数组，所以，我们只要在一边循环中进行比较。还要说明的一点是，这里
            //没有使用skip记录跳过的位置，直接针对主串中移动的指针i进行移动
            for (j = pLen - 1; target.charAt(i) == pattern.charAt(j); i--, j--) { 
                if (j == 0) { //指向模式串的首字符，说明匹配成功，直接返回就可以了
                    System.out.println("匹配成功，位置：" + i);
                    //如果你还要匹配不止一个模式串，那么这里直接跳出这个循环，并且让i++
                    //因为不能直接跳过整个已经匹配的字符串，这样的话可能会丢失匹配。
    // i++; // 多次匹配
    // break;
                    return i;
                }
            }
            //如果出现坏字符，那么这个时候比较坏字符以及好后缀的数组，哪个大用哪个
            i += Math.max(good_table[pLen - j - 1], bad_table[target.charAt(i)]);
        }
        return -1;
    }
    
    //字符信息表
    public static int[] build_bad_table(String pattern) { 
        final int table_size = 256;//上面已经解释过了，字符的种类
        int[] bad_table = new int[table_size];//创建一个数组，用来记录坏字符出现时，应该跳过的字符数
        int pLen = pattern.length();//模式串的长度
    
        for (int i = 0; i < bad_table.length; i++) { 
            bad_table[i] = pLen;  
            //默认初始化全部为匹配字符串长度,因为当主串中的坏字符在模式串中没有出
            //现时，直接跳过整个模式串的长度就可以了
        }
        for (int i = 0; i < pLen - 1; i++) { 
            int k = pattern.charAt(i);//记录下当前的字符ASCII码值
            //这里其实很值得思考一下，bad_table就不多说了，是根据字符的ASCII值存储
            //坏字符出现最右的位置，这在上面实现坏字符的时候也说过了。不过你仔细思考
            //一下，为什么这里存的坏字符数值，是最右的那个坏字符相对于模式串最后一个
            //字符的位置？为什么？首先你要理解i的含义，这个i不是在这里的i，而是在上面
            //那个pattern函数的循环的那个i，为了方便我们称呼为I，这个I很神奇，虽然I是
            //在主串上的指针，但是由于在循环中没有使用skip来记录，直接使用I随着j匹配
            //进行移动，也就意味着，在某种意义上，I也可以直接定位到模式串的相对位置，
            //理解了这一点，就好理解在本循环中，i的行为了。
    
    		//其实仔细去想一想，我们分情况来思考，如果模式串的最
            //后一个字符，也就是匹配开始的第一个字符，出现了坏字符，那么这个时候，直
            //接移动这个数值，那么正好能让最右的那个字符正对坏字符。那么如果不是第一个
            //字符出现坏字符呢？这种情况你仔细想一想，这种情况也就意味着出现了好后缀的
            //情况，假设我们将最右的字符正对坏字符
            bad_table[k] = pLen - 1 - i;
        }
        return bad_table;
    }
    
    //匹配偏移表
    public static int[] build_good_table(String pattern) { 
        int pLen = pattern.length();//模式串长度
        int[] good_table = new int[pLen];//创建一个数组，存好后缀数值
        //用于记录最新前缀的相对位置，初始化为模式串长度，因为意思就是当前后缀字符串为空
        //要明白lastPrefixPosition 的含义
        int lastPrefixPosition = pLen;
    
        for (int i = pLen - 1; i >= 0; --i) { 
            if (isPrefix(pattern, i + 1)) { 
            //如果当前的位置存在前缀匹配，那么记录当前位置
                lastPrefixPosition = i + 1;
            }
            good_table[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1;
        }
    
        for (int i = 0; i < pLen - 1; ++i) { 
        //计算出指定位置匹配的后缀的字符串长度
            int slen = suffixLength(pattern, i);
            good_table[slen] = pLen - 1 - i + slen;
        }
        return good_table;
    }
    
    //前缀匹配
    private static boolean isPrefix(String pattern, int p) { 
        int patternLength = pattern.length();//模式串长度
        //这里j从模式串第一个字符开始，i从指定的字符位置开始，通过循环判断当前指定的位置p
        //之后的字符串是否匹配模式串前缀
        for (int i = p, j = 0; i < patternLength; ++i, ++j) { 
            if (pattern.charAt(i) != pattern.charAt(j)) { 
                return false;
            }
        }
        return true;
    }
    
    //后缀匹配
    private static int suffixLength(String pattern, int p) { 
        int pLen = pattern.length();
        int len = 0;
        for (int i = p, j = pLen - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) { 
            len += 1;
        }
        return len;
    }

理解一下上面代码，这里我针对上面代码举个例子，计算之后的两张表的数值如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][20200417184330586.png_pic_center]

## 总结 ##

其实如果你把上面理解了，我相信你会有一种兴奋，可能还会有一种疑问，就是BM的算法，如果将坏字符和好后缀规则都实现了，看着代码量怎么多，而且在计算两个位移数组的时候，相当于要做这么多准备工作，难道不会影响效率么。这个问题我也不好回答，根据不同语言的具体实现，代码的执行效率也会有所影响，不过有一点可以肯定的是，当字符匹配的长度量非常大的时候，BM的算法优势还是很明显的，而且要知道，BM算法在CV中应用的还是很广泛的，毕竟CV中的数据集样本动不动就是上百万。BM算法非常值得一学。

[KMP]: https://dengbocong.blog.csdn.net/article/details/105500652
[BM]: https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
[BM 1]: http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
[BM 2]: http://www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html
[BM_C]: https://www.cnblogs.com/xubenben/p/3359364.html
[BM 3]: https://mp.weixin.qq.com/s/S68mm8XicGerimD8zC6b-Q
[Boyer-Moore algorithm]: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: /images/20230521/9a585119790b4ed8b1d71240a858034c.png
[20200416232645818.png_pic_center]: /images/20230521/50c8ffc2c6c440cfa7b5d76eeed7aa27.png
[20200416232659663.png_pic_center]: /images/20230521/6cd1cb700fd84d3d917d5d169edd2797.png
[20200416232705526.png_pic_center]: /images/20230521/ff8a3476ee5742909faca2fc21f9a2da.png
[20200416232717269.png_pic_center]: /images/20230521/10679040dd5f4eeaa25588bd444a3c0a.png
[20200416232732644.png_pic_center]: /images/20230521/be0113e4a45747ce8229cf83a7fd450d.png
[20200416232738946.png_pic_center]: /images/20230521/92546a304e0a4fe293db6cfa36cc30fe.png
[20200416232805600.png_pic_center]: /images/20230521/2f1622815aa9465480f7fb77495c4cba.png
[20200416232819406.png_pic_center]: /images/20230521/4a859094edfa48d28683f9034a30d187.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230521/081882a2d0b44a8baaa26358ed99eb8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230521/37352d5f21554e8da5851f881f688b13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230521/e1e453a2155d43218921a1b926664098.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230521/bb188e2637724c8e821e69689f1d2bb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230521/022935d5d60b4169ad3e93fde855956e.png
[20200417184330586.png_pic_center]: /images/20230521/4fe18c9677994a15a383cedd98af620f.png