Kurs:Algorithmen und Datenstrukturen/Vorlesung/Textsuche Knuth Morris Path
Einleitung Algorithmus von Knuth-Morris-Pratt[Bearbeiten]
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[Bearbeiten]
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[Bearbeiten]
Preprocessing bedeutet, dass für jedes 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:
![{\displaystyle border[j]:=max_{a\leq k\leq j-1}\{k|pat[1...k-1]=pat[j-k+1...j-1]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7939f59961b713709ba3e3955ceb37dea6611376)
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[Bearbeiten]
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.
Algorithmus von border[Bearbeiten]
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[Bearbeiten]
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:
![{\displaystyle 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]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27295f5e6f5a9cfe77d097f376876bd69e9909dd)
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[Bearbeiten]
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[Bearbeiten]
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 hat. Beweisen kann man das durch eine einfache Schleifenanalyse: 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 .
Literatur[Bearbeiten]
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.
