Textsuche

Jedes Textverarbeitungsprogramm hat eine Suchfunktion, mit der man in einem Text alle Vorkommen eines bestimmten Wortes suchen kann. Sucht man beispielsweise in diesem Absatz das Wort "Text", so wird das erste Vorkommen am Anfang von "Textverarbeitungsprogramm" gefunden und dann noch an drei weiteren Stellen.

Es folgt zunächst die formale Definition einiger Begriffe.

Grundlagen

Der Begriff "Wort" nach dieser Definition bezeichnet also jede beliebige endliche Folge von Zeichen; die Bedeutung der Zeichen spielt keine Rolle. Insofern unterscheidet sich der Begriff hier vom Begriff "Wort" im umgangssprachlichen Sinne.

Das Textsuchproblem (engl.: string matching problem) stellt sich wie folgt: Gegeben ist ein Wort t, der Text, und ein kürzeres Wort p, der Suchbegriff oder das Muster. Gesucht sind alle Positionen i, an denen das Muster p im Text t vorkommt.

Eingabe:

Text  t = t₀ ... t_n-1  und Muster   p = p₀ ... p_m-1 über einem Alphabet A

Ausgabe:

Alle Positionen von Vorkommen von p in t, d.h.  { i  |  p = w_i }

Es sind auch überlappende Vorkommen des Musters möglich, wie in folgendem Beispiel:

Strategie

Der einfachste Algorithmus überprüft das Muster an allen Positionen i = 0, ...,  n-m. Das Muster wird an der jeweiligen Position zeichenweise von links nach rechts mit dem entsprechenden Textfenster verglichen. Bei einem Mismatch oder bei vollständiger Übereinstimmung wird das Muster um eine Position weitergeschoben und an dieser Position verglichen usw. Dieser Algorithmus wird als der naive Algorithmus bezeichnet. Er benötigt im schlechtesten Fall n·m Zeichenvergleiche.

Durch Ausnutzung unterschiedlicher Informationen lässt sich die Anzahl der Zeichenvergleiche verringern. Es gibt verschiedene Ansätze, alle untersuchen das Muster in einem Vorlauf (engl.: preprocessing), um Vorabinformation über die Struktur des Musters und über die vorkommenden Zeichen zu gewinnen.

Struktur des Musters

In folgendem Beispiel stimmen die ersten vier Zeichen des Musters mit dem Text überein, das fünfte Zeichen führt zu einem Mismatch. Es ist in dieser Situation nicht nötig, das Muster an den Positionen i = 2, 3, und 4 zu vergleichen, sondern das Muster kann gleich bis Position i = 5 weitergeschoben werden. Keines der Textzeichen t₂, t₃ und t₄ kann nämlich ein a sein, denn die Textzeichen hatten ja mit den von a verschiedenen Zeichen c, b und e des Musters übereingestimmt. Die nächste mögliche Übereinstimmung des Musters ist also an Position 5, wie im Beispiel gezeigt.

Anders stellt sich die Situation in folgendem Beispiel dar. Das Muster kann nur um zwei Positionen weitergeschoben werden, da ein Präfix des Musters (ab) als Suffix des übereinstimmenden Teils abab vorkommt.

Es geht also in der Vorlaufphase darum, die Struktur des Musters daraufhin zu analysieren, wie weit es bei einem Mismatch an einer jeweiligen Position weitergeschoben werden kann.

Vorkommende Zeichen

Ist t_i ein Zeichen, das im Muster überhaupt nicht vorkommt, so kann das Muster an keiner der m Positionen i-m+1, ..., i übereinstimmen. In folgendem Beispiel kommt das e nicht im Muster vor. Das Muster kann daher bis hinter das e weitergeschoben werden.

In der Vorlaufphase wird eine Tabelle angelegt, die für jedes Zeichen des Alphabets die Position seines letzten Vorkommens im Muster enthält, bzw. -1, falls das Zeichen nicht im Muster vorkommt.

Wahrscheinlichkeit der Zeichen

Es ist prinzipiell nicht notwendig, die Zeichen des Musters von links nach rechts mit dem Text zu vergleichen, sondern sie können in beliebiger Reihenfolge verglichen werden. Ist die Wahrscheinlichkeitsverteilung der Zeichen des Textes bekannt (oder zumindest annähernd bekannt), so kann es vorteilhaft sein, zuerst dasjenige Zeichen des Musters mit dem Text zu vergleichen, das die geringste Wahrscheinlichkeit hat. Mit hoher Wahrscheinlichkeit wird es dann zu einem Mismatch kommen, und das Muster kann weitergeschoben werden.

Signatur

Anstatt das Musters mit dem jeweiligen Textfenster zeichenweise direkt zu vergleichen, wird bei diesem Ansatz ein indirekter Vergleich durchgeführt. Aus dem Muster wird ein Wert berechnet, die Signatur. Diese Signatur wird jeweils mit der Signatur des entsprechenden Textfensters verglichen. Nur dort, wo die Signaturen übereinstimmen, können auch Muster und Text übereinstimmen.

Philosophie

"Suchen" bedeutet "Versuchen, etwas zu finden". Wenn wir Vorkommen eines Musters in einem Text suchen, sollten wir uns eigentlich über jedes übereinstimmende Zeichen freuen. Um so größer wird schließlich die Hoffnung, ein Vorkommen zu finden.

