【字元串處理Python實作】字元串模式比對之暴力、BM算法簡介與實作

文章目錄

• 一、暴力比對算法
• • 1. 介紹
  • 2. 實作
  • 3. 複雜度
• 二、Boyer-Moore算法
• • 1. 介紹
  • 2. 實作

字元串模式比對是字元串進行中的一類經典問題，即給定長度為 n n n的字元串

text

以及長度為 m m m的模式串

pattern

，期望先确定

pattern

是否為

text

的一個子串，如果是，則傳回

text

中

pattern

開始的最小索引

j

，使得

text[j:j+m]

等于

pattern

，或者傳回所有滿足條件的索引。

實際上，在Python内置的

str

子產品中，

t.find(p)

、

t.index(p)

、

t.count(p)

以及

t.partition(p)

、

t.split(p)

、

t.replace(p, q)

等方法的實作都依賴于字元串的模式比對。

本文将分别介紹并實作兩種種常見的字元串模式比對算法：暴力算法、BM算法（Boyer-Moore）。

一、暴力比對算法

1. 介紹

暴力比對法是最直覺的一種字元串模式比對算法，這種方法的主要思想是先枚舉出所有可能的情況，然後找出符合要求的結果。具體地，将模式串

pattern

從索引為 0 的位置依次和

text

索引在 0 、1 、2 直到 n − m n-m n−m 的索引處進行對齊，然後疊代 m m m 次判斷是否可以在

text

中找出和

pattern

比對的子串。

2. 實作

下面給出暴力法實作字元串模式比對的具體代碼：

def find_brute(text, pattern):
    """如果子串pattern存在text中，則傳回pattern在text中起始位置索引，否則傳回-1"""
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):  # 從索引0至n - m處依次嘗試開始比對
        k = 0
        while k < m and text[i + k] == pattern[k]:  # 第k個字元比對
            k += 1
        if k == m:  # 判斷此輪for循環是否成功比對
            return i  # 子串text[i:i + m]和pattern比對
    return -1

           

3. 複雜度

如暴力法的思想和實作一樣，其時間複雜度分析同樣直覺。該算法包括兩個嵌套的循環，外層循環依次疊代每個可能的子串起始索引，内層循環判斷此次外層循環的疊代是否成功比對。顯然，在最壞的情況下，外層循環最多執行 n − m + 1 n-m+1 n−m+1 次，内層循環最多執行 m m m 次，是以該方法的最壞時間複雜度為 O ( n m ) O(nm) O(nm) 。

二、Boyer-Moore算法

1. 介紹

上述暴力比對算法雖然直覺，但是在最壞情況下，需要在窮舉

text

的所有可能子串，然後和模式串

pattern

逐字元比對，是以效率較低。下面将介紹的 Boyer-Moore（BM）算法則可以跳過

pattern

和

text

的子串比對時相當部分的字元。該方法主要基于下列兩個手段：

• 鏡像試探

  ：在将模式串

  pattern

  和

  text

  的某子串進行比對時，從右到左進行比較，而不是從左到右（這也是這裡鏡像二字的含義）；

• 字元跳躍試探

  ：在将模式串

  pattern

  和

  text

  的某子串進行比對時，當該子串中某字元

  text[i]=c

  和模式串對應位置字元

  pattern[k]

  不比對時，根據兩種不同情況，分别做如下操作：
  • 如果字元

    text[i]=c

    不在模式串

    pattern

    中，則将模式串

    pattern

    向右整體移過

    text[i]

    所在位置；
  • 如果字元

    text[i]=c

    在模式串

    pattern

    中，為確定不漏掉可能成功比對的情況，隻能将模式串

    pattern

    整體向右移動，直到

    pattern

    中的最後一次1出現的字元

    c

    和

    text[i]

    對齊。

為便于讀者了解，結合下圖對上述兩個過程進行詳細解釋：

• 一開始，模式串

  'sushi'

  和

  text

  在最左側對齊，然後将二者從右往左進行比對；
• 接着，由于

  text

  中的字元

  'e'

  和模式串對應位置的字元

  'i'

  不比對，且字元

  'e'

  不在模式串

  'sushi'

  中，是以将模式串整體向右移過字元

  'e'

  處；
• 然後，繼續将模式串和

  text

  從右往左進行比對，雖然此時

  text

  中的字元

  's'

  和模式串對應位置字元

  'i'

  不比對，但是字元

  's'

  包含在模式串中，是以将模式串向右移動，直到模式串中右起第一個

  's'

  字元和

  text

  中的該字元對齊。

上圖僅描繪了當

pattern

的最後一個字元和

text

對應位置字元不比對時應該進行的操作。一般地，當二者比對時，此時算法會接着從

pattern

的倒數第二個字元開始，嘗試繼續擴大發生比對的字元數。此過程會一直繼續，直到整個

pattern

成功比對或發生某個字元不比對。

如果在上述繼續擴大發生比對字元數的過程中确實發生某字元不比對，則需要根據下列兩種情況做不同處理：

• 如果

  text

  中目前不比對的字元不存在

  pattern

  中，則類似上圖，将模式串

  pattern

  整體移過該字元；
