iT邦幫忙

0

Boyer-Moore字串搜尋演算法

python boyer-moore 字串搜尋 演算法
nwm310 2025-03-29 15:56:30 ‧ 1179 瀏覽

  • 分享至 

  • xImage
    •  

從後面往前面比對

text = 'ＱＱＱＡ２３Ｂ２３'
pattern = 'Ｂ２３'

# 長度
n = len(text)
m = len(pattern)

# 尾端對齊。從後面往前面比對
i = m - 1       # text索引值
j = m - 1       # pattern索引值

# 備份。比對失敗時使用。使i、j回到尾端
i0 = i
j0 = j

while i < n:
    if text[i] == pattern[j]: # 比對成功
        if j == 0:
            return i
        else:
            i -= 1
            j -= 1

    else: # 比對失敗
        i = i0 + 移動格數
        j = j0
        i0 = i

return -1

壞字符規則

壞字符

從後面往前比對

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３
比對失敗

壞字符是Ａ

對齊壞字符

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

pattern往右移動
還沒比對的字陸續經過壞字符Ａ
如果某個字和壞字符相同，就可以對齊

ＱＱＱＡ２３Ｂ２３
　　　Ａ２３Ｂ２３

這是從後面往前面比對的原因

移動格數

j是比對失敗位置

如果有找到相同的字
移動格數 = j - 相同字的索引值

如果沒有找到相同的字
移動格數 = j - (-1)

壞字符表格

表格的索引值

各種可能的壞字符的ascii碼

假設壞字符只有ascii

表格的值

pattern的索引值
「pattern裡面：和壞字符相同的字」的索引值

製造壞字符表格

# 各種可能的壞字符的數量
NO_OF_CHARS = 256

def makeBadTable(pattern):
    # 建立預設值
    badTable = [-1] * NO_OF_CHARS

    # pattern長度
    patLen = len(pattern)

    # 從索引值0開始、從左往右
    # 如果pattern有兩個以上相同的字，右邊的位置優先、覆蓋已經設的值
    for i in range(patLen - 1):
        badTable[ord(pattern[i])] = i
        # 取得「pattern裡面：和壞字符相同的字」的索引值

    return badTable

使用方式

j是比對失敗位置

移動格數 = j - badTable[ord(text[i])]
移動格數有可能是負的
需要搭配好後綴規則來決定移動格數

例如：
　　ＱＱＱＡＡ３ＢＡ３
　　ＡＡ３ＢＡ３

　　ＱＱＱＡＡ３ＢＡ３
　　ＡＡ３ＢＡ３

　　ＱＱＱＡＡ３ＢＡ３
　　ＡＡ３ＢＡ３
　　比對失敗

　　ＱＱＱＡＡ３ＢＡ３
　ＡＡ３ＢＡ３
　　移動格數 -1 往左移動了

好後綴規則

好後綴

從後面往前比對

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

好後綴是２３

對齊好後綴

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３

pattern往右移動
pattern[-1]左邊的字陸續經過好後綴２３
如果這些字和好後綴相同，就可以對齊

ＱＱＱＡ２３Ｂ２３
　　　Ａ２３Ｂ２３

這是從後面往前面比對的原因

對齊的情形

完全對齊(左邊還有字 - 情況1)

ＱＱＱＡ２３Ｂ２３
Ｂ２３Ｂ２３
比對

ＱＱＱＡ２３Ｂ２３
　　　Ｂ２３Ｂ２３
移動、對齊

ＱＱＱＡ２３Ｂ２３
　　　Ｂ２３Ｂ２３
左邊還有字
左邊的字一樣，重蹈覆轍，不能對齊，就像上次一樣

完全對齊(左邊還有字 - 情況2)

ＱＱＱＡ２３Ｂ２３
Ａ２３Ｂ２３
比對

ＱＱＱＡ２３Ｂ２３
　　　Ａ２３Ｂ２３
移動、對齊

ＱＱＱＡ２３Ｂ２３
　　　Ａ２３Ｂ２３
左邊還有字
左邊的字不一樣，可以對齊

完全對齊(左邊沒有字)

ＱＱＱ２３Ｂ２３
２３Ｂ２３

ＱＱＱ２３Ｂ２３
　　　２３Ｂ２３
移動之後
左邊沒有字，不用檢查了

部份對齊

ＱＱ２３Ｂ２３
３Ｂ２３

ＱＱ２３Ｂ２３
　　　３Ｂ２３

好後綴的位置 (in pattern)

好後綴可能有許多字
以最右邊那一個字的位置，代表好後綴的位置
總是m - 1(pattern最後一個索引值)

對齊的位置

與好後綴對齊的字，可能有許多字
以最右邊那一個字的位置，代表對齊的位置

可能的對齊位置：0 到 (m - 2)

尋找的對齊位置

方法1

每個比對失敗位置 → 好後綴長度 → 每個可能對齊位置、逐一查找

方法2

每個可能對齊位置 → 它和它左邊的那些字，可以提供多少長度範圍(給好後綴對齊用) →
根據長度範圍算出比對失敗位置

如果長度範圍沒有到達最左邊(索引值0)，表示：左邊有一字比對失敗
這個位置用來「完全對齊」
只能對齊相同長度好後綴

如果長度範圍到達最左邊(索引值0)，左邊內容全部都用來對齊了
這個位置除了「完全對齊」，還可以「部份對齊」
可以對齊

  1. 相同長度好後綴 (完全對齊)
  2. 大於此長度好後綴 (部份對齊)

