Einleitung Algorithmus von Knuth-Morris-Pratt

Auf dieser Seite behandeln wir den Algorithmus von Knuth-Morris-Pratt. Die Idee ist, dass bereits gelesene Informationen bei einem Mismatch genutzt werden. Kommt es an Stelle j von pat zum Mismatch, so gilt:

pat[1...j-1]=text[i...i+j-2]

a	b	a	c	a	a	b	a	c	c	a	b	a	c	a	b	a	a	b	b

a (1)	b (2)	a (3)	c (4)	a (5)	b (6)

Das a an Stelle 5 ist das Suffix von pat[1..5]. Nun gilt: schiebe Muster um 4, überprüfe weiter ab Position 6 im Text, ab Position 2 im Muster

a	b (7)	a	c	a	b

Das erste a ist nun das Präfix

a (8)	b (9)	a (10)	c (11)	a (12)	b

a (13)	b	a	c	a	b

a (14)	b (15)	a (16)	c (17)	a (18)	b (19)

Realisierung mit Fehlerfunktion

Bestimme für jedes j der Länge f[j] des längsten Präfixes von pat der Suffix von pat[1..j] ist. Gibt es einen Fehler an Stelle j, dann verschiebe die Suchposition im Muster auf j:=f[j-1]+1=border[j].

Position j im Pattern	1	2	3	4	5	6
Pattern pat[j]	a	b	a	c	a	b
Längster Präfix f[j]	0	0	1	0	1	2
Verschiebeposition	0	1	1	2	1	2

border im Detail

Preprocessing bedeutet, dass für jedes $j,1\leq j\leq m$ das größte k so bestimmt wird, dass pat [1...k-1] ein echter Suffix von pat[1...j-1] ist. Genauer berechnet und als border bezeichnet wird:

 $border[j]:=max_{a\leq k\leq j-1}\{k|pat[1...k-1]=pat[j-k+1...j-1]\}$

Bei einem Mismatch an Position j verschiebe die Position im Text auf i:=i+ border[j] )oder 1 falls nicht definiert, z.B. erste Position) und die Position im Suchmuster auf j:=border[j]

Die border-Tabelle

Beispiel: Drei Zeilen j, pat[j] und border [j]

1	2	3	4	5	6	7	8	9	10	11	12	13	j
a	b	a	a	b	a	b	a	a	b	a	a	b	pat[j]
0	1	1	2	2	3	4	3	4	5	6	7	5	border[j]

Dieses Beispiel ist ein so genannter Fibonacci String.

$F_{7}:$

$1.F_{0}=\epsilon ,F_{1}=b,F_{2}=a$

$2.F_{n}=F_{n-1}F_{n-2}$

Algorithmus von border

 
Eingabe: char-Array pattern[]
Ausgabe: int-Array border[]

int[] border = new int[pattern.length];
for(int k = 0; k < border.length; k++){
    border[k] = 0;
}

int i = 1, j = 0;
while(i < border.length){
     while(i+j < border.length-1 && 
           pattern[j] == pattern[i+j]){
        border[i+j+1] = max(border[i+j+1],j+1);
        j++;
     }
     i++;
}

sborder als Verbesserung von border

Problem:

pat:							a	b	a	a	b	a	-	-
text:	-	-	-	-	-	-	a	b	a	a	b	c	-	-

Hier gibt es ein mismatch an der Stelle j=g, border[6]=3. Daher muss um 3 verschoben werden.

pat:										a	b	a	a	b	a	-	-
text:	-	-	-	-	-	-	a	b	a	a	b	c	-	-

Nun haben wir als Result sofort wieder ein Mismatch. Wir wissen bereits, dass an der Mismatch Stelle kein a stehen darf.

Verbesserung:

 $sborder[j]=max_{1\leq k\leq j-1}\{k|pat[1...k-1]=pat[j-k+1...j-1]\land pat[k]\neq pat[j]\}$

Falls kein deratiges k existiert, dann 0.

Beispeil vier Zeilen mit j, pat[j], border[j] und sborder[j]:

1	2	3	4	5	6	7	8	9	10	11	12	13	j
a	b	a	a	b	a	b	a	a	b	a	a	b	pat[j]
0	1	1	2	2	3	4	3	4	5	6	7	5	border[j]
0	1	0	2	1	0	4	0	2	1	0	7	1	sborder[j]

Algorithmus

 
Eingabe: char-Array text[], char-Array pattern[]
Ausgabe: true/false

int[] sborder = new int[pattern.length];
for(int k = 0; k < sborder.length; k++){
    sborder[k] = 0;
}

int i = 1, j = 0;
while(i < sborder.length){
   while(i+j < sborder.length-1 && 
                pattern[j] == pattern[i+j]){
      if(pattern [j+1] == pattern[i+j+1])
          sborder[i+j+1] = max(sborder[i+j+1],j+1);
      j++;
    }
    i++;
}
i = 0;
j = 0;
while(i < text.length() - pattern.length() + 1){
     while(j < pattern.length() && text[i+j] == pattern[j]){
       j++;
     }
     if(j == pattern.length()) return true;
     i = i + max(border[j], 1);
     j = border[j];
}

Analyse

Das Theorem der Terminierung besagt, dass der Algorithmus von Knuth-Morris-Pratt für endliche text[] und pat[] eine endliche Laufzeit hat.

Das Theorem der Korrektheit besagt, wenn text die Zeichenkette pat enthält, so gibt der Algorithmus von Knu5‐Morris‐Pra5 TRUE zurück, ansonsten FALSE.

Das Theorem der Laufzeit besagt, dass der Algorithmus von Knutt-Morris-Pratt eine Worst-Case Laufzeit von $\Theta (m+n)$ hat. Beweisen kann man das durch eine einfache Schleifenanalyse: $\Theta (m)$ für die Berechnung von sborder und </math> \Theta (n) </math> für die Hauptschleife. Der zusätzliche Platzbedarf des Algorithmus von Knutt-Morris-Pratt ist $\Theta (m)$ .

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5 zu finden.