<fieldset id="seu22"></fieldset>

<ul id="seu22"></ul>

Boyer-Moore算法的實現

stormzhang 發布于2019-08-14 12:08 / 2670人閱讀

摘要：算法用于搜索匹配字符串，如中的查找功能，是一個十分巧妙高效的算法。如果好后綴有多個，則除了最長的那個好后綴，其他好后綴的上一次出現位置必須在頭部。

Boyer-Moore算法用于搜索匹配字符串，如Word中的查找功能，是一個十分巧妙高效的算法。下面是Moore教授自己給出的例子:
http://www.cs.utexas.edu/~moore/best-ideas/string-searching/index.html
根據上面的例子來說一下算法思想：
假定被匹配的字符串為A”This is a simple Example" 搜索的字符串為B“Example”
與暴力匹配不同的是，這個算法從搜索字符串的結尾開始匹配，將A和B的頭對齊。如果結尾不同，那么前面的字符串也都不需要比較了。
步驟：
this is a simple example
example
顯然“s"和”e“不一樣，s就是一個壞字符串。然后把B字符串后移，后移公式為
后移位數 = 壞字符串的位置 - 上一次在字符串B中出現的位置。
如s，后移位數 = 壞字符串位置（6，相對于example，從0開始數） - 上次出現的位置（沒有出現，為-1） = 7
所以把B往后移動7位，直接到了s的后一位。
如此，當我們進行到下面這一步：
this is a simple example
example
B中”mple"和A中相匹配，我們把“mple”稱為好后綴（good suffix),同時“ple","le","e"都是好后綴。此時比較"I"和‘a’不同，需要把字符串往后移，此時因為存在好后綴，移動規則如下：
后移位數 = 好后綴的位置 - 上次出現好后綴的位置

"好后綴"的位置以最后一個字符為準。假定"ABCDEF"的"EF"是好后綴，則它的位置以"F"為準，即5（從0開始計算）。

　　如果"好后綴"在搜索詞中只出現一次，則它的上一次出現位置為 -1。比如，"EF"在"ABCDEF"之中只出現一次，則它的上一次出現位置為-1（即未出現）。

　　如果"好后綴"有多個，則除了最長的那個"好后綴"，其他"好后綴"的上一次出現位置必須在頭部。比如，假定"BABCDAB"的"好后綴"是"DAB"、"AB"、"B"，請問這時"好后綴"的上一次出現位置是什么？回答是，此時采用的好后綴是"B"，它的上一次出現位置是頭部，即第0位。這個規則也可以這樣表達：如果最長的那個"好后綴"只出現一次，則可以把搜索詞改寫成如下形式進行位置計算"(DA)BABCDAB"，即虛擬加入最前面的"DA"。
如上例：mple 好后綴位置為6（e的位置），上次出現位置為0（e在開頭出現了）
那么往后移動6位。

下面給出實現了規則一的代碼，完整的BM算法稍后補充：

    package BM字符串匹配算法;

public class BM {
    private int[] right;//用來記錄A字符串中的字符在字符串B中所在的位置
    private String pat;//目標字符串，也就是字符串B
    BM(String pat){
        this.pat = pat;
        int M = pat.length();
        int R = 256;//ASCII 碼 256種可能的字符
        right = new int[R];
        for(int c = 0;c < R;c++)
            right[c] = -1; //初始化，全都為-1
        for(int j = 0;j < M;j++)
            right[pat.charAt(j)] = j;//在pat中出現的最右的位置

    }

    public int search(String txt){
        int N = txt.length();
        int M = pat.length();
        int skip;
        for(int i = 0;i <= N - M;i += skip){
            //目標字符串B和被匹配字符串在i位置是否相同
            skip = 0;
            for(int j = M-1;j >=0;j--){
                if(pat.charAt(j) != txt.charAt(i+j)){
                    skip = j -right[txt.charAt(i+j)]; //規則一skip等于壞字符串的位置-上一次出現的位置
                    if(skip < 1) skip = 1;
                    break;
                }
            }
            if(skip == 0) return i;//找到匹配
        }
        return N;//未找到匹配
    }
    public static void main(String args[]){
        String pat = "example";
        String txt = "this is a example";
        BM bm = new BM(pat);
        System.out.print(bm.search(txt));
    }
}

使用BM算法在一般情況下，對于長度為N的文本和長度為M的模式字符串需要1 - N/M次比較。

GPU云服務器云服務器最佳置換算法的實現最容易實現的替換算法自主設計編程實現遙感圖像處理的各種算法算法實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64310.html

Majority Vote Alogrithm（最大投票算法）及其擴展

摘要：，這是最基礎的最大投票算法。例如，和這兩個數組最后得到的分別為和，但是這并不影響答案的正確性。接下來，我們可以對這個算法做一些簡單的擴展，我們當前定義的的數量大于的元素。為當前出現的次數。這意味著當前這個數字就是這兩個等待的第三個數字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，這是最基礎的最大投票算法。原文中提到：decid...

niceforbear 2019-08-14 15:25 評論0 收藏0
用 PHP 的方式實現的各類算法合集

摘要：數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。數據對象是性質相同的數據元素的集合，是數據的一個子集。數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...

Karrdy 2019-06-28 13:32 評論0 收藏0
用 PHP 的方式實現的各類算法合集

摘要：數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。數據對象是性質相同的數據元素的集合，是數據的一個子集。數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...

pakolagij 2019-07-25 15:02 評論0 收藏0