Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Textsuche: Knuth-Morris-Pratt-Algorithmus

Bild

Du suchst ein Muster pp der Länge mm in einem Text tt der Länge nn, wobei mnm \ll n.

Mit dem naiven Algorithmus probierst du an jeder Stelle des Textes aus, ob das Muster dort übereinstimmt. Dies dauert im schlechtesten Fall mnm \cdot n Schritte, etwa wenn das Muster aaaab und der Text aaaa…aaaaab lautet.

Der naive Algorithmus führt viele überflüssige Vergleiche durch. Der Knuth-Morris-Pratt-Algorithmus dagegen untersucht vorher in mm Schritten die Struktur des Musters, sodass er für die Suche anschließend nur noch nn Schritte benötigt.

Spielend einfach erklärt

Du verstehst den Knuth-Morris-Pratt-Algorithmus am besten, wenn du ihn als eine Art "Mensch-ärgere-dich-nicht-Spiel" betrachtest.

Aus beispielsweise dem Muster pp = ababaa leitest du direkt das folgende "Spielfeld" ab.

Bild

Spielregeln

Der erste Spielstein steht auf dem Startfeld 0. Nun wird reihum gewürfelt, mit einem Würfel, der mit Buchstaben beschriftet ist.

Bild

Ein Spieler, der ein a würfelt, darf den Spielstein auf Feld 1 "herausbringen". Gleichzeitig wird ein neuer Spielstein auf Feld 0 gestellt.

Bild

Der grüne Spielstein bleibt von nun an im Spiel, solange ein Buchstabe gewürfelt wird, mit dem er weiterrücken kann. Wenn also als nächstes ein b gewürfelt wird, darf er auf Feld 2 weiterrücken. Wenn danach ein a gewürfelt wird, darf er auf Feld 3 weiterrücken – und der Spieler, der das a gewürfelt hat, darf den gelben Spielstein auf Feld 1 herausbringen. Gleichzeitig wird ein neuer Spielstein auf Feld 0 gestellt.

Die folgende Abbildung zeigt die Spielsituation, nachdem die Buchstabenfolge aba gewürfelt worden ist.

Bild

Wenn danach erneut ein a gewürfelt wird, "fliegen" alle Spielsteine "raus", die mit dem a nicht weiterrücken können, also hier der gelbe und der grüne, sie werden vom Spielfeld entfernt. Jedoch darf der Spieler, der das a gewürfelt hat, den roten Spielstein auf Feld 1 herausbringen, und gleichzeitig wird ein neuer Spielstein auf Feld 0 gestellt.

So geht es die ganze Zeit weiter. Wird irgendwann im Verlauf des Spiels die Buchstabenfolge pp = ababaa gewürfelt, so erreicht ein Spieler mit seinem Spielstein das Zielfeld 6 und hat "gewonnen"! Das Spiel ist dann aber nicht vorbei, sondern es wird weiter gewürfelt, sodass andere Spieler auch noch "gewinnen" können.

Algorithmische Umsetzung

Tatsächlich werden die Buchstaben nicht gewürfelt, sondern die Buchstabenfolge ist der Text tt, in welchem die Vorkommen des Musters pp gesucht werden. Wenn ein Spieler "gewinnt", so ist ein Vorkommen des Musters im Text gefunden.

Wenn du den Knuth-Morris-Pratt-Algorithmus ausführst, simulierst du dieses Spiel. Der Clou dabei:

Du spielst nur mit dem am weitesten nach rechts fortgerückten Spielstein!

Du schaust jeweils, ob du diesen Spielstein mit dem nächsten Zeichen des Textes weiterziehen kannst.

  • Wenn ja, dann ziehst du ihn weiter.

  • Wenn nein, dann entfernst du ihn und spielst mit dem nächstfolgenden Spielstein weiter – wo dieser steht, schlägst du in einer sogenannten Fallback-Tabelle nach.

Es kann sein, dass du auch diesen nächstfolgenden Spielstein mit dem Zeichen des Textes nicht weiterziehen kannst. Dann entfernst du ihn und spielst mit dem als nächsten folgenden Spielstein weiter. Wo dieser steht, entnimmst du wieder der Fallback-Tabelle. Und so weiter.

Spätestens beim Feld 0 endet dieses Zurückfallen auf nächstfolgende Spielsteine. Auf Feld 0 steht immer ein Spielstein. Wenn du mit diesem nicht weiterziehen kannst, entfernst du ihn und stellst sofort wieder einen neuen Spielstein dorthin. Dann kommt das nächste Zeichen des Textes dran.

Zeitkomplexität

Du brauchst also nicht bei jedem Zeichen des Textes alle Spielsteine zu aktualisieren, sondern immer nur einen. Auf diese Weise benötigst du nur höchstens proportional zu nn viele Schritte, wobei nn die Länge des Textes tt ist.

Denn mit jedem der nn Zeichen des Textes rückst du einen Spielstein weiter, dies sind nn Schritte. Das gelegentliche Nachschlagen in der Fallback-Tabelle kostet zusammengenommen höchstens nn zusätzliche Schritte. Insgesamt sind dies also höchstens 2n2n Schritte.

Programm

