Textsuche

Knuth-Morris-Pratt-Algorithmus

 English version  aufwärts

Idee

Der naive Algorithmus hat den Nachteil, dass er bei einem Mismatch alle Zeichen, die bis dahin schon überein­gestimmt haben, wieder vergisst und von vorne anfängt zu vergleichen. Auf diese Weise kommt seine Komplexität von Θ(n·m) Vergleichen im schlechtesten Fall zustande (n: Länge des Textes, m: Länge des Musters).

Der Algorithmus von Knuth, Morris und Pratt [KMP 77] nutzt die bei Über­ein­stimmung von Zeichen gewonnene Information aus. So brauchen die Zeichen nach einem Mismatch nicht noch einmal alle wieder von vorn verglichen zu werden. Im Ergebnis benötigt der Algorithmus in der Suchphase nur noch O(n) Vergleiche.

In einem Vorlauf (preprocessing) analysiert der Algorithmus zunächst das Muster und speichert Information über seine Struktur in einem Array der Länge m. Die Vorlaufphase lässt sich in Zeit O(m) durchführen. Da mkleiner gleichn, hat der gesamte Algorithmus eine Komplexität von O(n).

Das Verfahren lässt sich auch als Simulation eines speziellen nicht­deterministischen endlichen Automaten, eines String-Matching-Automaten, auf­fassen.

Grundlagen

Definition:  Sei A ein Alphabet und  x = x0 ... xk-1,  k Element natürliche Zahlen   ein Wort der Länge k über A.

 

Ein Präfix von x ist ein Teilwort u mit

u  =  x0 ... xb-1   wobei  b Element {0, ..., k},

also ein Anfangswort der Länge b von x.

 

Ein Suffix von x ist ein Teilwort u mit

u  =  xk-b ... xk-1   wobei  b Element {0, ..., k},

also ein Endwort der Länge b von x.

 

Ein Präfix u von x bzw. ein Suffix u von x heißt echt, wenn u ≠ x ist, d.h. wenn die Länge b<k ist.

 

Ein Rand von x ist ein Teilwort r mit

r  =  x0 ... xb-1  und  r  =  xk-b ... xk-1

wobei  b Element {0, ..., k-1}

 

Ein Rand von x ist also ein Wort, das gleichzeitig echtes Präfix und echtes Suffix von x ist.

Die Länge b wird als die Breite des Randes r bezeichnet.

Beispiel:  Sei x = abacab. Die echten Präfixe von x sind

ε, a, ab, aba, abac, abaca.

 

Die echten Suffixe von x sind

ε, b, ab, cab, acab, bacab.

 

Ränder von x sind

ε, ab.

 

Der Rand ab hat die Breite 2.

Stets ist das leere Wort ε ein Rand von xx Element A+. Lediglich ε selbst hat keinen Rand.

In folgendem Beispiel wird deutlich, wie mithilfe des Begriffes "Rand" die Schiebe­distanz beim Knuth-Morris-Pratt-Algorithmus ermittelt wird.

Beispiel:  

0123456789...
abcabcabd
abcabd
abcabd

Die Zeichen an den Positionen 0, ..., 4 haben überein­gestimmt. Der Vergleich c-d an Position 5 ergibt einen Mismatch. Das Muster kann bis Position 3 weiter­geschoben werden, und der Vergleich wird ab Position 5 des Textes fortgesetzt.

Die Schiebe­distanz richtet sich nach dem breitesten Rand des über­einstimmenden Präfixes des Musters. In diesem Beispiel ist das über­einstimmende Präfix abcab; es hat die Länge j = 5. Sein breitester Rand ist ab mit der Breite b = 2. Die Schiebe­distanz beträgt j – b  =  5 – 2  =  3.

Die im Vorlauf zu gewinnende Information besteht also darin, für jedes Präfix des Musters die Länge seines breitesten Randes zu bestimmen.

Vorlauf

Satz:  Seien r, s Ränder eines Wortes x, wobei |r| < |s|. Dann ist r ein Rand von s.

Beweis:  Bild 1 zeigt schematisch das Wort x mit den Rändern r und s. Als Rand von x ist r Präfix von x und damit, weil kürzer als s, auch echtes Präfix von s. Aber r ist auch Suffix von x und damit echtes Suffix von s. Also ist r Rand von s.

Bild 1: Ränder r, s eines Wortes x
Bild 1: Ränder r, s eines Wortes x

Ist s der breiteste Rand von x, so ergibt sich der nächst­schmalere Rand r von x als breitester Rand von s usw.

 

Definition:  Sei x ein Wort und a Element A ein Zeichen. Ein Rand r von x lässt sich durch a fortsetzen, wenn ra Rand von xa ist.

Bild 2: Fortsetzung eines Randes
Bild 2: Fortsetzung eines Randes

Anhand von Bild 2 ist zu sehen, dass sich ein Rand r der Breite j von x durch a fortsetzen lässt, wenn xj = a ist.

 

In der Vorlaufphase wird ein Array b der Länge m+1 berechnet. Der Eintrag b[i] enthält für jedes Präfix der Länge i des Musters die Breite seines breitesten Randes (i = 0, ..., m). Das Präfix ε der Länge i = 0 hat keinen Rand; daher wird b[0] = -1 gesetzt.

Bild 3: Präfix der Länge i des Musters mit Rand der Breite b[i]
Bild 3: Präfix der Länge i des Musters mit Rand der Breite b[i]

