Boyer-Moore Galil Rule

Question

私はGalil Ruleについて学んだときに、Pythonで部分文字列検索のためにBoyer-Moore Algorithmを実装していました。私はガリルルールのためにオンラインを見回しましたが、何種類もの文章が見つかりませんでした。元の論文にアクセスできません。これを現在のアルゴリズムに実装するにはどうすればよいですか？

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

• offsets [a] = 2つの
• オフセット[B] = 5
• オフセット[C] = 4つの
• オフセット[D] = -1

私は発見したいくつかの文章はときに最初のトラックを維持すると述べています私の内部ループ（内側ループ内のif文がTrueの場合はj）と比較を開始した位置（私の場合はi + j）で不一致が発生します。私はそれらの間のすべての指標を既にチェックしているという直感を理解しているので、再びその比較を行う必要はありません。私はちょうどドットを接続し、実装に到達する方法を理解していない。

Answer 1

ガリルルールは、パターンの周期性を利用して比較を減らすことです。パターンabcabcabがあるとします。最小期間は、abcで定期的です。一般に、パターンPは、文字列Uがあり、Pという接頭辞がUUUUU...である場合、定期的です。 （上記の例では、abcabcabは明らかに繰り返し文字列abc = Uの接頭辞です。）この文字列の最短文字列をPと呼びます。その期間の長さはk（上記の例ではk = 3からU = abcまで）です。

最初にギャリルのルールは、テキストにPの出現が見つかった後にのみを適用することに注意してください。そうすると、ギャリルルールはk（パターンの周期性）でシフトできると言っています。一致したかどうかを判断するために、今シフトされたパターンの最後のk文字を比較するだけです。

ここでは例です：

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

最初に出現した：b[ababa]babab。今、あなたはk = 2だけシフトすることができますし、あなただけのパターンの最後の2つの文字をチェックする必要があります。

は

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

P以来P必要試合の残りの部分は周期的であり、あなたからその期間kことによってそれをシフトします既存の一致（これは重要です）ので、繰り返し部分がうまく整列します。

もう一度一致するものが見つかった場合は、繰り返してください。しかし、不一致が見つかった場合、別の一致が見つかるまで標準のBoyer-Mooreアルゴリズムに戻ります。 ととの一致が見つかった場合は、kでシフトするだけです（パターンが前のオカレンスと一致するとは限りません）。

ここで、与えられたパターンPのためにkを決定する方法が不思議に思うかもしれません。接尾辞配列Nを最初に計算する必要があります。N[i]は接頭辞P[0, i]とPの最長共通接尾辞の長さになります。 （たとえば、hereのようにZアルゴリズムを使用して、の逆の接頭辞配列Zを計算することで接尾辞配列を計算できます）。最も小さいものはk > 0N[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