|
Brute Force
Dieser Suchalgorithmus durchsucht einen Text nach einem Muster. Dabei vergleicht er die aktuelle Stelle des Musters mit der aktuellen Stelle im Text. Tritt ein ,Mismatch' auf wird das Muster um eine Stelle verschoben und neu verglichen, sonst wird die aktuelle Stelle des Musters und des Textes um eine Stelle erhöht und weiter verglichen. Selbst wenn das Muster nahezu komplett durchsucht wurde und erst zum Schluß ein ,Mismatch' auftaucht wird das Muster nur um eine Stelle verschoben.
Algorithmus:
int search (char *p, char *a) // p ... Suchmuster
{ // a ... durchsuchter Text
int i, j, m = strlen (p), n = strlen (a);
for (i = 0, j = 0; j < m && i < n; i++, j++)
while (a[i] != p[j]) {
i-= j - 1;
j = 0;
}
if (j == m) return i-m;
else return i;
}
Durch dieses Verfahren kommt es zu vielen doppelten Vergleichen.
Suchaufwand: maximal: n * m
n ... Länge des Musters
m ... Länge des Textes
Knuth-Morris-Pratt (KMP)
Der Algorithmus von KMP stellt eine wesentliche Verbesserung gegenüber dem Brute-Force-Algorithmus dar. Diese Verbesserung wird durch eine Vorverarbeitung des Musters erreicht. In dieser Vorverarbeitung wird ermittelt, ab welcher Stelle des Textes frühestens ein nächster Vergleich des gesamten Musters beginnen kann. Es wird ein Array verwendet, um zu bestimmen, an welcher Stelle im Muster zurückzukehren ist, wenn eine Nichtübereinstimmung festgestellt wurde.
Es sind niemals mehr als n + m Zeichenvergleiche notwendig.
Boyer-Moore
Im Gegensatz zu den vorherigen Algorithmen wird das Muster nicht von links nach rechts mit dem Text verglichen, sondern umgekehrt. Der Vergleich beginnt also immer an der letzten Stelle im Muster. Tritt eine Nichtübereinstimmung auf, wird die Distanz berechnet, um die das Muster verschoben wird, bevor ein erneuter Vergleich ausgeführt wird.
Die Berechnungen für die Verschiebung des Musters sind nur von dem Zeichen im Text abhängig, das die Nichtübereinstimmung verursacht hat. Darüber hinaus spielt es eine Rolle, ob und an welcher Position das Zeichen im Muster auftaucht. Dies führt dazu, daß man für jedes Zeichen des Alphabets einen Eintrag in einem Array reserviert, der die Größe der möglichen Verschiebungen nach rechts angibt, wenn das Zeichen eine Nichtübereinstimmung verursacht. Das Array wird mit delta bezeichnet und enthält für jedes Element, das nicht im Muster verkommt m und ansonsten den Abstand des rechtesten Vorkommens des Zeichens bis zum Musterende.
Der Algorithmus von Boyer-Moore kann im ungünstigsten Fall n * m Schritte benötigen. Im Idealfall hingegen nur n / m Schritte.
Algorithmus:
// Berechnung von delta
for (c = ´A´; c |