Sind die Werte b[0], ..., b[i] bereits bekannt, so ergibt sich der Wert b[i+1], indem geprüft wird, ob sich ein Rand des Präfixes p0 ... pi-1 durch pi fortsetzen lässt. Dies ist der Fall, wenn pb[i] = pi ist (Bild 3). Die zu prüfenden Ränder ergeben sich nach obigem Satz in absteigender Breite aus den Werten b[i], b[b[i]] usw.

Der Vorlauf­algorithmus enthält daher eine Schleife, die diese Werte durchläuft. Ein Rand der Breite j lässt sich durch pi fortsetzen, wenn pj = pi ist. Wenn nicht, wird j = b[j] gesetzt und damit der nächst­schmalere Rand geprüft. Die Schleife endet spätestens, wenn sich kein Rand fortsetzen lässt (j = -1).

Nach Erhöhung von j durch die Anweisung j++ enthält j in jedem Fall die Breite des breitesten Randes von p0 ... pi. Dieser Wert wird in b[i+1] eingetragen (in b[i] nach Erhöhung von i durch die Anweisung i++).

 

Vorlauf­algorithmus
void kmpPreprocess()
{
    int i=0, j=-1;
    b[i]=j;
    while (i<m)
    {
        while (j>=0 && p[i]!=p[j]) j=b[j];
        i++; j++;
        b[i]=j;
    }
}

Beispiel:  Für das Muster p = ababaa ergeben sich die Randbreiten im Array b wie folgt. Beispiels­weise ist b[5] = 3, weil das Präfix ababa der Länge 5 einen Rand der Breite 3 hat.

j:0123456
p[j]:ababaa
b[j]:-1001231

Suchalgorithmus

Konzeptionell könnte der obige Vorlauf­algorithmus statt auf p auf das Wort pt angewendet werden. Wenn nur Ränder bis zur maximalen Breite m berechnet werden, so entspricht ein Rand der Breite m eines Präfixes x von pt einem Vorkommen des Musters in t, wenn der Rand sich nicht über­schneidet (Bild 4).

Bild 4: Rand der Länge m eines Präfixes x von pt
Bild 4: Rand der Länge m eines Präfixes x von pt

Hierdurch ist die große Ähnlichkeit des folgenden Such­algorithmus mit dem Vorlauf­algorithmus zu erklären.

 

Knuth-Morris-Pratt-Such­algorithmus
void kmpSearch()
{
    int i=0, j=0;
    while (i<n)
    {
        while (j>=0 && t[i]!=p[j]) j=b[j];
        i++; j++;
        if (j==m)
        {
            report(i-j);
            j=b[j];
        }
    }
}

 

In der inneren While-Schleife wird bei einem Mismatch an Position j der breiteste Rand des über­einstimmenden Präfixes des Musters betrachtet (Bild 5). Dieser hat die Breite b[j]. Indem an Position b[j] weiter­verglichen wird, ergibt sich eine neue Ausrichtung des Musters. Diese berück­sichtigt somit das breiteste Präfix des Musters, das bereits überein­gestimmt hat. Die While-Schleife wird solange durchlaufen, bis Über­ein­stimmung vorliegt oder kein Rand mehr vorhanden ist (j = -1).

Bild 5: Verschieben des Musters bei einem Mismatch an Position j
Bild 5: Verschieben des Musters bei einem Mismatch an Position j

Wenn alle m Zeichen des Musters mit dem ent­sprechenden Textfenster überein­gestimmt haben (j = m), wird durch die Funktion report(i-j) die Position des Vorkommens gemeldet. Anschließend wird das Muster so weit verschoben, wie es sein breitester Rand zulässt.

Das folgende Beispiel zeigt die Vergleiche, die der Such­algorithmus durchführt: Über­ein­stimmungen (grün) und Mismatches (rot).

Beispiel:  

0123456789...
ababbabaa
ababac
ababac
ababac
ababac
ababac

Analyse

Die innere While-Schleife des Vorlauf­algorithmus vermindert bei jedem Durchlauf den Wert von j um mindestens 1, denn es ist stets b[j]<j. Da die Schleife spätestens bei j = -1 abbricht, kann sie den Wert von j höchstens so oft vermindern, wie er vorher durch j++ erhöht wurde. Da j++ in der äußeren Schleife insgesamt genau m-mal ausgeführt wird, kann die Gesamtanzahl aller Durchläufe durch die While-Schleife auch nur maximal m betragen. Der Vorlauf­algorithmus benötigt daher höchstens O(m) Schritte.

Mit derselben Argumentation ist einzusehen, dass der Such­algorithmus höchstens O(n) Schritte benötigt. Anschaulich wird dies auch anhand des obigen Beispiels klar: die durch­geführten Vergleiche (grüne und rote Zeichen) bilden eine Treppe. Jede Stufe der Treppe kann höchstens so hoch sein, wie sie breit ist, somit werden höchstens 2n Vergleiche durchgeführt.

Da mkleiner gleichn, beträgt die Komplexität des gesamten Verfahrens ebenfalls O(n).

Literatur

[KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Verfahren von Knuth-Morris-Pratt und andere Textsuchverfahren, so etwa die Verfahren von Boyer-Moore, Horspool und Sunday finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  
[Web 1]http://www-igm.univ-mlv.fr/~lecroq/string/  
[Web 2]http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/stringmatchingclasses/KmpStringMatcher.java   Knuth-Morris-Pratt-Algorithmus als Java-Programm
[Web 3]http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/patternmatcher.htm#section4   Knuth-Morris-Pratt-Algorithmus als Simulation eines String-Matching-Automaten

 

Weiter mit:   [Boyer-Moore-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 19.03.2001   Updated: 19.01.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik