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