String matching WS13-14

Autor: Yevgeniy Oliynyk

Allgemeines und Festlegungen

String matching befasst sich allgemein mit dem Finden eines Wortes in einem Text.
Beim Text handelt es sich um eine endliche Folge von Zeichen (bestehend aus dem Alphabet \Sigma der Groß- und Kleinbuchstaben, Zahlen und Satzzeichen) und wird mit t abgekürzt. Das Wort setzt sich ebenfalls aus den selben Zeichen zusammen und wird abgekürzt als w dargestellt. Obwohl es aus mehreren Wörtern bestehen kann, wird es im Folgenden als "Wort" bezeichnet.
Sowohl der Text, als auch das Wort, weisen eine bestimmte Länge auf. Dies bezieht sich auf die Anzahl der Zeichen des Textes bzw. des Wortes. Beim Text wird die Länge mit n (bzw. |t|) bezeichnet und beim Wort mit m (bzw. |w|). Dabei gilt für jedes Text- und Wortpaar in den Beispielen der Seite folgende Vereinbarung: m \leq n.
Um nun festzustellen, ob sich ein Wort in einem Text befindet, müssen einzelne Zeichen verglichen werden. Deren Positionen werden folgedermaßen beschrieben:

• das i-te Zeichen von t heißt t[i], wobei 1\leq i \leq n gilt
• das j-te Zeichen von w heißt w[j], wobei 1\leq j \leq m gilt.

Somit ist eine präzise Positionsangabe möglich.
Der Standardtext für alle hier aufgeführten Beispiele lautet: Das ist das Haus vom Nikolaus mit n=29.

Ein naiver Algorithmus

Vorüberlegung

Um zu erfahren, ob sich das gesuchte Wort an einer beliebigen Stelle t[pos] (1 \leq pos \leq n-m+1) im Text befindet, muss ein Vergleich zwischen den Zeichen an der Stelle t[pos] und w[1] unternommen werden. Falls diese übereinstimmen, so wird weiter verglichen. Im nächsten Schritt wären es dann die Zeichen der Positionen t[pos+1] und w[2]. In der Art und Weise geht es weiter, bis entweder irgendwann 2 ungleiche Zeichen miteinander verglichen werden oder der Fall eintritt, dass auch die Zeichen an der Stelle t[pos+m-1] und w[m] überein stimmen. Das erstere bedeutet, dass das Wort nicht im Text an der gegebenen Position vorkommt. Das letztere hingegen würde eine Erfolgsmeldung nachsich ziehen.

Beispiele

Programmbeispiel

Bisher wird aber nur eine Stelle im Text betrachtet. Um aber festzustellen, ob sich das Wort nicht nur an einer bstimmten Stelle befindet, sonder ob es an einer beliebigen Position vorkommt, ist eine Schleife nötig. Dadurch geht man Zeichen für Zeichen den Text durch und Vergleicht diesen mit dem Wort. Da es eine naive Methode ist, kann man ganz genau sagen, wie viele Schleifendurchläufe nötig sind, nämlich n-m+1. Als Ergebnis einer solchen Funktion, würde man alle Vorkommen des Wortes im Text und dessen Position als Ergebnis zurück bekommen. Sollte sich das Wort nicht im Text befinden, so bekommt man eine dementsprechende Antwort.

Ein passender Algorithmus dazu könnte wie folgt aussehen:

Laufzeitanalyse

Durch die Einfachheit des Algorithmus lässt sich eine Laufzeitanalyse wunderbar durchführen.

Das Best-Case-Szenario würde offensichtlich so aussehen, dass bei jedem Schleifendurchgang nur eine Vergleichsoperation durchgeführt wird. Dies wäre der Fall, wenn m=1 ist oder wenn das Zeichen w[1] nicht in t vorkommt. Somit ist die Laufzeit \mathcal{O}(n-m+1).

Im Worst-Case-Szenario gibt es den Fall, dass bei jeder Stelle des Textes, alle Zeichen des Wortes mit dem jeweiligen Zeichen des Textes verglichen werden müssen. Ein Beispiel für so einen Fall wäre

mit t=aaaaa und w=aaa. Somit sind wieder alle Schleifendurchläufe im Spiel und noch zusätzlich eine weitere Schleife, die in der bisheringen verschachtelt ist und die jedes mal von 1 bis m durchläuft. Der Zeitbedarf steigt auf \mathcal{O}((n-m+1)m). Dementsprechend arbeitet der Algorithmus insgesamt mit einem Aufwand in \mathcal{O}((n-m+1)m).
Bei geeigneter Wahl von t und w und deren längen (m = ⌊n/2⌋), liegt der Aufwand des Algorithmus sogar in \Theta(n^2).

Der Boyer-Moore-Horspool Algorithmus

Der BMH Algorithmus kann eine deutliche Effizienzsteigung gegenüber dem naiven Algorithmus aufweisen. Er wurde 1980 von Nigel Horspool veröffentlicht und stellt eine Vereinfachung des Boyer-Moore Algorithmus dar.

Idee

Im naiven Algorithmus hat man immer bei einer bestimmten Position im Text das Wort mit dem Textabschnitt von links aus verglichen. Im Grunde ist es aber egal, ob man von links oder von rechts mit dem Vergleichen beginnt, denn das spielt in dem Fall keine Rolle. Für BMH jedoch ist es essenziell, dass man von rechts aus mit dem Vergleich beginnt. Dies bringt denn folgenden Vorteil mit sich, dass man eine Art Vorhersage treffen kann. Denn im Grunde genommen geht es bei dem Verfahren darum, nicht jedes Zeichen des Textes zu untersuchen und somit unnötige Operationen einzusparen, ohne dabei das Risiko einzugehen, dass man ein Vorkommen des Wortes im Text übersieht. Dies gelingt mit diesem Vorhersehen und durch eine vorherige Auswertung des Wortes. Dadurch wird es möglich bis zu m Stellen in Folge im Text auszulassen.

Beispiele

Bad-Character

Bevor man mit dem Suchen des Wortes im Text beginnt, erstellt man eine Tabelle mit allen möglichen Zeichen, die im Wort vorkommen dürfen (\Sigma). Jedes der Zeichen wird ein bestimmter Wert zugeordnet, der später entscheidet, um wie viele Stellen des Wort verschoben werden darf.

Weitere Algorithmen

Einige weitere Algorithmen.