Boyer-Moore Galil Regel

Question

Ich implementierte die Boyer-Moore Algorithm für Teilstringsuche in Python, als ich über die Galil Rule erfuhr. Ich habe mich online nach der Galil-Regel umgeschaut, aber ich habe nicht mehr als ein paar Sätze gefunden, und ich bekomme keinen Zugang zu der Originalarbeit. Wie kann ich dies in meinen aktuellen Algorithmus implementieren?

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 

Hinweise:

• Offsets [c] = -1, wenn c nicht in dem Muster
• Offsets [c] = letzten Index von c im Muster

Beispiel: aaabcb

• Offsets [a] = 2
• Offsets [b] = 5
• Offsets [c] = 4
• Offsets [d] = -1

Die wenigen Sätze ich gefunden habe, haben gesagt, im Auge zu behalten, wenn das erste Mismatch tritt in meiner inneren Schleife auf (j, wenn die if-Anweisung in der inneren Schleife True ist) und in der Position, in der ich die Vergleiche gestartet habe (i + j, in meinem Fall). Ich verstehe die Intuition, dass ich bereits alle Indizes zwischen diesen überprüft habe, also sollte ich diese Vergleiche nicht noch einmal machen müssen. Ich verstehe einfach nicht, wie man die Punkte verbindet und zu einer Implementierung gelangt.

Answer 1

Bei der Galil-Regel wird die Periodizität im Muster ausgenutzt, um Vergleiche zu vermeiden. Angenommen, Sie haben ein Muster abcabcab. Es ist periodisch mit der kleinsten Periode abc. Im Allgemeinen ist ein Muster P periodisch, wenn es eine Zeichenkette U gibt, so dass P ein Präfix von UUUUU... ist. (Im obigen Beispiel ist abcabcab eindeutig ein Präfix der sich wiederholenden Zeichenfolge abc = U.) Wir nennen die kürzeste solche Zeichenfolge die Periode P. Die Länge dieses Zeitraums sei k (im obigen Beispiel k = 3 seit U = abc).

Beachten Sie zunächst, dass die Galil-Regel gilt nur, nachdem Sie eine Vorkommen von P im Text gefunden haben. Wenn Sie das tun, besagt die Galil-Regel, dass Sie nach k (die Periodizität des Musters) verschieben können und Sie nur die letzten k Zeichen des jetzt verschobenen Musters vergleichen müssen, um festzustellen, ob es eine Übereinstimmung gab.

Hier ist ein Beispiel:

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

Erstes Auftreten: b[ababa]babab. Jetzt können Sie verschieben, indem k = 2 und Sie nur die letzten zwei Zeichen des Musters zu überprüfen:

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

Der Rest Pmuss Spiel seit P periodisch ist und Sie verschoben es durch seine Periode kvon einem existierende Übereinstimmung (das ist entscheidend), so dass die sich wiederholenden Teile werden gut in Einklang gebracht.

Wenn Sie ein anderes Spiel gefunden haben, wiederholen Sie es einfach. Wenn Sie jedoch eine Abweichung feststellen, kehren Sie zum Standard-Boyer-Moore-Algorithmus zurück, bis Sie eine andere Übereinstimmung gefunden haben. Denken Sie daran, dass Sie die Galil-Regel nur verwenden können, wenn Sie eine Übereinstimmung und finden, die Sie um k verschieben (andernfalls stimmt das Muster nicht mit dem vorherigen Vorkommen überein).

Nun könnten Sie sich fragen, wie Sie k für ein gegebenes Muster P bestimmen können. Sie müssen zuerst das Suffix-Array N berechnen, wobei N[i] die Länge des längsten gemeinsamen Suffix des Präfix P[0, i] und P ist. (Sie können das Suffixarray berechnen, indem Sie das Präfixarray Z auf dem Reverse von P mit dem Z-Algorithmus berechnen, wie zum Beispiel here beschrieben.) Sobald Sie das Suffix-Array haben, können Sie leicht k finden, da es sein wird die kleinste k > 0 so, dass N[m - k - 1] == m - k (wo m = |P|).

Zum Beispiel:

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