資訊專欄INFORMATION COLUMN
摘要：算法用于搜索匹配字符串，如中的查找功能，是一個十分巧妙高效的算法。如果好后綴有多個，則除了最長的那個好后綴，其他好后綴的上一次出現(xiàn)位置必須在頭部。
Boyer-Moore算法用于搜索匹配字符串，如Word中的查找功能，是一個十分巧妙高效的算法。下面是Moore教授自己給出的例子:
http://www.cs.utexas.edu/~moore/best-ideas/string-searching/index.html
根據(jù)上面的例子來說一下算法思想：
假定被匹配的字符串為A”This is a simple Example" 搜索的字符串為B“Example”
與暴力匹配不同的是，這個算法從搜索字符串的結(jié)尾開始匹配，將A和B的頭對齊。如果結(jié)尾不同，那么前面的字符串也都不需要比較了。
步驟：
this is a simple example
example
顯然“s"和”e“不一樣，s就是一個壞字符串。然后把B字符串后移，后移公式為
后移位數(shù) = 壞字符串的位置 - 上一次在字符串B中出現(xiàn)的位置。
如s，后移位數(shù) = 壞字符串位置（6，相對于example，從0開始數(shù)） - 上次出現(xiàn)的位置（沒有出現(xiàn)，為-1） = 7
所以把B往后移動7位，直接到了s的后一位。
如此，當(dāng)我們進行到下面這一步：
this is a simple example
example
B中”mple"和A中相匹配，我們把“mple”稱為 好后綴（good suffix),同時“ple","le","e"都是好后綴。此時比較"I"和‘a(chǎn)’不同，需要把字符串往后移，此時因為存在好后綴，移動規(guī)則如下：
后移位數(shù) = 好后綴的位置 - 上次出現(xiàn)好后綴的位置
"好后綴"的位置以最后一個字符為準(zhǔn)。假定"ABCDEF"的"EF"是好后綴，則它的位置以"F"為準(zhǔn)，即5（從0開始計算）。
如果"好后綴"在搜索詞中只出現(xiàn)一次，則它的上一次出現(xiàn)位置為 -1。比如，"EF"在"ABCDEF"之中只出現(xiàn)一次，則它的上一次出現(xiàn)位置為-1（即未出現(xiàn)）。
如果"好后綴"有多個，則除了最長的那個"好后綴"，其他"好后綴"的上一次出現(xiàn)位置必須在頭部。比如，假定"BABCDAB"的"好后綴"是"DAB"、"AB"、"B"，請問這時"好后綴"的上一次出現(xiàn)位置是什么？回答是，此時采用的好后綴是"B"，它的上一次出現(xiàn)位置是頭部，即第0位。這個規(guī)則也可以這樣表達：如果最長的那個"好后綴"只出現(xiàn)一次，則可以把搜索詞改寫成如下形式進行位置計算"(DA)BABCDAB"，即虛擬加入最前面的"DA"。
如上例：mple 好后綴位置為6（e的位置），上次出現(xiàn)位置為0（e在開頭出現(xiàn)了）
那么往后移動6位。
下面給出實現(xiàn)了規(guī)則一的代碼，完整的BM算法稍后補充：
package BM字符串匹配算法;
public class BM {
private int[] right;//用來記錄A字符串中的字符在字符串B中所在的位置
private String pat;//目標(biāo)字符串，也就是字符串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中出現(xiàn)的最右的位置
}
public int search(String txt){
int N = txt.length();
int M = pat.length();
int skip;
for(int i = 0;i <= N - M;i += skip){
//目標(biāo)字符串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)]; //規(guī)則一skip等于壞字符串的位置-上一次出現(xiàn)的位置
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次比較。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/64310.html
摘要：，這是最基礎(chǔ)的最大投票算法。例如，和這兩個數(shù)組最后得到的分別為和，但是這并不影響答案的正確性。接下來，我們可以對這個算法做一些簡單的擴展，我們當(dāng)前定義的的數(shù)量大于的元素。為當(dāng)前出現(xiàn)的次數(shù)。這意味著當(dāng)前這個數(shù)字就是這兩個等待的第三個數(shù)字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，這是最基礎(chǔ)的最大投票算法。 原文中提到：decid...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
摘要：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。 項目地址 https://github.com/m9rco/algo... 每周最少一更，求出題，求虐待 At least once a week, ask for problems and abuse 簡...
閱讀 3400·2023-04-25 17:19
閱讀 700·2021-11-23 09:51
閱讀 1407·2021-11-08 13:19
閱讀 855·2021-09-29 09:34
閱讀 1754·2021-09-28 09:36
閱讀 1547·2021-09-22 14:59
閱讀 2777·2019-08-29 16:38
閱讀 2107·2019-08-26 13:40