Diese optimistische Herangehensweise führt jedoch nicht zu besonders effizienten Algorithmen. Die effizientesten Algorithmen entstehen aus der Haltung des Pessimisten: "Wetten, das Muster kommt sowieso nicht vor." Der Algorithmus erbringt den Beweis, dass das Muster nirgendwo im Text vorkommen kann, außer möglicherweise an ein paar Stellen. An diesen Stellen wird dann geprüft, ob das Muster dort tatsächlich vorkommt.

Die Strategie, dasjenige Zeichen des Musters zuerst zu vergleichen, das am wenigsten wahrscheinlich übereinstimmt, geht in diese Richtung. Ein Optimist hätte zuerst das wahrscheinlichste Zeichen verglichen.

Der Pessimist jubelt, wenn er auf ein Textzeichen trifft, das im Muster überhaupt nicht vorkommt. Der Optimist verfällt in, natürlich nur kurzlebige, Depressionen ob dieses Missgeschicks. Der Pessimist darf, der Optimist muss, notgedrungen, das Muster hinter dieses Zeichen weiterschieben.

Im Ergebnis macht der Optimist aufgrund seines Wunschdenkens, das Muster könnte passen, mehr Vergleiche als der Pessimist.

Geschichte

Erstaunlich spät, erst 1974, erschien ein Algorithmus, der im schlechtesten Fall O(n) Vergleiche benötigt. Der Algorithmus von Knuth, Morris und Pratt [KMP 77] nutzt hierbei die Information über die Struktur des Musters aus, um unnötige Mehrfachvergleiche zu vermeiden.

Aho und Corasick verallgemeinerten diesen Ansatz für die gleichzeitige Suche nach mehreren Mustern [AC 75].

Aufsehen erregte 1977 die Idee von Boyer und Moore, das Muster von rechts nach links zu vergleichen und außer der Struktur des Musters auch die vorkommenden Zeichen zu berücksichtigen. Das Ergebnis ist ein sublinearer Algorithmus, der im Durchschnitt lediglich O(n/m) Vergleiche benötigt [BM 77].

Beim Boyer-Moore-Verfahren bestimmt sich die Schiebedistanz durch das Vorkommen desjenigen Textzeichens, das zu einem Mismatch geführt hat. Das Verfahren von Horspool [Hor 80] verwendet stets das Vorkommen des ganz rechten Zeichens im Textfenster. Dies führt zu einer Vereinfachung des Verfahrens; die Struktur des Musters braucht nicht mehr berücksichtigt zu werden.

Noch weiter geht die Idee von Sunday [Sun 90], das Vorkommen des unmittelbar rechts neben dem Textfenster stehenden Zeichens zu verwenden, denn dieses Zeichen muss beteiligt sein, wenn das Muster an der nächsten Position verglichen wird. Diese kleine Veränderung erlaubt es darüber hinaus, die Vergleiche im Textfenster in beliebiger Reihenfolge durchzuführen. Es kommt nicht mehr darauf an, möglichst weit rechts im Textfenster einen Mismatch zu entdecken, um das Muster möglichst weit verschieben zu können. Es kann somit eine Reihenfolge aufgrund der Wahrscheinlichkeit der Zeichen gewählt werden.

Auf dem Signatur-Ansatz beruht das Verfahren von Karp und Rabin [KR 87]. Da es möglich ist, die Signatur eines Textfensters aus der Signatur des vorhergehenden Textfensters in konstanter Zeit zu berechnen, erreicht das Verfahren eine Komplexität von O(n).

Mit Bitvektoren als Signaturen arbeitet der Shift-And-Algorithmus [WM 92]. Die Signatur des jeweiligen Fensters wird aus der Signatur des vorherigen Fensters durch eine Shift- und eine And-Operation von Bitvektoren der Länge m ermittelt. Der Algorithmus erreicht eine Komplexität von O(n), wenn die Shift- und die And-Operation in konstanter Zeit ausgeführt werden können, insbesondere also dann, wenn m≤32 (z.Zt. Länge eines Maschinenwortes) ist.

Literatur

Originalartikel:

Der Algorithmus [KMP 77] erschien 1974 als Institutsbericht und erst 1977 in einer Fachzeitschrift.

[AC 75]   A.V. Aho, M.J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM, 18, 6, 333-340 (1975)

[BM 77]   R.S. Boyer, J.S. Moore: A Fast String Searching Algorithm. Communications of the ACM, 20, 10, 762-772 (1977)

[Hor 80]   R.N. Horspool: Practical Fast Searching in Strings. Software - Practice and Experience 10, 501-506 (1980)

[KMP 77]   D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977)

[KR 87]   R. Karp, M. Rabin: Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development 31, 249-260 (1987)

[Sun 90]   D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)

[WM 92]   S. Wu, U. Manber: Fast Text Searching Allowing Errors. Communications of the ACM 35, 10, 83-91 (1992)

Bücher:

[OW 90]   T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag (1990)

[Sed 88]   R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)

[Schö 97]   U. Schöning: Algorithmen -- kurz gefasst. Spektrum (1997)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Alle hier erwähneten Textsuchverfahren (außer Karp-Rabin) finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]