Boyer-Moore Galil規則

當我瞭解到Galil Rule時，我正在實施Boyer-Moore Algorithm用於Python中的子字符串搜索。我在網上查了一下Galil規則，但我沒有發現任何東西，只有幾句話，我無法訪問原始論文。我怎樣才能將其實現到我目前的算法？Boyer-Moore Galil規則

i = 0 
while i < (N - M + 1): 
    skip = 0 
    for j in reversed(range(0, M)): 
     if pattern[j] != text[i + j]: 
      skip = max(1, j - offsets[text[i+j]]) 
      break 
    if skip == 0: 
     return i 
    i += skip 
return -1

注：

偏移並[c] = -1如果c不在圖案
偏移並[c]在圖案

的C =最後一個索引示例： aaabcb

偏移[a] = 2個
偏移並[b] = 5
偏移並[c] = 4個
偏移並[d] = -1

我發現的幾個句子所說保持跟蹤，當第一在我的內部循環（j，如果內部循環內的if語句爲True）和我開始比較的位置（在我的情況下爲i + j）中發生不匹配。我理解我已經檢查過所有這些指數的直覺，所以我不應該再次進行這些比較。我只是不明白如何連接點並達成實現。

來源

2016-07-05 lorenzocastillo

http://thirdworld.nl/on-improving-the-worst-case-running-time-of-the-boyer-moore-string-matching-algorithm –

Galil規則是關於利用模式中的週期性來減少比較。假設你有一個模式abcabcab。這是週期最小的期間abc。一般來說，如果有一個字符串U，P是P的格式是P是UUUUU...的前綴。（在上例中，abcabcab顯然是重複字符串abc = U的前綴。）我們稱之爲最短的這樣的字符串，其時間段爲P。假設該時間段的長度爲k（在k = 3以上的示例中，自U = abc起）。

首先，請記住，在您發現文本中出現P之後，Galil規則適用僅限於。當你這樣做時，加利爾規則說你可以移動k（模式的週期性），你只需要比較現在移動模式的最後k字符來確定是否匹配。

下面是一個例子：

P = ababa 
T = bababababab 
U = ab 
k = 2

第一次出現：b[ababa]babab。現在，您可以通過k = 2轉移，你只需要檢查花樣的最後兩個字符：

T = bababa[ba]bab 
P = aba[ba]  // Only need to compare chars inside brackets for next match.

的P必須比賽，因爲P中的其餘部分是週期性的，你從一個轉向它通過其週期k現有的匹配（這是至關重要的），所以重複的部分將很好地排隊。

如果你找到了另一個匹配，只需重複。但是，如果發現不匹配，則可以恢復爲標準Boyer-Moore算法，直到找到另一匹配。請記住，只有當您找到和的匹配項時，您才能使用Galil規則，您將移動k（否則該模式不能保證與前一次匹配）。

現在，您可能會想知道，如何確定k對於給定模式P。您需要首先計算後綴數組N，其中N[i]將是前綴P[0, i]和P的最長公共後綴的長度。（通過使用Z算法計算前綴數組，使用Z算法計算反向的P的前綴數組），一旦你有了後綴數組，你可以很容易地找到k，因爲它會是最小的k > 0這樣N[m - k - 1] == m - k（其中m = |P|）。

例如：

P = ababa 
m = 5 
N = [1, 0, 3, 0, 5] 
k = 2 because N[m - k - 1] == N[5 - 2 - 1] == N[2] == 3 == 5 - k

來源

2016-11-08 01:02:45

Boyer-Moore Galil規則

回答

相關問題