字元串比對算法-BM

  在用于查找子字元串的算法中，BM(Boyer-Moore)算法是目前有效且應用比較廣泛的一種算法，各種文本編輯器的“查找”功能（Ctrl+F），大多采用Boyer-Moore算法。比我們學習的KMP算法快3~5倍。

  在1977年，Boyer-Moore算法由德克薩斯大學的Robert S. Boyer教授和J Strother Moore教授發明

  下面通過Java實作BM算法：

package com.buaa;

import java.util.Random;

/** 
* @ProjectName StringPatternMatchAlgorithm
* @PackageName com.buaa
* @ClassName BM
* @Description TODO
* @Author 劉吉超
* @Date 2016-05-26 22:26:08
*/
public class BM {
    /**
     * 利用壞字元規則計算移動位數
     */
    public static int badCharacter(String moduleString, char badChar,int badCharSuffix){
        return badCharSuffix - moduleString.lastIndexOf(badChar, badCharSuffix);
    }
    
    /**
     * 利用好字尾規則計算移動位數
     */
    public static int goodCharacter(String moduleString,int goodCharSuffix){
        int result = -1;
        // 模式串長度
        int moduleLength = moduleString.length();
        // 好字元數
        int goodCharNum = moduleLength -1 - goodCharSuffix;
        
        for(;goodCharNum > 0; goodCharNum--){
            String endSection = moduleString.substring(moduleLength - goodCharNum, moduleLength);
            String startSection = moduleString.substring(0, goodCharNum);
            if(startSection.equals(endSection)){
                result = moduleLength - goodCharNum;
            }
        }
        
        return result;
    }
    
    /**
     * BM比對字元串 
     * 
     * @param originString 主串
     * @param moduleString 模式串
     * @return 若比對成功，傳回下标，否則傳回-1 
     */
    public static int match(String originString, String moduleString){
        // 主串
        if (originString == null || originString.length() <= 0) {
            return -1;
        }
        // 模式串
        if (moduleString == null || moduleString.length() <= 0) {
            return -1;
        }
        // 如果模式串的長度大于主串的長度，那麼一定不比對
        if (originString.length() < moduleString.length()) {
            return -1;
        }
        
        int moduleSuffix = moduleString.length() -1;
        int module_index = moduleSuffix;
        int origin_index = moduleSuffix;
        
        for(int ot = origin_index; origin_index < originString.length() && module_index >= 0;){
            char oc = originString.charAt(origin_index);
            char mc = moduleString.charAt(module_index);
            if(oc  == mc){
                origin_index--;
                module_index--;
            }else{
                // 壞字元規則
                int badMove = badCharacter(moduleString,oc,module_index);
                // 好字元規則
                int goodMove = goodCharacter(moduleString,module_index);
                 // 下面兩句代碼可以這樣了解，主串位置不動，模式串向右移動
                origin_index = ot + Math.max(badMove, goodMove);
                 module_index = moduleSuffix;
                 // ot就是中間變量
                 ot = origin_index;
            }
        }
        
        if(module_index < 0){
            // 多減了一次
            return origin_index + 1;
        }
        
        return -1;
    }
    
    /**
     * 随機生成字元串
     *  
     * @param length 表示生成字元串的長度  
     * @return String
     */
    public static String generateString(int length) {
        String baseString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";     
        
        StringBuilder result = new StringBuilder();
        
        Random random = new Random();     
        for (int i = 0; i < length; i++) {     
            result.append(baseString.charAt(random.nextInt(baseString.length())));     
        }
        
        return result.toString();     
     }
    
    public static void main(String[] args) {  
        // 主串
//        String originString = generateString(10);
        String originString = "HERE IS A SIMPLE EXAMPLE";
        // 模式串
//        String moduleString = generateString(4);
        String moduleString = "EXAMPLE";
        // 壞字元規則表
//        int[] badCharacterArray = badCharacter(originString,moduleString);
        
        System.out.println("主串：" + originString);
        System.out.println("模式串：" + moduleString);
        
        
        int index = match(originString, moduleString);
        System.out.println("比對的下标：" + index);
    } 
}      

  下面，我來解釋上面代碼

    首先先明确兩個規則：壞字元規則、好字尾規則

    1、壞字元規則

      後移位數 = 壞字元的位置 - 模式串中的壞字元上一次出現位置

      如果"壞字元"不包含在模式串之中，則上一次出現位置為 -1。以下面這兩個字元串為例

      因為"P"與"E"不比對，是以"P"被稱為"壞字元"，它出現在模式串（模式串就是EXAMPLE）的第6位（從0開始編号），在模式串中的上一次出現位置為4，是以後移 6 - 4 = 2位

    2、好字尾規則 

      後移位數 = 好字尾的位置 - 模式串中的上一次出現位置

      舉例來說，如果模式串"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位，其他好字尾上一次出現的位置都不在頭部

  規則講完啦，接下說一下上面代碼

  1、假定主串為"HERE IS A SIMPLE EXAMPLE"，模式串為"EXAMPLE"，模式串也就是搜尋詞 

主串	HERE IS A SIMPLE EXAMPLE
模式串	EXAMPLE

  2、首先，主串與模式串頭部對齊，從尾部開始比較。這是一個很聰明的想法，因為如果尾部字元不比對，那麼隻要一次比較，就可以知道前7個字元（整體上）肯定不是要找的結果。我們看到，"S"與"E"不比對。這時，"S"就被稱為"壞字元"（bad character），這時用壞字元規則得到的是7，用好字尾規則得到的是-1，選擇大的作為後移位數，這裡選擇7

3、依然從尾部開始比較，發現"P"與"E"不比對，是以"P"是"壞字元"。

4、這時用壞字元規則得到的是2，用好字尾規則得到的是-1，選擇大的作為後移位數，這裡選擇2

5、依然從尾部開始比較，"E"與"E"比對。

6、比較前面一位，"LE"與"LE"比對。

7、比較前面一位，"PLE"與"PLE"比對

8、比較前面一位，"MPLE"與"MPLE"比對。我們把這種情況稱為"好字尾"（good suffix），即所有尾部比對的字元串。注意，"MPLE"、"PLE"、"LE"、"E"都是好字尾

9、比較前一位，發現"I"與"A"不比對。是以，"I"是"壞字元"，這時用壞字元規則得到的是3，用好字尾規則得到的是6，選擇大的作為後移位數，這裡選擇6

10、繼續從尾部開始比較，"P"與"E"不比對，是以"P"是"壞字元"。這時用壞字元規則得到的是2，用好字尾規則得到的是-1，選擇大的作為後移位數，這裡選擇2

11. 從尾部開始逐位比較，發現全部比對，于是搜尋結束

如果，您認為閱讀這篇部落格讓您有些收獲，不妨點選一下右下角的【推薦】。

如果，您希望更容易地發現我的新部落格，不妨點選一下左下角的【關注我】。

如果，您對我的部落格所講述的内容有興趣，請繼續關注我的後續部落格，我是【劉超★ljc】。

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。