• 如果

  text

  中目前不比對的字元（假設此時

  text

  該位置為

  'a'

  ，

  pattern

  的該位置為

  'b'

  ）存在

  pattern

  中，則根據

  text

  中字元

  'a'

  最後一次出現在

  pattern

  中的位置，分别做如下處理：
  • 如果在

    pattern

    中，字元

    'a'

    最後一次出現的位置在字元

    'b'

    之前，則向右整體移動

    pattern

    ，使得二者在字元

    'a'

    處對齊；
  • 如果在

    pattern

    中，字元

    'a'

    最後一次出現的位置在字元

    'b'

    之後，則向右整體移動

    pattern

    一個字元。

為便于後續的編碼實作，下面結合示意圖對上述兩種情況進行量化分析：

為便于分析，下圖2中的索引

i

，

k

，

j

的含義分别為：

• i

  ：表示繼續擴大比對字元數的過程中，比對失敗的字元

  'a'

  在

  text

  中的索引；

• k

  ：表示和上述字元

  'a'

  對齊的字元（此處為

  'b'

  ）在

  pattern

  中的索引；

• j

  ：表示

  pattern

  中最後一次出現的字元

  'a'

  的在

  pattern

  中的索引。

是以：

• 當 j < k j\lt{k} j<k ，即

  pattern

  中字元

  'a'

  最後一次出現的位置在字元

  'b'

  之前，則将

  pattern

  整體向右移動 k − j k-j k−j 個字元，此時索引

  i

  需遞增 ( k − j ) + ( m − 1 − k ) = m − ( j + 1 ) (k-j)+(m-1-k)=m-(j+1) (k−j)+(m−1−k)=m−(j+1) ；
• 當 j > k j\gt{k} j>k ，即

  pattern

  中字元

  'a'

  最後一次出現的位置在字元

  'b'

  之後，則将

  pattern

  整體向右移動1個字元，此時索引

  i

  需遞增 1 + ( m − 1 − k ) = m − k 1+(m-1-k)=m-k 1+(m−1−k)=m−k 。

在實作字元串比對的 BM 算法之前，為了使讀者對上述一系列分析有一個集中的直覺了解，下面給出通過BM 算法以模式串

pattern = 'abacab'

比對字元串

text = 'abacaabadcabacabaabb'

的詳細過程：

• pattern

  處于第一個位置時，由于第一次即發生不比對，且字元

  'a'

  存在

  pattern

  中，将

  pattern

  向右平移一個字元到達第二個位置，累計進行了 1 次比對操作；

• pattern

  處于第二個位置時，直到累計發生的第 4 次比對才出現不比對現象，由于此時

  text

  中和目前位置

  pattern

  中字元

  'c'

  對齊的字元

  'a'

  在

  pattern

  中， 且

  pattern

  中最後一個

  'a'

  在字元

  'c'

  後面，則将

  pattern

  整體向右移動一個字元；

• pattern

  處于第三個位置時，發生第 5 次比對操作，此時過程和

  pattern

  處于第一個位置的情況類似；

• pattern

  處于第四個位置時，發生第 6 次比對操作，由于此時

  text

  中的字元

  'd'

  不在

  pattern

  中，是以将

  pattern

  整體移過字元

  'd'

  ；

• pattern

  處于第五個位置時，發生第 7 次比對操作，此時此時過程和

  pattern

  處于第一、三個位置的情況類似；

• pattern

  處于第六個位置時，發生第8、9、10、11、12、13比對，最終比對成功。

2. 實作

下面是基于BM算法實作的字元串比對：

def find_boyer_moore(text, pattern):
    """如果模式串pattern存在text中，則傳回pattern在text中起始位置索引，否則傳回-1"""
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    last = {}
    for k in range(m):  # 以pattern中字元為鍵索引為值建立字典
        last[pattern[k]] = k
    # 初始化索引輔助變量，使得pattern最右側字元和text索引m - 1處對齊
    i = m - 1
    k = m - 1
    while i < n:
        if text[i] == pattern[k]:
            if k == 0:  # 判斷是否連續完成了len(pattern)次成功比對
                return i  # 成功将pattern和text某子串進行比對後，text中和pattern相同的子串起始于索引i
            else:  # 繼續從右向左比對pattern和text對齊位置字元相同
                i -= 1
                k -= 1
        else:
            j = last.get(text[i], -1)
            if j < k:  # text[i]不存在pattern中即j = -1時，該條件及其操作依然成立
                i += m - (j + 1)
            if j > k:
                i += m - k
            k = m - 1  # 重新從右開始對pattern和text進行比對
    return -1


if __name__ == '__main__':
    text = 'qwertyqazxswedcvfrtgb'
    pattern = 'zx'
    print(find_boyer_moore(text, pattern))  # 8
           

1. 字元串中字元從左到右排列，如一個字元出現次數大于等于1，則位于最右側的該字元被視為最後一次出現。 ↩︎
2. 需要注意的是，圖中僅示意在發生此次不比對前，

   pattern

   和

   text

   在目前位置僅有最後一個字元發生比對。實際上，圖中的情形具有一般性，即适用于所有已發生小于 m m m 個字元比對的情況。 ↩︎