Kurs:Algorithmen und Datenstrukturen/Vorlesung/Naiver Algorithmus Textsuche
Einleitung Suchen in Texten Bearbeiten
Nun betrachten wir einen naiven Algorithmus zur Textsuche.
Problem der Worterkennung Bearbeiten
Direkte Lösung - brute force
| 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) |
a (7) b a c a b
a (8) b (9) a c a b
....
a (22) b (23) a (24) c (25) a (26) b (27)
Pseudocode Brute Force Algorithmus Bearbeiten
for i=1 to n-m+1 do
- Falls pat = text[i...i+m-1] gib i zurück;
Gib -1 zurück
In Java:
int bruteforce_search(char[] text, char[] pat){
int i,j;
for(i = 0; i < text.length - pat.length+1; i++){
for(j = 0; j < pat.length && pat[j] == text[i+j]; j++)
;
if(j == pat.length)
return i;
}
return -1;
}
Analyse Bearbeiten
Das Terminierungstheorem besagt, dass der Algorithmus bruteforce_search bei endlicher Eingabe nach endlich vielen Schritten terminiert.
Das Theorem der Korrektheit besagt, wenn text die Zeichenkette pat enthält, so gibt bruteforce_search(text,pat) den Startindex des ersten Vorkommens von pat zurück, ansonsten -1.
Das Theorem der Laufzeit besagt, dass der Algorithmus bruteforce_search einen Worst-Case Laufzeit von hat. Beweisen lässt sich das durch eine einfache Schleifenanalyse. Die äußere for-Schleife wird maximal (n-m)-mal durchlaufen, die innere for-Schleife wird jedes mal maximal m-mal durchlaufen:
Dafür hat bruteforce_search nun einen Platzbedarf von . Kann man durch zusätzlichen Platzbedarf die Laufzeit verbessern?
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.