無論長度範圍是哪種情況
不能用來對齊小於此長度好後綴
理由：對齊的情形 → 完全對齊(左邊還有字 - 情況1)

移動格數

如果有找到對齊的位置
移動格數 = (m - 1) - 對齊的位置

如果沒有找到對齊的位置，移動pattern長度
移動格數 = (m - 1) - (-1)

好後綴表格

表格的索引值

比對失敗位置：0 到 (m-1)

表格的值

移動格數

製造好後綴表格

def makeGoodTable(pattern):
    # pattern長度
    patLen = len(pattern)

    # 建立預設值
    defaultMove = patLen     # (patLen - 1) - (-1)
    goodTable = [defaultMove] * patLen

    # 一開始就比對失敗，沒有好後綴，移動1格
    goodTable[-1] = 1

    # 好後綴位置
    good = patLen - 1
 

    # test是每一個可能對齊的位置
    # 從左到右，較右邊位置優先，覆蓋已經設的值
    for test in range(patLen - 1):
        t = test
        g = good

        while t > -1:
            if pattern[t] != pattern[g]:
                break
            t -= 1
            g -= 1

        '''
        比對失敗位置| 好後綴左端     好後綴右端
             g     |     g+1         good
                   |
             t     |     t+1         test
                   | 對齊範圍左端   對齊範圍右端
        '''

        # t有移動
        if t != test:
            goodTable[g] = good - test

            # t有移動，而且移到了最左邊
            # 可以用來部份對齊  比對失敗位置[0:g]
            if t == -1:
                goodTable[0:g] = [good - test] * g

    return goodTable

Boyer-Moore字串搜尋演算法

# 各種可能的壞字符的數量
NO_OF_CHARS = 256

def makeBadTable(pattern):
    # 建立預設值
    badTable = [-1] * NO_OF_CHARS

    # pattern長度
    patLen = len(pattern)

    # 從索引值0開始、從左往右
    # 如果pattern有兩個以上相同的字，右邊的位置優先、覆蓋已經設的值
    for i in range(patLen - 1):
        badTable[ord(pattern[i])] = i
        # 取得「pattern裡面：和壞字符相同的字」的索引值

    return badTable

def makeGoodTable(pattern):
    # pattern長度
    patLen = len(pattern)

    # 建立預設值
    defaultMove = patLen     # (patLen - 1) - (-1)
    goodTable = [defaultMove] * patLen

    # 一開始就比對失敗，沒有好後綴，移動1格
    goodTable[-1] = 1

    # 好後綴位置
    good = patLen - 1
 

    # test是每一個可能對齊的位置
    # 從左到右，較右邊位置優先，覆蓋已經設的值
    for test in range(patLen - 1):
        t = test
        g = good

        while t > -1:
            if pattern[t] != pattern[g]:
                break
            t -= 1
            g -= 1

        '''
        比對失敗位置| 好後綴左端     好後綴右端
             g     |     g+1         good
                   |
             t     |     t+1         test
                   | 對齊範圍左端   對齊範圍右端
        '''

        # t有移動
        if t != test:
            goodTable[g] = good - test

            # t有移動，而且移到了最左邊
            # 可以用來部份對齊  比對失敗位置[0:g]
            if t == -1:
                goodTable[0:g] = [good - test] * g

    return goodTable

def BM(text, pattern):
    # 長度
    n = len(text)
    m = len(pattern)

    # 尾端對齊。從後面往前面比對
    i = m - 1       # text索引值
    j = m - 1       # pattern索引值

    # 備份。比對失敗時使用。使i、j回到尾端
    i0 = i
    j0 = j

    # 製造表格
    badTable = makeBadTable(pattern)
    goodTable = makeGoodTable(pattern)

    while i < n:
        if text[i] == pattern[j]: # 比對成功
            if j == 0:
                return i
            else:
                i -= 1
                j -= 1

        else: # 比對失敗
            i = i0 + max(j - badTable[ord(text[i])], goodTable[j])
            j = j0
            i0 = i

    return -1

if __name__ == '__main__':
    # 這個版本的BM只能找ascii
    text = '49 59 69 45 55 65'
    pattern = '65'
    r = BM(text, pattern)
    print('match at %s' % r)

其他

i值的兩種使用方式

  1. text[i] == pattern[j]
  2. text[i+j] == pattern[j]

壞字符表格

理論版
badTable[比對失敗位置][ascii碼]

實際版
badTable[ascii碼]

壞字符表格的值

有三種

  1. pattern索引值(壞字符相同字所在處)
    預設值：-1

  2. 移動格數
    預設值：m
    計算方式：m - 1 - pattern索引值

  3. 移動格數 + i值回到尾端距離
    計算方式：m - 1 - pattern索引值

m - 1 - pattern索引值的意思

  1. 一開始就比對失敗的移動格數
    各種比對失敗位置的移動格數 = 一開始就比對失敗的移動格數 - (j0 - j)

  2. 不管是在哪一個位置比對失敗，就當作是一開始就比對失敗，壞字符是text[i0]
    (Boyer–Moore–Horspool algorithm)

  3. 移動格數 + i值回到尾端距離
    與text[i] == pattern[j]搭配使用

    原本：i = i0 + 移動格數
    現在：i = i + (移動格數 + i值回到尾端距離)

好後綴表格的值

有兩種

  1. 移動格數
    預設值：m

  2. 移動格數 + i值回到尾端距離
    與text[i] == pattern[j]搭配使用

    原本：i = i0 + 移動格數
    現在：i = i + (移動格數 + i值回到尾端距離)

    表格的值常常大於pattern長度

參考資料


圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22212 篇
完賽人數
600 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