小例子理解BM匹配算法
字符串為 HERE IS A SIMPLE EXAMPLE
搜索詞為 EXAMPLE
1

圖一
從尾部開始比較，思路的出發(fā)點(diǎn)是，只要尾部字符如果不匹配的話，前面比較也就沒什么意義。
如圖一：S與E不匹配，那么S被稱為壞字符，并且EXAMPLE中不包含S，所以把搜索詞移到S的后面。
2

圖二 ：P和E繼續(xù)不匹配，繼續(xù)在搜索詞中查找P,搜索詞后移兩位。
3

圖三
因此，總結(jié)出來的壞字符規(guī)則是：

后移位數(shù)=壞字符的位置 - 搜索次中上一次出現(xiàn)的位置

如果壞字符的位置不在搜索詞中，則上次出現(xiàn)的位置為-1，相當(dāng)于把搜索詞整體移動(dòng)到壞字符的后面 例如第一次變換。

4

依次從尾部開始比較；
5

6

例如上面三步驟，后綴MPLE依次相匹配，我們把這種情況稱為好后綴，其中MPLE PLE LE E 都是稱為好后綴。
7
比較前一位發(fā)現(xiàn) I 和A不匹配，所以I是壞字符
根據(jù)壞字符規(guī)則，搜索詞應(yīng)該后移2-（-1）=3位
8

好后綴規(guī)則：
后移位數(shù) = 好后綴的位置 - 搜索詞中上一次出現(xiàn)位置

舉例1，如果字符串"ABCDAB"的后一個(gè)"AB"是"好后綴"。那么它的位置是5（從0開始計(jì)算，取最后的"B"的值），在"搜索詞中的上一次出現(xiàn)位置"是1（第一個(gè)"B"的位置），所以后移 5 - 1 = 4位，前一個(gè)"AB"移到后一個(gè)"AB"的位置。

舉例2，如果字符串"ABCDEF"的"EF"是好后綴，則"EF"的位置是5 ，上一次出現(xiàn)的位置是 -1（即未出現(xiàn)），所以后移 5 - (-1) = 6位，即整個(gè)字符串移到"F"的后一位。
9

回到上邊例子。此時(shí)，所有的"好后綴"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"還出現(xiàn)在頭部，所以后移 6 - 0 = 6位。
10

"壞字符規(guī)則"只能移3位，"好后綴規(guī)則"可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移這兩個(gè)規(guī)則之中的較大值。
11

根據(jù)壞字符規(guī)則 P是壞字符 P和E不匹配，根據(jù)壞字符規(guī)則，后移6 - 4 =2位。
12

匹配成功。
python代碼部分：

def getBMBC(pattern)#預(yù)計(jì)生成壞字符表BMBC=dict()for i in range(len(pattern)-1):char=pattern[i]BMBC[char]=i+1return BMBC def getBMGS(pattern): # 預(yù)計(jì)生成好后綴 BMGS= dict()#無后綴壞字符移動(dòng)符規(guī)則 BMGS['']=0for i in range(len(pattern)):#好后綴GS=pattern[len(pattern)-i-1:]for j in range(len(pattern)-i-1):NGS=pattern[j:j+i+1]if GS ==NGS:BMGS[GS]=len(pattern)-j-i-1return BMGSdef BM(string,pattern):m=len(pattern)n=len(string)i=0j=mindex=[]BMBC=getBMBC(pattern=pattern)BMGS=getBMGS(pattern=pattern)while i<n:while(j>0):if i+j-1>=n:return indiesa=string[i+j-1:i+m]b=pattern[j-1:]if a==b:j=j-1else:i=i+max(BMGS.setdefault(b[1:],m),j - BMBC.setdefault(string[i+j-1],0))j=mif j==0:indies.append(i)i+=1j=len(pattern)

完整代碼：

import datetimedef getBMBC(pattern):# 預(yù)生成壞字符表BMBC = dict()for i in range(len(pattern) - 1):char = pattern[i]# 記錄壞字符最右位置（不包括模式串最右側(cè)字符）BMBC[char] = i + 1return BMBCdef getBMGS(pattern):# 預(yù)生成好后綴表BMGS = dict()# 無后綴僅根據(jù)壞字移位符規(guī)則BMGS[''] = 0for i in range(len(pattern)):# 好后綴GS = pattern[len(pattern) - i - 1:]for j in range(len(pattern) - i - 1):# 匹配部分NGS = pattern[j:j + i + 1]# 記錄模式串中好后綴最靠右位置（除結(jié)尾處）if GS == NGS:BMGS[GS] = len(pattern) - j - i - 1return BMGSdef BM(string, pattern):"""Boyer-Moore算法實(shí)現(xiàn)字符串查找"""m = len(pattern)#子串n = len(string)#父串i = 0j = mindies = []BMBC = getBMBC(pattern=pattern) # 壞字符表BMGS = getBMGS(pattern=pattern) # 好后綴表while i < n:while (j > 0):if i + j -1 >= n: # 當(dāng)無法繼續(xù)向下搜索就返回值return indies# 主串判斷匹配部分a = string[i + j - 1:i + m]# 模式串判斷匹配部分b = pattern[j - 1:]# 當(dāng)前位匹配成功則繼續(xù)匹配if a == b:j = j - 1# 當(dāng)前位匹配失敗根據(jù)規(guī)則移位else:i = i + max(BMGS.setdefault(b[1:], m), j - BMBC.setdefault(string[i + j - 1], 0))j = m# 匹配成功返回匹配位置if j == 0:indies.append(i)i += 1j = len(pattern)if __name__ == '__main__':starttime = datetime.datetime.now()string =[]pattern =[]file = open("E:\\tim下載的文件\\bm匹配算法文檔\\chr1.fa", "r", encoding='utf-8')for line in file:if not line.startswith('>'):string.append(line.replace('\n',''))string = ''.join(string)#join() 方法用于將序列中的元素以指定的字符連接生成一個(gè)新的字符串；string = string.upper()file.close()#s_2 = s_1.upper()pattern="CACGTGCTACCACGCCCGGCTAATTTTTGTGTTTTTAATAGAGACAGGATTT CACCATCTTGACCAGGCTGGTCTCAAACTCCTGACCTCATGATCCACC"s = BM(string,pattern)print (string)print (pattern)print (s)#starttime=datetime.datetime.now()endtime=datetime.datetime.now()print ((endtime-starttime).seconds)

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

總結(jié)

以上是生活随笔為你收集整理的BM匹配算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。