String-Matching-Algorithmus
String-Matching-Algorithmen, etwa Zeichenketten-Übereinstimmungs- oder Zeichenketten-Such-Algorithmen, befassen sich mit dem Problem, eine gegebene Zeichenkette, Suchmaske genannt, innerhalb einer anderen, Text genannt, zu finden. Das Problem besteht darin, diese Aufgabe möglichst effizient zu lösen.
Unter einer Zeichenkette versteht man in diesem Zusammenhang eine geordnete Kette von Symbolen, die aus einem Alphabet stammen.
Im engeren Sinne suchen die hier angesprochenen Algorithmen nach exakten Übereinstimmungen (matches). Im weiteren Sinne werden auch Algorithmen eingeschlossen, die "ungefähre" Übereinstimmungen zulassen, wobei der Begriff "ungefähr" durch ein Toleranzkriterium genau definiert sein muss.
Eine derartige Suche wird dann interessant, wenn ein großer Korpus von Strings, wie etwa die Wikipedia, nach z. B. Begriffen durchsucht werden soll.
Unter UNIX erlaubt das grep-Kommando die Textsuche in Dateien.
Exakte Suche
Problemstellung
Grundsätzlich sind zwei Situationen zu unterscheiden:
- Die Suchmaske ist vorgegeben, und dann sollen beliebige Texte durchsucht werden.
- Der Text ist vorgegeben, und dann sollen beliebige Suchmasken im Text gefunden werden.
Der zweite Fall entspricht etwa der Aufgabe, etwa die Wikipedia derart aufzubereiten, dass beliebige Suchmasken schnell und effizient aufgefunden werden. Auch Suchmaschinen im Internet finden sich in der zweiten Situation.
Im folgenden wird jedoch nur auf die erste Situation eingegeangen.
Lösungsmethoden
Naiver Algorithmus
Der einfachste Algorithmus besteht darin, ein so genanntes Suchfenster von der Länge der Suchmaske über den Text zu schieben. In jeder Position der Suchmaske werden die Symbole der Maske mit denen des darunterliegenden Textes verglichen. Wenn ein nichtübereinstimmendes Symbol gefunden wird, wird das Fenster um eine Position verschoben, und erneut ein Vergleich angestellt; wenn alle Symbole im Fenster übereinstimmen, ist die Suchmaske gefunden worden. Der Algorithmus endet, wenn der ganze Text vom Fenster abgesucht worden ist.
Dieser Allgorithmus hat eine Laufzeit von der Ordnung n*m, wenn n die Länge der Suchmaske und m die Länge des Textes ist.
Der Morris-Pratt-Algorithmus
Der Morris-Pratt Algorithmus baut auf dem naiven Suchalgorithmus auf. Wesentlicher Unterschied ist, dass das Vergleichsfenster nicht immer um nur eine Position weitergerückt wird, sondern eventuell um mehr als eine Position.
Dazu muss zu Anfang die Suchmaske analysiert werden, so dass bei jeder teilweisen Übereinstimmung, etwa der ersten k Symbole, bekannt ist, ob der Anfang der Suchmaske mit dem Ende der letzten übereinstimmenden Teilmaske übereinstimmt. Die Verschiebung der Suchmaske erfolgt nach der überlappenden Übereinstimmung; zusätzlicher Vorteil ist, dass die schon verglichenen Symbole nicht noch einmal verglichen werden müssen.
Weitere Algorithmen
- Knuth-Morris-Pratt-Algorithmus
- Boyer-Moore-Algorithmus
- Modifizierter Boyer-Moore-Algorithmus
- Boyer-Moore-Horspool-Algorithmus
- Boyer-Moore-Horspool-Raita-Algorithmus
- Boyer-Moore-Sunday-Algorithmus
- Skip-Search-Algorithmus
- Karp-Rabin-Algorithmus
- Shift-And- (Shift-Or-)Algorithmus
Approximative Suche
Zunächst muss festgelegt werden, bis zu welcher Fehlerschwelle gefundene Strings noch als ungefähre Suchtreffer gelten dürfen. Dafür wurde das Konzept der edit distance formuliert, das zählt, wieviel der folgenden Operationen minimal den einen in den anderen String überführen:
- Einfügen eines Zeichens
- Löschen eines Zeichens
- Verändern eines Zeichens
Siehe auch: Baum (Datenstruktur), Endlicher Automat