String matching WS13-14

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 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 bezeichnet und beim Wort mit m.
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.

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.

Programmbeispiel

Weitere Algorithmen

Einige weitere Algorithmen.

Der Boyer-Moore-Horspool Algorithmus

Ein sehr bekannter Algorithmus für das String-Matching-Problem.