Die folgende Funktion kmpSearch in der Programmiersprache Python implementiert das Verfahren. Die Indexposition ii zeigt auf das jeweilige Zeichen des Textes, jj zeigt auf das jeweilige Zeichen des Musters.

# Textsuche mit dem Knuth-Morris-Pratt-Algorithmus
def kmpSearch():
    # Muster p, Text t, Länge des Musters m, Länge des Textes n,
    # Fallback-Tabelle f
    global p, t, m, n, f
    i=0
    j=0
    while i<n:
        while j>=0 and p[j]!=t[i]:   # Mismatch, j kann nicht weiter
            j=f[j]   # Fallback
        i+=1
        j+=1
        if (j==m):   # Vorkommen gefunden
            report(i-j)
            j=f[j]    # j kann nicht weiter: Fallback

Verschiebung des Musters

Wenn der Index jj auf einen kleineren Wert f[j]f[j] zurückfällt, entspricht dies einer Verschiebung des Musters nach rechts um jf[j]j-f[j] Positionen, zum Beispiel

a b a b a b a a b b a a …

a b a b a a

__ a b a b a a

________a b a b a a

Hier kommt es bei i=5i= 5 und j=5j=5 zu einem Mismatch. Daraufhin wird j=f[5]=3j=f[5] = 3 gesetzt. Das Muster wird um 53=25-3 = 2 Positionen nach rechts geschoben, und es wird bei i=6i=6 und j=4j=4 weiterverglichen. Bei i=8i=8 und j=6j=6 wird ein Vorkommen des Musters gefunden und daraufhin j=f[6]=1j = f[6]=1 gesetzt. Das Muster wird daraufhin um 61=56-1 = 5 Positionen nach rechts geschoben, usw.

Fallback-Tabelle berechnen

Jetzt brauchst du nur noch die Fallback-Tabelle zu berechnen.

Die Einträge der Fallback-Tabelle hängen nur vom Muster ab, nicht vom Text!

Wenn also zum Beispiel wie in der Abbildung der grüne Spielstein bis zum Feld 3 gekommen ist, dann steht zwangsläufig auf Feld 1 auch ein Spielstein. Das Fallback-Feld von Feld 3 ist somit das Feld 1. In der Fallback-Tabelle ff steht f[3]=1f[3]=1.

Die Fallback-Tabelle berechnest du in einem Vorlauf aus dem Muster. Hierzu verwendest du wieder das Spielfeld wie eben. Das Eingabewort ist diesmal das Muster selber, also hier im Beispiel p=p=ababaa.

Mit zwei Variablen ii und jj führst du dabei Buch über die Felder, auf denen der am weitesten und der am zweitweitesten fortgerückte Spielstein steht.

Das Feld ii ist jeweils das aktuelle Feld, das Feld jj ist das zugehörige Fallback-Feld. Zu jedem jeweils aktuellen Feld ii trägst du das zugehörige Fallback-Feld jj in die Fallback-Tabelle ff ein: f[i]=jf[i]=j.

Da du das Muster selber als Eingabewort eingibst, kann der erste Spielstein bei jedem Zeichen weiterrücken; der zweite Spielstein fällt dagegen gelegentlich gemäß der schon berechneten Einträge der Fallback-Tabelle zurück.

Du beginnst mit dem Feld i=0i=0. Als Initialisierung trägst du f[0]=1f[0]=-1 in die Fallback-Tabelle ein.

Programm

Die folgende Funktion kmpPreprocess berechnet aus dem Muster die Fallback-Tabelle ff.

def kmpPreprocess():
    global p, t, m, n, f
    i=0
    j=-1
    f[i]=j
    while i<m:
        while j>=0 and p[j]!=p[i]:    # j kann nicht weiter
            j=f[j]   # fallback
        i+=1
        j+=1
        f[i]=j

Ganz entsprechend wie die Suchfunktion kmpSearch benötigt die Funktion kmpPreprocess höchstens 2m2m Schritte.

Die Funktion kmpPreprocess berechnet die Einträge der Fallback-Tabelle und greift dabei auf schon berechnete, gespeicherte Einträge zurück. Dieses Vorgehen ist ein schönes Beispiel für die algorithmische Technik der dynamischen Programmierung.

Hauptprogramm

Im Hauptprogramm legst du zunächst das Muster pp fest und rufst dann den Vorlauf kmpPreprocess auf, um die Fallback-Tabelle zu berechnen. Danach legst du den Text tt fest und rufst den Suchalgorithmus kmpSearch auf.

if __name__=="__main__":
    p="ababaa"
    m=len(p)
    f=(m+1)*[0]    # Fallback-Tabelle f mit Nullen vorbesetzen 
    kmpPreprocess()
    print(f)
    t="ababababaababaa"
    n=len(t)
    print(t)
    kmpSearch()

Die Funktion report implementierst du wie beim naiven Algorithmus.

def report(i):
    print(i*" " + p)

Die entsprechende Ausgabe zeigt dir dann die Positionen, an denen das Muster im Text vorkommt.

a b a b a b a b a a b a b a a

____ a b a b a a

__________a b a b a a

Probiere das Programm einmal mit unterschiedlichen Texten und Mustern aus!


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0.Was bedeutet das?