AuK/ String matching WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
'''Autor''': [mailto:s3yeoliy@stud.hszg.de Yevgeniy Oliynyk]
== Allgemeines und Festlegungen ==
String matching befasst sich allgemein mit dem Finden eines Wortes in einem Text. <br>
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. <br>
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$. <br>
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. <br>
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'''
<table>
<tr>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
<td style="text-align: center;width: 5mm;">'''6'''</td>
<td style="text-align: center;width: 5mm;">'''7'''</td>
<td style="text-align: center;width: 5mm;">'''8'''</td>
<td style="text-align: center;width: 5mm;">'''9'''</td>
<td style="text-align: center;width: 5mm;">'''10'''</td>
<td style="text-align: center;width: 5mm;">'''11'''</td>
<td style="text-align: center;width: 5mm;">'''12'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">D</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">i</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;">t</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;">D</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;">h</td>
<td style="text-align: center;width: 5mm;">c</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">m</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkred;">'''x'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
<td style="text-align: center;width: 5mm;">'''6'''</td>
<td style="text-align: center;width: 5mm;">'''7'''</td>
<td style="text-align: center;width: 5mm;">'''8'''</td>
<td style="text-align: center;width: 5mm;">'''9'''</td>
<td style="text-align: center;width: 5mm;">'''10'''</td>
<td style="text-align: center;width: 5mm;">'''11'''</td>
<td style="text-align: center;width: 5mm;">'''12'''</td>
<td style="text-align: center;width: 5mm;">'''13'''</td>
<td style="text-align: center;width: 5mm;">'''14'''</td>
<td style="text-align: center;width: 5mm;">'''15'''</td>
<td style="text-align: center;width: 5mm;">'''16'''</td>
<td style="text-align: center;width: 5mm;">'''17'''</td>
<td style="text-align: center;width: 5mm;">'''18'''</td>
<td style="text-align: center;width: 5mm;">'''19'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">D</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">i</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;">t</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">v</td>
<td style="text-align: center;width: 5mm;">o</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;">D</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">i</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;">t</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
</tr>
<tr style="text-align:center">
<td>Beispiel 1</td>
<td style="width:10mm;"></td>
<td>Beispiel 2</td>
</tr>
</table>
=== 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. <br>
Ein passender Algorithmus dazu könnte wie folgt aussehen:
<code id="52d0732515910">
void naiveSuche(String text, String wort){
int laengeText = text.length();
int laengeWort = wort.length();
int position = 0;
int aktZeichen;
boolean gefunden = false;
while (position <= laengeText-laengeWort){
aktZeichen = 0;
while (aktZeichen < laengeWort && wort.charAt(aktZeichen)==text.charAt(position+aktZeichen))
aktZeichen++;
if (aktZeichen == laengeWort){
System.out.println("Wort an der Stelle " + (position+1) + " im Text gefunden.");
gefunden=true;
}
position++;
}
if (gefunden == false)
System.out.println("Keine Treffer bei der Suche.");
}
</code>
<run id="52d0732515992">
naiveSuche("Das ist das Haus vom Nikolaus","aus");
</run>
=== 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
<table>
<tr>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">a</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
<td style="text-align: center;width: 5mm;color:darkgreen;">'''✓'''</td>
</tr>
</table>
</td>
</tr>
<tr style="text-align:center;">
<td>Schritt 1</td>
<td style="width:10mm;"></td>
<td>Schritt 2</td>
<td style="width:10mm;"></td>
<td>Schritt 3</td>
</tr>
<table>
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)$. <br>
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 das Ziel dieses Verfahrens ist es, 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'''
<table>
<tr>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''11'''</td>
<td style="text-align: center;width: 5mm;">'''12'''</td>
<td style="text-align: center;width: 5mm;">'''13'''</td>
<td style="text-align: center;width: 5mm;">'''14'''</td>
<td style="text-align: center;width: 5mm;">'''15'''</td>
<td style="text-align: center;width: 5mm;">'''16'''</td>
<td style="text-align: center;width: 5mm;">'''17'''</td>
<td style="text-align: center;width: 5mm;">'''18'''</td>
<td style="text-align: center;width: 5mm;">'''19'''</td>
<td style="text-align: center;width: 5mm;">'''20'''</td>
<td style="text-align: center;width: 5mm;">'''21'''</td>
<td style="text-align: center;width: 5mm;">'''22'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''s'''</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">v</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">m</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">N</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">n</td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:darkred;">'''x'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''19'''</td>
<td style="text-align: center;width: 5mm;">'''20'''</td>
<td style="text-align: center;width: 5mm;">'''21'''</td>
<td style="text-align: center;width: 5mm;">'''22'''</td>
<td style="text-align: center;width: 5mm;">'''23'''</td>
<td style="text-align: center;width: 5mm;">'''24'''</td>
<td style="text-align: center;width: 5mm;">'''25'''</td>
<td style="text-align: center;width: 5mm;">'''26'''</td>
<td style="text-align: center;width: 5mm;">'''27'''</td>
<td style="text-align: center;width: 5mm;">'''28'''</td>
<td style="text-align: center;width: 5mm;">'''29'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">m</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">N</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''i'''</td>
<td style="text-align: center;width: 5mm;">k</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">l</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">s</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;">M</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''i'''</td>
<td style="text-align: center;width: 5mm;">r</td>
<td style="text-align: center;width: 5mm;">k</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:darkred;">'''x'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
</tr>
<tr>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''11'''</td>
<td style="text-align: center;width: 5mm;">'''12'''</td>
<td style="text-align: center;width: 5mm;">'''13'''</td>
<td style="text-align: center;width: 5mm;">'''14'''</td>
<td style="text-align: center;width: 5mm;">'''15'''</td>
<td style="text-align: center;width: 5mm;">'''16'''</td>
<td style="text-align: center;width: 5mm;">'''17'''</td>
<td style="text-align: center;width: 5mm;">'''18'''</td>
<td style="text-align: center;width: 5mm;">'''19'''</td>
<td style="text-align: center;width: 5mm;">'''20'''</td>
<td style="text-align: center;width: 5mm;">'''21'''</td>
<td style="text-align: center;width: 5mm;">'''22'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''s'''</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">v</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">m</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">N</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;">H</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">n</td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Stelle'''</td>
<td style="text-align: center;width: 5mm;">'''19'''</td>
<td style="text-align: center;width: 5mm;">'''20'''</td>
<td style="text-align: center;width: 5mm;">'''21'''</td>
<td style="text-align: center;width: 5mm;">'''22'''</td>
<td style="text-align: center;width: 5mm;">'''23'''</td>
<td style="text-align: center;width: 5mm;">'''24'''</td>
<td style="text-align: center;width: 5mm;">'''25'''</td>
<td style="text-align: center;width: 5mm;">'''26'''</td>
<td style="text-align: center;width: 5mm;">'''27'''</td>
<td style="text-align: center;width: 5mm;">'''28'''</td>
<td style="text-align: center;width: 5mm;">'''29'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Text'''</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">m</td>
<td style="text-align: center;width: 5mm;"></td>
<td style="text-align: center;width: 5mm;">N</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''i'''</td>
<td style="text-align: center;width: 5mm;">k</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">l</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">u</td>
<td style="text-align: center;width: 5mm;">s</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wort'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;">M</td>
<td style="text-align: center;width: 5mm;color:darkblue;">'''i'''</td>
<td style="text-align: center;width: 5mm;">r</td>
<td style="text-align: center;width: 5mm;">k</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Vergleich'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
<td style="text-align: center;width: 5mm;color:lightgrey;">'''-'''</td>
</tr>
</table>
</td>
</tr>
<tr style="text-align:center;">
<td>Beispiel 1: verschieben um 4 Stellen</td>
<td style="width:10mm;"></td>
<td>Beispiel 2: verschieben um 3 Stellen</td>
</tr>
<table>
Die Beispiele verdeutlichen in etwa, wie das System in etwa funktioniert. Nach dem eine Suche auf einer beliebigen $pos$ im Text beendet wurde, wird geguckt, ob das Zeichen bei $t[pos]$ im Wort vorkommt. Ist das der Fall, wird der Abstand $a$ des Zeichens zum rechten Ende des Wortes genommen. $a$ gibt an, um wie viele Positionen das Wort verschoben werden darf. Nach der Verschiebung stimmen $t(pos+a)$ und $w(m)$ überein. Sollte das Zeichen nicht in $w$ vorkommen, dann wird $w$ um $m$ Stellen verschoben. <br>
Die Abstandsberechnung wird typischerweise im Vorfeld durchgeführt.
=== Bad-Character ===
Bevor man mit dem Suchen des Wortes im Text beginnt, erstellt man eine Tabelle $D$ mit allen möglichen Zeichen, die im Wort vorkommen dürfen ($\Sigma$). Jedem Zeichen wird ein bestimmter Wert zugeordnet, der später entscheidet, um wie viele Stellen das Wort verschoben werden darf. Dabei wird sinnvollerweise als erstes jedem Zeichen der Wert $m$ zugewiesen. Danach geht man Zeichenweise von links nach rechts das Wort durch und trägt in die entsprechenden Felder den Abstand zum rechten Ende des Wortes ein. Das letzte Zeichen, also $w[m]$, darf nicht mitberücksichtigt werden, da sonst $a=0$ wäre und $D[w[m]]=0$ verboten ist. Andernfalls würde der Algorithmus in einer Endlosschleife enden.
'''Beispiele für einige Tabellen $D$'''
<table>
<tr>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Zeichen'''</td>
<td style="text-align: center;width: 5mm;">K</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">e</td>
<td style="text-align: center;width: 5mm;">t</td>
<td style="text-align: center;width: 5mm;">z</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wert'''</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">1</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Zeichen'''</td>
<td style="text-align: center;width: 5mm;">e</td>
<td style="text-align: center;width: 5mm;">s</td>
<td style="text-align: center;width: 5mm;">t</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wert'''</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">1</td>
</tr>
</table>
</td>
<td style="width:10mm;"></td>
<td>
<table border="1">
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Zeichen'''</td>
<td style="text-align: center;width: 5mm;">S</td>
<td style="text-align: center;width: 5mm;">a</td>
<td style="text-align: center;width: 5mm;">c</td>
<td style="text-align: center;width: 5mm;">d</td>
<td style="text-align: center;width: 5mm;">e</td>
<td style="text-align: center;width: 5mm;">h</td>
<td style="text-align: center;width: 5mm;">l</td>
<td style="text-align: center;width: 5mm;">n</td>
<td style="text-align: center;width: 5mm;">o</td>
<td style="text-align: center;width: 5mm;">p</td>
<td style="text-align: center;width: 5mm;">r</td>
</tr>
<tr>
<td style="width: 5mm;" bgcolor="#D8D8D8">'''Wert'''</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">13</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">1</td>
</tr>
</table>
</td>
</tr>
<tr style="text-align:center;">
<td>Beispiel 1: w = Katze</td>
<td style="width:10mm;"></td>
<td>Beispiel 2: w = stets</td>
<td style="width:10mm;"></td>
<td>Beispiel 2: w = Schneeleopard</td>
</tr>
<table>
In den Beispielen wurden übersichtshalber nur Zeichen berücksichtigt, die im Wort enthalten sind. Allen anderen ist der Wert $m$ zugewiesen. Außerdem sind sie praktischerweise nach dem Vorkommen in der ASCII-Tabelle sortiert.
=== Programmbeispiel ===
<code>
void bmh(String t, String w){
int n = t.length();
int m = w.length();
int[] d = badCharacter(w,m);
int pos = 0;
int j;
boolean g = false;
while (pos <= n-m+1){
j = m;
while (j > 0 && w.charAt(j-1) == t.charAt(pos+j-2))
j--;
if (j == 0){
System.out.println("Wort an der Stelle " + (pos) + " im Text gefunden.");
g = true;
}
pos += d[(int)t.charAt(pos+m-2)];
}
if (g == false)
System.out.println("Keine Treffer bei der Suche.");
}
int[] badCharacter(String w, int m){
int[] d = new int[256];
for (int i = 0;i<256;i++)
d[i] = m;
char c;
for (int i = 0;i<m-1;i++){
c = w.charAt(i);
d[(int)c] = (i-m)*-1-1;
}
return d;
}
</code>
<run>
bmh("Das ist das Haus vom Nikolaus","laus");
</run>
=== Laufzeitanalyse ===
Obwohl auch hier beim Worst-Case-Szenario der Algorithmus die selben Probleme aufweißt wie der naive Algorithmus, ist dieser Algorithmus im Mittel jedoch viel schneller bei der Abarbeitung. Vor allem, wenn es sich um einen gewöhnlichen Text handelt. Dies kann sehr gut dadurch veranschauligt werden, dass bei dem Algorithmus die Möglichkeit besteht, unnötiges Suchen an Stellen, wo niemals das Wort vorkommen kann, zu vermeiden. Doch um diesen Vorteil ausnutzen zu können, muss davor $D$ berechnet werden. Der Aufwand liegt dabei in $\mathcal{O}(m)$. Nach dieser einmaligen Vorverarbeitung arbeitet der eigentliche Suchalgorithmus in $\mathcal{O}(n)$ (im Average-Case) und ist somit potenziell deutlich schneller als das naive Verfahren.
== Weitere Algorithmen ==
=== String-Matching mit endlichen Automaten ===
Es gibt viele Wortsuchalgorithmen, die mit Hilfe von endlichen Automaten arbeiten. Eins davon wird hier vorgestellt. <br>
Die Motivation dahinter ist die Effizienz eines solchen Algorithmus. Bei der Suche nach einem Wort (in dem Zusammenhang auch Muster bzw. pattern genannt) wird jedes Textzeichen nur ein einziges mal untersucht. Diese Untersuchung benötigt, anders als bei den vorherigen Verfahren, stets eine konstante Zeit. Somit schafft es der Algorithmus einen Aufwand zu erreichen, der in $\Theta(n)$ liegt, wenn man nur die Matchingzeit betrachtet.
Für die Veranschaulichung wird ein DEA mit $M = (Q,\Sigma , q_0 , E, \delta )$ verwendet. Dabei ist das Eingabealphabet $\Sigma$ nichts weiter als das am Anfang unter [[AuK/_String_matching_WS13-14#Allgemeines und Festlegungen|Allgemeines und Festlegungen]] festgelegte Alphabet und besteht demzufolge aus den selben Elementen. Da das Wort entscheidend für die Gestaltung des Automaten ist und nicht der Text, besitzt der Automat $m+1$ Zustände: $Q = \{ 0,1,2,...,m-1,m\} $, wobei $q_0 = 0$ ist. Es gibt nur einen Endzustand, nämlich $A = \{ m\} $. Diesen gilt es zu erreichen, damit $M$ das Signal geben kann, dass das Wort im Eingabetext des Automaten gefunden wurde. Jetzt fehlt nur noch die Übergangsfunktion $\delta$, die ein Wort im Text erkennen soll. Um diese Übergangsfunktion aufzustellen, gibt es eine Vorschrift.
'''Vorschrift'''
''Compute-Transition-Function($w$,$\Sigma$)''
{|
|
1 $m ← länge[w]$
2 '''for''' $q ← 0$ '''to''' $m$
3 '''do for''' jedes Zeichen $a \in \Sigma $
4 '''do''' $k ←$ min$(m+1,q+2)$
5 '''repeate''' $k ← k - 1$
6 '''until''' $w_k \sqsupset w_q a$
7 $\delta (q,a) ← k$
8 '''return''' $\delta $
|}
<popup name = "Bemerkung">
Die Schleifen, die in Zeile 2 und 3 beginnen, betrachten alle Zustände in Kombination mit allen Zeichen. Ziel der Funktion ist es den Folgezustand $k$ zu ermitteln, der in Zeile 7 in eine Übergangstabelle $\delta(q,a)$ in das jeweilige Feld eingetragen wird. $w_k$ steht für das Wort, das aber nur bis zur $k$-ten Stelle betrachtet wird und $w_q a$ ist das selbe wie $a$ an $w_{k-1}$ angehängt.
</popup>
[[Bild:Eugen_DEA.jpg|right|thumb|500px|DEA für $w = ababaca$]]
'''Beispiel'''
$M = (Q,\Sigma , q_0 , E, \delta )$, mit
* $Q = \{ 0,1,2,3,4,5,6,7\} $
* $\Sigma = \{ a,b,c\} $
* $q_0 = 0$
* $E = \{ 7\} $
* $\delta$
[[Bild:Eugen_White.jpg|400px]]
=== Der Knuth-Morris-Pratt-Algorithmus ===
Obwohl die Suche beim endlichen Automaten eine akzeptable Laufzeit ausweist, stellt die Vorverarbeitung und damit die Berechnung der Überführungsfunktion mit einem Aufwand in $\Theta(m |\Sigma|)$ ein Hindernis dar. Eine vielversprechende Lösung bietet der KMP Algorithmus. Statt der $\delta$ wird eine Hilfsfunktion $\pi$ (auch Feld genannt) zum Einsatz für die Vorberechnung kommt. Deren Aufwand liegt in nur $\Theta(m)$. Das Matching selber ist vom Aufwand her der selbe, wie schon mit endlichen Automaten.
'''KMP-Matching-Algorithmus'''
''KMP-Matcher($t$,$w$)''
{|
|
1 $n ← länge[t]$
2 $m ← länge[w]$
3 $\pi ←$''Compute-Prefix-Function($w$)''
4 $q ← 0$
5 '''for''' $i ← 1$ '''to''' $n$
6 '''do while''' $q > 0$ und $w[q+1] ≠ t[i]$
7 '''do''' $q ← \pi[q]$
8 '''if''' $w[q+1] = t[i]$
9 '''then''' $q ← q+1$
10 '''if''' $q=m$
11 '''then''' print "Das Wort tritt mit der Verschiebung" $i-m$ "auf"
12 $q ← \pi[q]$
|
|}
''Compute-Prefix-Function($w$)''
{|
|
1 $m ← länge[w]$
2 $\pi[1] ← 0$
3 $k ← 0$
4 '''for''' $q ← 2$ '''to''' $m$
5 '''do while''' $k>0$ und $w[k+1] ≠ w[q]$
6 '''do''' $k ← \pi[k]$
7 '''if''' $w[k+1] = w[q]$
8 '''then''' $k ← k+1$
9 $\pi[q] ← k$
10 '''return''' $\pi$
|
|}
Das Ziel der Präfixfunktion ist es, für jedes Zeichen von $w$ einen Wert $\pi$ zu berechnen, der beim Matching aussagt, was die nächste Position ist, auf die das Wort verschoben werden soll. Die Demonstration geschieht an einem Beispiel
Zuerst wird die Tabelle $\pi$ für das Wort $w=ababababca$ berechnet.
<table border="1">
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$i$</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
<td style="text-align: center;width: 5mm;">'''6'''</td>
<td style="text-align: center;width: 5mm;">'''7'''</td>
<td style="text-align: center;width: 5mm;">'''8'''</td>
<td style="text-align: center;width: 5mm;">'''9'''</td>
<td style="text-align: center;width: 5mm;">'''10'''</td>
</tr>
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$w[i]$</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
<td style="text-align: center;width: 5mm;">'''b'''</td>
<td style="text-align: center;width: 5mm;">'''c'''</td>
<td style="text-align: center;width: 5mm;">'''a'''</td>
</tr>
<tr>
<td style="text-align:center;width: 5mm;" bgcolor="#D8D8D8">$\pi[i]$</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
<td style="text-align: center;width: 5mm;">'''2'''</td>
<td style="text-align: center;width: 5mm;">'''3'''</td>
<td style="text-align: center;width: 5mm;">'''4'''</td>
<td style="text-align: center;width: 5mm;">'''5'''</td>
<td style="text-align: center;width: 5mm;">'''6'''</td>
<td style="text-align: center;width: 5mm;">'''0'''</td>
<td style="text-align: center;width: 5mm;">'''1'''</td>
</tr>
</table>
Jeder Wert $\pi[i]$ gibt darüber Auskunft, um wie viele Stellen das Wort beim Suchen verschoben werden kann für den Fall, dass $w[i]$ nicht mit $t[j]$ (wobei $0<j<n$) übereinstimmt oder $w[m] = w[j]$ ist. Dabei berechnet sich die Verschiebung aus $i-\pi[i]$. Die Funktion gibt außerdem eine Auskunft über die Präfixeigenschaften des Wortes (wodurch sie auch zustande kommt). So ist $w_{\pi[i]}$ ein Präfix von $w_i$.
<popup name = "Bemerkung">
Falls $\pi[i]=0$ und somit $w_{\pi[i]} = w_0$, ergibt sich ein Wort der Länge 0, also ein Wort ohne Zeichen. Dieses Wort ist automatisch ein Präfix von allen beliebigen Wörtern. Somit ist die Aussage, dass $w_{pi[i]}$ ein Präfix von $w_i$ ist, in dem Bezug allgemeingültig.
</popup>
Für die Suche des Wortes $w$ im Text $t=abababababcbababababca$ sehen die entscheidenden Schritte folgendermaßen aus:
{| class="wikitable"
! Position:
| align="center" width="17" bgcolor="#ffffaa" | 1
| align="center" width="17" bgcolor="#ffffaa" | 2
| align="center" width="17" bgcolor="#ffffaa" | 3
| align="center" width="17" bgcolor="#ffffaa" | 4
| align="center" width="17" bgcolor="#ffffaa" | 5
| align="center" width="17" bgcolor="#ffffaa" | 6
| align="center" width="17" bgcolor="#ffffaa" | 7
| align="center" width="17" bgcolor="#ffffaa" | 8
| align="center" width="17" bgcolor="#ffffaa" | 9
| align="center" width="17" bgcolor="#ffffff" | 10
| align="center" width="17" bgcolor="#ffffff" | 11
| align="center" width="17" bgcolor="#ffffff" | 12
| align="center" width="17" bgcolor="#ffffff" | 13
| align="center" width="17" bgcolor="#ffffff" | 14
| align="center" width="17" bgcolor="#ffffff" | 15
| align="center" width="17" bgcolor="#ffffff" | 16
| align="center" width="17" bgcolor="#ffffff" | 17
| align="center" width="17" bgcolor="#ffffff" | 18
| align="center" width="17" bgcolor="#ffffff" | 19
| align="center" width="17" bgcolor="#ffffff" | 20
| align="center" width="17" bgcolor="#ffffff" | 21
| align="center" width="17" bgcolor="#ffffff" | 22
|-
! Text:
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#ffaaaa" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
|-
! Wort:
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#ffaaaa" | c
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
|}
{| class="wikitable"
! Position:
| align="center" width="17" bgcolor="#ffffff" | 1
| align="center" width="17" bgcolor="#ffffff" | 2
| align="center" width="17" bgcolor="#ffffff" | 3
| align="center" width="17" bgcolor="#ffffff" | 4
| align="center" width="17" bgcolor="#ffffff" | 5
| align="center" width="17" bgcolor="#ffffff" | 6
| align="center" width="17" bgcolor="#ffffff" | 7
| align="center" width="17" bgcolor="#ffffff" | 8
| align="center" width="17" bgcolor="#ffffaa" | 9
| align="center" width="17" bgcolor="#ffffff" | 10
| align="center" width="17" bgcolor="#ffffff" | 11
| align="center" width="17" bgcolor="#ffffff" | 12
| align="center" width="17" bgcolor="#ffffff" | 13
| align="center" width="17" bgcolor="#ffffff" | 14
| align="center" width="17" bgcolor="#ffffff" | 15
| align="center" width="17" bgcolor="#ffffff" | 16
| align="center" width="17" bgcolor="#ffffff" | 17
| align="center" width="17" bgcolor="#ffffff" | 18
| align="center" width="17" bgcolor="#ffffff" | 19
| align="center" width="17" bgcolor="#ffffff" | 20
| align="center" width="17" bgcolor="#ffffff" | 21
| align="center" width="17" bgcolor="#ffffff" | 22
|-
! Text:
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
|-
! Wort:
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#aaaaff" | a
| align="center" width="17" bgcolor="#aaaaff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
|}
{| class="wikitable"
! Position:
| align="center" width="17" bgcolor="#ffffff" | 1
| align="center" width="17" bgcolor="#ffffff" | 2
| align="center" width="17" bgcolor="#ffffff" | 3
| align="center" width="17" bgcolor="#ffffff" | 4
| align="center" width="17" bgcolor="#ffffff" | 5
| align="center" width="17" bgcolor="#ffffff" | 6
| align="center" width="17" bgcolor="#ffffff" | 7
| align="center" width="17" bgcolor="#ffffff" | 8
| align="center" width="17" bgcolor="#ffffaa" | 9
| align="center" width="17" bgcolor="#ffffaa" | 10
| align="center" width="17" bgcolor="#ffffaa" | 11
| align="center" width="17" bgcolor="#ffffaa" | 12
| align="center" width="17" bgcolor="#ffffff" | 13
| align="center" width="17" bgcolor="#ffffff" | 14
| align="center" width="17" bgcolor="#ffffff" | 15
| align="center" width="17" bgcolor="#ffffff" | 16
| align="center" width="17" bgcolor="#ffffff" | 17
| align="center" width="17" bgcolor="#ffffff" | 18
| align="center" width="17" bgcolor="#ffffff" | 19
| align="center" width="17" bgcolor="#ffffff" | 20
| align="center" width="17" bgcolor="#ffffff" | 21
| align="center" width="17" bgcolor="#ffffff" | 22
|-
! Text:
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | c
| align="center" width="17" bgcolor="#ffaaaa" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
|-
! Wort:
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#aaffaa" | a
| align="center" width="17" bgcolor="#aaffaa" | b
| align="center" width="17" bgcolor="#aaffaa" | c
| align="center" width="17" bgcolor="#ffaaaa" | a
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
|}
{| class="wikitable"
! Position:
| align="center" width="17" bgcolor="#ffffff" | 1
| align="center" width="17" bgcolor="#ffffff" | 2
| align="center" width="17" bgcolor="#ffffff" | 3
| align="center" width="17" bgcolor="#ffffff" | 4
| align="center" width="17" bgcolor="#ffffff" | 5
| align="center" width="17" bgcolor="#ffffff" | 6
| align="center" width="17" bgcolor="#ffffff" | 7
| align="center" width="17" bgcolor="#ffffff" | 8
| align="center" width="17" bgcolor="#ffffff" | 9
| align="center" width="17" bgcolor="#ffffff" | 10
| align="center" width="17" bgcolor="#ffffff" | 11
| align="center" width="17" bgcolor="#ffffaa" | 12
| align="center" width="17" bgcolor="#ffffff" | 13
| align="center" width="17" bgcolor="#ffffff" | 14
| align="center" width="17" bgcolor="#ffffff" | 15
| align="center" width="17" bgcolor="#ffffff" | 16
| align="center" width="17" bgcolor="#ffffff" | 17
| align="center" width="17" bgcolor="#ffffff" | 18
| align="center" width="17" bgcolor="#ffffff" | 19
| align="center" width="17" bgcolor="#ffffff" | 20
| align="center" width="17" bgcolor="#ffffff" | 21
| align="center" width="17" bgcolor="#ffffff" | 22
|-
! Text:
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
|-
! Wort:
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" |
|}
{| class="wikitable"
! Position:
| align="center" width="17" bgcolor="#ffffff" | 1
| align="center" width="17" bgcolor="#ffffff" | 2
| align="center" width="17" bgcolor="#ffffff" | 3
| align="center" width="17" bgcolor="#ffffff" | 4
| align="center" width="17" bgcolor="#ffffff" | 5
| align="center" width="17" bgcolor="#ffffff" | 6
| align="center" width="17" bgcolor="#ffffff" | 7
| align="center" width="17" bgcolor="#ffffff" | 8
| align="center" width="17" bgcolor="#ffffff" | 9
| align="center" width="17" bgcolor="#ffffff" | 10
| align="center" width="17" bgcolor="#ffffff" | 11
| align="center" width="17" bgcolor="#ffffaa" | 12
| align="center" width="17" bgcolor="#ffffff" | 13
| align="center" width="17" bgcolor="#ffffff" | 14
| align="center" width="17" bgcolor="#ffffff" | 15
| align="center" width="17" bgcolor="#ffffff" | 16
| align="center" width="17" bgcolor="#ffffff" | 17
| align="center" width="17" bgcolor="#ffffff" | 18
| align="center" width="17" bgcolor="#ffffff" | 19
| align="center" width="17" bgcolor="#ffffff" | 20
| align="center" width="17" bgcolor="#ffffff" | 21
| align="center" width="17" bgcolor="#ffffff" | 22
|-
! Text:
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffaaaa" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
|-
! Wort:
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffffff" |
| align="center" width="17" bgcolor="#ffaaaa" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" | b
| align="center" width="17" bgcolor="#ffffff" | c
| align="center" width="17" bgcolor="#ffffff" | a
| align="center" width="17" bgcolor="#ffffff" |
|}