Kurs:Algorithmen und Datenstrukturen/Vorlesung/Textsuche Knuth Morris Path
Einleitung Algorithmus von Knuth-Morris-Pratt
BearbeitenAuf 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
BearbeitenBestimme 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
BearbeitenPreprocessing 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
BearbeitenBeispiel: 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
BearbeitenProblem:
| 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
BearbeitenDas 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
BearbeitenDa 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.
