String-Matching-Algorithmus

Grundidee und Anwendungsfall

String-Matching-Algorithmen sind in der Informatik Zeichenkettenalgorithmen. Sie finden Textsegmente in einer Zeichenkette anhand eines vorgegebenen Suchmusters. Im engeren Sinn suchen sie exakte Übereinstimmungen (matches). Im weiteren Sinn gehören auch Verfahren dazu, die ungefähre Übereinstimmungen zulassen; dabei muss ein Toleranzkriterium genau festlegen, was als ungefähr gilt.

Wichtig ist eine effiziente Suche, besonders in großen Textmengen, etwa beim Auffinden von Begriffen in einer Wikipedia. Bei der exakten Suche gibt es zwei Grundsituationen: Entweder ist eine Suchmaske vorgegeben und sie wird in beliebigen Texten gesucht, oder der Text ist vorgegeben und viele unterschiedliche Suchmasken sollen darin schnell gefunden werden. Die zweite Situation entspricht beispielsweise der Aufbereitung der Wikipedia oder der Arbeit von Internetsuchmaschinen. Die beschriebenen Verfahren zur exakten Suche behandeln vor allem die erste Situation.

Naive exakte Suche

Der naive Algorithmus schiebt ein Suchfenster mit der Länge der Suchmaske über den Text. An jeder möglichen Position werden die Symbole der Maske mit den darunterliegenden Textsymbolen verglichen. Bei einem nicht passenden Symbol wird das Fenster um eine Position verschoben. Stimmen alle Symbole überein, wurde die Suchmaske gefunden. Der Vorgang endet, wenn das Fenster den gesamten Text abgesucht hat.

Für Textlänge n und Musterlänge m beträgt die Laufzeit 𝒪(n·m). Im Pseudocode werden für q = 0 bis n − m die Bedingungen P[1] = T[q+1], P[2] = T[q+2], …, P[m] = T[q+m] geprüft; bei Erfolg wird q ausgegeben. q bezeichnet also die Stellen, an denen P in T auftritt.

In der Praxis ist dieses Verfahren bei natürlichsprachigen Texten überraschend schnell, weil ein Fehler meist schon nach 1 bis 2 Zeichen gefunden wird. Für die englische Sprache wird eine Wahrscheinlichkeit von 1.07 Zeichen angegeben; dadurch ist der Ansatz nahezu linear schnell. Ein ungünstiger Fall ist Text „aaa...aab“ mit Muster „ab“. Solche Fälle sind in natürlichsprachlichen Texten äußerst unwahrscheinlich.

Automat, KMP und Suffixbaum

Ein endlicher Automat für ein Alphabet Σ und ein Suchmuster der Länge m hat die Form (Q, Σ, δ, q₀, {qₘ}) mit Q = {qᵢ | 0 ≤ i ≤ m}. Der Zustand i gibt an, wie viele Buchstaben vom Beginn des Musters an der aktuellen Stelle übereinstimmen. Sei Pᵢ das Präfix des Suchmusters bis einschließlich des Buchstabens an Stelle i. Für a ∈ Σ liefert die Übergangsfunktion δ(qᵢ, a) den Zustand qⱼ, wobei j die maximale Anzahl von Buchstaben ist, für die Pⱼ ein Suffix von Pᵢa ist:

δ(qᵢ,a) = q₍max{j | Pⱼ ist Suffix von Pᵢa}₎.

Nach dem Finden des Musters verharrt der Automat im Endzustand: δ(qₘ,a) = qₘ. Im Unterschied zum naiven Verfahren verwirft er bei einem Fehler nicht das Wissen über den bereits verarbeiteten Text. Beim Muster „anax“ im Text „ananax“ kann er beim zweiten „n“ die ersten beiden Buchstaben verwerfen und mit „anax“ weiterarbeiten; der naive Algorithmus würde den bisherigen verarbeiteten Teil vollständig verwerfen.

Der Knuth-Morris-Pratt-Algorithmus baut auf der naiven Suche auf. Sein Vergleichsfenster wird nicht zwingend nur um eine Position verschoben. Vorab wird die Suchmaske analysiert: Nach einer Teilübereinstimmung der ersten k Symbole muss bekannt sein, ob der Musteranfang mit dem Ende der zuletzt passenden Teilmaske übereinstimmt. Die Maske wird entsprechend dieser Überlappung verschoben; bereits verglichene Symbole müssen nicht erneut verglichen werden.

Ist ein Text im Voraus bekannt und sollen später viele verschiedene Muster darin gesucht werden, eignet sich ein Suffixbaum. Er kann in 𝒪(n) konstruiert werden. Danach lässt sich jedes Muster ohne erneute Vorbereitung des Textes in 𝒪(m) suchen: Ist es vorhanden, wird vom Ursprung des Suffixbaums der passende Knoten erreicht; andernfalls existiert kein entsprechender Knoten.

Laufzeiten und weitere Verfahren

Dabei ist m die Länge der Suchmaske und n die Länge des Textes. Der naive Algorithmus benötigt keine Vorbereitung, seine Suchzeit ist Θ((n−m+1)·m). Rabin-Karp hat Vorbereitungszeit Θ(m), durchschnittliche Suchzeit Θ(n+m) und im schlechtesten Fall Θ(n·m). Der endliche Automat benötigt 𝒪(m·|Σ|) Vorbereitung und Θ(n) Suchzeit.

Knuth-Morris-Pratt benötigt Θ(m) Vorbereitung und Θ(n) Suchzeit. Boyer-Moore hat Θ(m) Vorbereitungszeit, durchschnittlich Θ(n/m) Suchzeit und im schlechtesten Fall Θ(n·m). Shift-Or benötigt Θ(m+|Σ|) Vorbereitung und Θ(n) Suchzeit. Bei der Suche im Suffixbaum betragen die Zeiten Θ(n) für die Vorbereitung und Θ(m) für die Suche.

Als weitere Algorithmen werden Skip-Search, Baeza-Yates-Gonnet (Shift-Or oder Shift-And), BNDM (Backward Nondeterministic Dawg Matching) und BOM (Backward Oracle Matching) genannt.

Mehrere, flexible und unscharfe Muster

Die Suche nach mehreren Mustern in einem Text heißt Multi-String-Matching. Die meisten entsprechenden Algorithmen werden aus einem String-Matching-Algorithmus für genau ein Muster abgeleitet. Eine besondere Herausforderung sind Überlappungen von Suchwörtern. Genannt werden Multi-Shift-And zu Shift-And, Aho-Corasick zu Knuth-Morris-Pratt, Commentz-Walter zu Boyer-Moore, Set-Horspool zu Horspool, Wu-Manber zu Horspool/Rabin-Karp und Set-BOM zu BOM.

Die Mustervergleichssuche liegt zwischen exakter und unscharfer Suche. Der Benutzer muss ausdrücklich angeben, welchen Spielraum er für bestimmte Zeichenklassen an bestimmten Positionen eines Strings zulässt.

Bei der unscharfen Suche entscheidet üblicherweise der Algorithmus anhand eines vorgegebenen Güte- oder Abstandskriteriums, wie stark Treffer abweichen dürfen. Dazu gehört auch die Suche nach gleichlautenden Wörtern, also die phonetische Suche. Beispiele sind Soundex und Kölner Phonetik.