Textdokumente
Nicht immer unterliegen im Computer verarbeitete Daten einer Struktur, die ihre Organisation in Feldern, Listen oder Bäumen erlaubt. Stattdessen bestehen diese Daten nur aus einer langen Folge von Zeichen. Textdokumente, wie sie mit Texteditoren oder Textverarbeitungssystemen erstellt werden, weisen zum Beispiel diese Struktur auf. Nun hat sicher jeder bereits einmal die Situation erlebt, in einem einzelnen Dokument oder in einer Sammlung von Dokumenten (sowohl auf dem PC als auch im World Wide Web) nach einem bestimmten Wort suchen zu müssen. Es ist daher offensichtlich, dass die Suche in Texten eine große Bedeutung hat und dass gerade vor dem Hintergrund der weltweit verfügbaren, riesigen Dokumentbestände effiziente Verfahren benötigt werden.
Ausgehend von der näheren Untersuchung der Aufgabenstellung und einem ersten »naiven« Ansatz werden wir in diesem Kapitel Verfahren zur Textsuche sowie für das verwandte Problem der Suche anhand von Mustern, die auf mehrere verschiedene Wörter passen würden, vorstellen. Ferner wollen wir auf Techniken für die fehlertolerante Suche auf Basis von Ähnlichkeitsvergleichen eingehen.
Muster
Maß für die Effizienz
Die grundsätzliche Aufgabenstellung besteht darin, eine Zeichenkette – ein sogenanntes Muster – in einem (längeren) Text zu finden. Sowohl Text als auch Muster können auf einem beliebigen, aber natürlich gemeinsamen Alphabet basieren. Auch wollen wir im Weiteren Wortgrenzen wie Leer- oder Interpunktionszeichen vollständig ignorieren. Es handelt sich hierbei um eine typische Funktion der Textverarbeitung und ein entsprechendes Softwaresystem sollte daher eine effiziente Lösung bereitstellen. Als Maß für die Effizienz können wir einfach die Anzahl der notwendigen Vergleiche zwischen den Zeichen betrachten.
Ein direkter Lösungsansatz für dieses Problem ist sicher nahe liegend: An jeder Position im Text, an der das Muster passen könnte, wird verglichen. Sei text[0… n − 1] der zu durchsuchende Text und pat[0 … m − 1] das gesuchte Muster (engl. pattern), dann ist für jede Position i im Text zu prüfen, ob pat = text[i … i + m − 1] erfüllt ist. In Algorithmus 17.1 ist dieser »Brute-Force«-Algorithmus vollständig angegeben. Das Ergebnis der Suche kann entweder die Position sein, an der das Muster zum ersten Mal gefunden wurde, bzw. -1 im Fehlerfall (wie im angegebenen Algorithmus) oder ein Wahrheitswert.
algorithm BruteForceSearch (text, pat)
Eingabe: zu durchsuchender Text text der Länge n,
gesuchtes Muster pat der Länge m
for i := 0 to n − m do
j := 0;
while j < m ∧ pat[j] = text[i + j] do
j := j + 1
od;
if j ≥ m then return i fi
od;
return − 1
Der Ablauf dieses Verfahrens und der damit verbundene Aufwand (in Anzahl der Vergleiche) ist in Abbildung 17–1 verdeutlicht. Das Muster wird Position für Position über den Text »geschoben« und dabei werden die Zeichen beider Texte verglichen. Sobald keine Übereinstimmung festgestellt wird, kann abgebrochen und an der nächsten Position des Textes fortgesetzt werden. In der Abbildung ist links von den einzelnen Schritten jeweils die Anzahl der Vergleiche angegeben, die grau hinterlegten Felder im Muster zeigen übereinstimmende Zeichen.
Abb. 17–1 Ablauf beim Brute-Force-Algorithmus
Laufzeitkomplexität
Man kann sich nun klar machen, dass im ungünstigsten Fall ca. (n − m) · m Vergleiche notwendig sind. Dieser ungünstigste Fall tritt beispielsweise bei einem binären Alphabet ein, wenn Muster und Text aus lauter 0-Zeichen bestehen und nur als letztes Zeichen eine 1 aufweisen. Hier würde fast jedes Mal das gesamte Muster verglichen werden müssen, bevor die Nichtübereinstimmung bzw. die Übereinstimmung an der letzten Position erkannt wird. Die Laufzeitkomplexität beträgt für diesen Fall O((n − m) · m) = O(nm), der zusätzliche Platzbedarf ist aber konstant und damit O(1). Insbesondere für lange Muster wünscht man sich daher eine Verbesserung der Laufzeitkomplexität, gegebenenfalls auch bei einer Verschlechterung des Platzbedarfs.
Das Problem des Brute-Force-Verfahrens ist im Wesentlichen, dass bei Feststellen einer Nichtübereinstimmung sowohl der Zeiger im Muster als auch der Zeiger im Text zurückgesetzt werden. In Algorithmus 17.1 ist dies im Vergleich in der while-Bedingung zu erkennen: Da sich der Index für text aus i + j − 1 ergibt und j im Fehlerfall auf 1 zurückgesetzt wird, muss auch die Textposition zurückgesetzt werden. Im Beispiel in Abbildung 17–1 tritt dies etwa im 3. Schritt nach dem Vergleich von »S« und »N« auf. Obwohl man an dieser Stelle eigentlich weiß, dass zuvor »S« und »I« gelesen wurden, wird dies nicht ausgenutzt.
Nutzung bereits gelesener Informationen
Vorverarbeitungsschritt
Verschiebedistanz
An dieser Stelle setzt der Algorithmus von Knuth, Morris und Pratt an, der die Suche mit einer Komplexität von O(n + m) ermöglicht. Die Idee ist hierbei gerade, die bereits gelesene Information bei einer Nichtübereinstimmung zu nutzen. Kommt es an der Stelle j des Musters pat zu einer solchen Nichtübereinstimmung, so gilt pat[0 … j − 1] = text[i … i + j − 1]. Daher kann das Muster um mehr als eine Stelle verschoben werden und auch der Zeiger im Text muss nicht mehr zurückgesetzt werden. Die Anzahl der zu verschiebenden Stellen ist dabei nur vom Muster abhängig. Der Knuth-Morris-Pratt-Algorithmus (kurz »KMP«) nutzt dies aus, indem in einem Vorverarbeitungsschritt die Struktur des Musters analysiert wird. Daraus kann abgeleitet werden, wie weit im Fall einer Nichtübereinstimmung zurückgegangen werden muss. Diese Informationen werden in einem Feld gespeichert, das als next- bzw. border-Feld oder manchmal auch als Fehlerfunktion bezeichnet wird. Es enthält für jede Position des Musters die Distanz für eine sichere Verschiebung. Diese Werte werden bestimmt, indem für jedes j das längste Präfix des Musters pat ermittelt wird, das auch Suffix von pat[1… j] ist.
Tritt nun im Rahmen der Suche beim Vergleich an der Position j des Musters eine Nichtübereinstimmung auf, dann wird im Muster auf Position next[j] zurückgegangen. In Abbildung 17–2 ist dies für das Muster »ABCAAB« mit dem zugehörigen next-Feld dargestellt.
Abb. 17–2 Knuth-Morris-Pratt-Algorithmus am Beispiel
Der erste Konflikt tritt an Position 4 (die erste Position war 0!) auf (i = j = 4). Unter Verwendung der Information aus next[j] ergibt sich als neue Position im Muster j = 1, so dass das Muster wie in der zweiten Zeile dargestellt positioniert wird. Beim nächsten Schritt wird sofort wieder ein Konflikt erkannt. Da hier jedoch die Verschiebedistanz 0 ist, wird im Muster wieder von vorn begonnen. Im folgenden Schritt tritt die Nichtübereinstimmung an Position j = 2 auf, das next-Feld liefert hierfür den Wert 0. Schließlich kann im vierten Schritt eine vollständige Übereinstimmung gefunden werden.
In Algorithmus 17.2 ist dieses Prinzip unter Verwendung des zuvor berechneten next-Feldes umgesetzt.
algorithm KMPSearch (text, pat)
Eingabe: zu durchsuchender Text text der Länge n,
gesuchtes Muster pat der Länge m
j := 0;
for i := 0 to n − 1 do
while j ≥ 0 ∧ pat[j] ≠ text[i] do j := next[j] od;
j := j + 1;
if j = m then return i − m + 1 fi
od;
return -1
Die Werte des next-Feldes werden berechnet, indem eine Kopie des Musters an sich selbst »entlang geschoben« wird und die überlappenden Zeichen jeweils verglichen werden. Dies erfolgt schrittweise für die Werte j = 0… m− 1, d.h., es werden jeweils j Zeichen des Musters unter sich selbst gelegt, wobei das erste Zeichen der Kopie zu Beginn unter dem zweiten Zeichen angeordnet wird. Die Kopie des Musters wird dann so lange nach rechts verschoben, bis entweder alle überlappenden Zeichen übereinstimmen oder keine Überlappung mehr besteht. Die Anzahl der überlappenden Zeichen entspricht dann dem Wert von next[j]. In Abbildung 17–3 ist dies am Beispiel des Musters »ABCAAB« dargestellt. Die Überprüfung beginnt bei j = 1, next[0] wird auf − 1 gesetzt. Die grau hinterlegten Zeichen in der Abbildung markieren den jeweils betrachteten Bereich des Musters.
Abb. 17–3 Berechnung der next-Tabelle
Abschließend ist in Programm 17.1 die Implementierung der Suchmethode und der Vorverarbeitung angegeben. Die Methode kmpSearch ist eine direkte Umsetzung des Algorithmus 17.2. Im ersten Schritt wird das next-Feld für das angegebene Muster berechnet, der weitere Ablauf folgt dem beschriebenen Algorithmus und bedarf sicher keiner weiteren Erläuterungen. Die Methode initNext dient zur Initialisierung des next-Feldes und implementiert das in Abbildung 17–3 dargestellte Prinzip. Die Methode ist prinzipiell ähnlich der Suchmethode. Jedoch wird hier das Muster mit sich selbst auf Übereinstimmung geprüft.
// next-Tabelle initialisieren
private static int[ ] initNext(String pat) {
int[ ] next = new int[pat.length()];
int i = 0, j = − 1;
next[0] = − 1;
while (i < pat.length() − 1) {
while (j > = 0 && pat.charAt(i) != pat.charAt(j))
j = next[j];
i++; j++;
next[i] = j;
}
return next;
}
// Suchfunktion
public static int kmpSearch(String text, String pat) {
int[ ] next = initNext(pat);
int i = 0, j = 0;
while (i < text.length()) {
while (j > = 0 &&
pat.charAt(j) != text.charAt(i))
j = next[j];
i++; j++;
if (j == pat.length())
return i − pat.length();
}
return − 1;
}
Laufzeitkomplexität
Der Aufwand für den KMP-Algorithmus ergibt sich aus dem Aufwand für die Vorbereitungsphase und dem eigentlichen Suchaufwand. Bei der Suche wird in jedem Schritt entweder i oder j (oder beide) um mindestens 1 erhöht, maximal wird also die Schleife 2n-mal durchlaufen, der Aufwand ist daher O(n). Zum Aufbau der next- Tabelle wird das Muster mit der Länge m in gleicher Weise wie bei der Suche durchlaufen, entsprechend ist der Aufwand O(m). Insgesamt ergibt sich somit eine Laufzeitkomplexität von O(n + m).
Es stellt sich noch die Frage, ob der KMP-Algorithmus in der Praxis wirklich schneller ist als der naive Ansatz. Schließlich kann eine signifikante Einsparung von Vergleichen nur dann erfolgen, wenn Teile des Muster sich wiederholen. Ein wesentlicher Vorteil des KMP-Algorithmus ist jedoch, dass im zu durchsuchenden Text nie rückwärts gegangen werden muss. Gerade bei sehr großen Texten, die von externen Speichermedien gelesen werden, ist dies von großer Bedeutung.
Vergleich von rechts nach links
Beim KMP-Algorithmus haben wir das Vermeiden des Zurücksetzens des Textzeigers als einen wesentlichen Vorteil herausgestellt. Wenn dieses Zurücksetzen dagegen ohne Schwierigkeiten möglich ist (etwa bei Texten im Hauptspeicher), kann eine andere Idee verfolgt werden. Vergleicht man das Muster von rechts nach links mit dem Text und stellt dabei fest, dass bereits das erste Zeichen im Text nicht im Muster vorkommt, so kann das Muster um m Positionen verschoben werden. In Abbildung 17–4 ist dieser Fall dargestellt. Beim Vergleich an Position 5 wird eine Nichtübereinstimmung festgestellt. Da außerdem das Zeichen »D« nicht im Muster auftritt, kann auch keine Übereinstimmung an den Positionen 0… 4 auftreten, so dass das Muster bis an Position 6 verschoben werden kann. In diesem günstigen Fall (Nichtübereinstimmung beim ersten zu vergleichenden Zeichen sowie Nichtvorkommen des Textzeichens im Muster) würden somit nur O(n/m) Vergleiche benötigt.
Abb. 17–4 Boyer-Moore: Verschiebung des Musters bei Nichtübereinstimmung I
Der Boyer-Moore-Algorithmus kombiniert nun die oben skizzierte Idee des Vergleichs von rechts nach links mit einem »Verschiebe-Ansatz« ähnlich dem KMP-Algorithmus und ist dadurch unter bestimmten Umständen effizienter. Diese beiden Heuristiken oder Strategien sind:
occurence-Heuristik
match-Heuristik
Abb. 17–5 Boyer-Moore: Verschiebung des Musters bei Nichtübereinstimmung II
Für die beiden Heuristiken wird jeweils die Verschiebedistanz berechnet und das Muster schließlich um den maximalen Wert dieser Distanzen verschoben. Hierzu werden benötigt:
last-Tabelle
shift-Tabelle
Berechnung der last-Tabelle
Die last-Tabelle für das Muster kann einfach berechnet werden, indem für jedes Zeichen des Alphabets seine letzte Position im Muster bestimmt wird bzw. der Wert − 1, falls das Zeichen im Muster nicht vorkommt. Für ein Muster pat der Länge m mit pat = p0p1 … pm−1und ein Alphabet Σ kann last (pat, a) für alle c ∊ Σ wie folgt bestimmt werden:
last[c] = max{j | pj = c}
Berechnung der shift-Tabelle
Die Initialisierung der shift-Tabelle ist dagegen etwas aufwendiger. Diese Tabelle enthält für jedes j die Distanz der Verschiebung, wenn das an Position j beginnende Suffix des Musters übereinstimmt und an Position j − 1 eine Nichtübereinstimmung auftritt. Die Berechnung basiert auf zwei Bedingungen:
Shift-Condition
Occurence-Condition
Für alle i mit 0 ≤ i < m berechnen sich die Werte der Tabelle wie folgt:
shift[i + 1] = min{s > 0 | Cs(i, s) und Co(i, s) gelten}
Der Wert shift[0] wird auf m gesetzt. Zur effizienten Berechnung dieser Tabelle verwendet man ein Hilfsfeld suffix mit
suffix[i] = max{k | pat[i − k + 1… i] = pat[m − k … m − 1]}
für alle i mit 1 ≤ i < m. Dieses Hilfsfeld enthält an der Position i die Länge der längsten Zeichenfolge, die gleichzeitig Suffix des gesamten Musters und des Teilmusters pat[0… i] ist (Abbildung 17–6).
Abb. 17–6 Boyer-Moore: Suffix-Tabelle
Ein Beispiellauf des Algorithmus ist in Abbildung 17–7 für das Muster »ACBABCBA« mit den zugehörigen last- und shift-Tabellen angegeben. Im ersten Schritt wird beim ersten Vergleich an Position 7 bereits eine Nichtübereinstimmung erkannt. Da sowohl last als auch shift eine Distanz von 1 liefert, wird das Muster um 1 verschoben. Im zweiten Schritt wird das Suffix »CBA« als übereinstimmend erkannt. Hier liefert die shift-Tabelle die Verschiebedistanz 4. Beim nächsten Schritt wird sofort beim ersten Vergleich ein Konflikt festgestellt. Unter Verwendung des Wertes aus der last-Tabelle wird das Muster um zwei Positionen verschoben, wobei sich dieser Wert aus m − (last[C] + 1) berechnet. Nach einem weiteren Schritt und der Erkennung des übereinstimmenden Suffix »CBA«, die eine Verschiebung um vier erfordert, wird schließlich das Muster erkannt.
Abb. 17–7 Boyer-Moore-Algorithmus am Beispiel
In Algorithmus 17.3 ist das Verfahren von Boyer-Moore unter Verwendung dieser beiden Strukturen dargestellt. Die Zeichen des Musters werden jeweils von rechts nach links mit dem Text verglichen, daher wird j vor jedem Durchlauf mit dem Index des letzten Musterzeichens (m−1) initialisiert. Ist nach dem Vergleich der Wert j ≤ 0, so bedeutet dies, dass das Muster vollständig übereinstimmt und die Suche wird beendet. Andernfalls wird die maximale Verschiebedistanz aus den beiden Heuristiken bestimmt und das Muster entsprechend verschoben.
algorithm BMSearch (text, pat)
Eingabe: zu durchsuchender Text text der Länge n,
gesuchtes Muster pat der Länge m
i := 0;
while i ≤ n − m do
j := m − 1;
while j ≥ 0 ∧ pat[j] = text[i + j] do j := j − 1 od;
if j < 0 then
return i
else
i := i + max(shift[j], j − last[text[i + j
)
fi
od;
return -1
Vorverarbeitungsphase
In Programm 17.2 ist eine mögliche Implementierung des Boyer-Moore-Algorithmus angegeben. Ähnlich wie bereits beim KMPAlgorithmus werden in einer Vorverarbeitungsphase zunächst die beiden benötigten Tabellen last und shift aufgebaut. Zu diesem Zweck sind zwei zusätzliche Methoden initLast und initShift implementiert, die die Tabellen entsprechend den oben beschriebenen Eigenschaften berechnen. Für die last-Tabelle wird dabei vereinfachend angenommen, dass nur ASCII-Zeichen im Bereich 0… 255 in Muster und Text verwendet werden. Bei Berücksichtigung des vollen Unicode-Zeichensatzes von Java müsste die Tabelle sonst 216 Einträge aufweisen.
public class BMSearch {
// last-Tabelle initialisieren
private static int[ ] initLast(String pat) {
int[ ] last = new int[256];
int i;
for (i = 0; i < 256; i++)
last[i] = − 1;
for (i = 0; i < pat.length(); i++)
last[pat.charAt(i)] = i;
return last;
}
// shift-Tabelle initialisieren
private static int[ ] initShift(String pat) {
int m = pat.length();
int[ ] shift = new int[m + 1];
int[ ] suffix = new int[m + 1];
int i, j, h = 0;
suffix[m − 1] = m;
j = m − 1;
for (i = m − 2; i >= 0; i −−) {
if (i > j && suffix[i + m − 1 − h] < i − j)
suffix[i] = suffix[i + m − 1− h];
else {
if (i < j)
j = i;
h = i;
while (j >= 0 &&
pat.charAt(j) ==
pat.charAt(j+m−1− h))
j −− ;
suffix[i] = h − j;
}
}
for (i = 0; i < m; i++)
shift[i] = m;
j = 0;
for (i = m − 1; i >= − 1; i −−)
if (i == − 1 || suffix[i] == i + 1)
while (j < m − 1− i) {
if (shift[j] == m)
shift[j] = m − 1− i;
j++;
}
for (i = 0; i < m − 1; i++)
shift[m − 1− suffix[i]] = m − i − 1;
return shift;
}
// Suchfunktion
public static int bmSearch(String text, String pat) {
int last[ ] = initLast(pat);
int shift[ ] = initShift(pat);
int i = 0;
while (i <= text.length() − pat.length()) {
int j = pat.length() − 1;
pat.charAt(j) == text.charAt(i+j))
j −−;
if (j < 0)
return i;
else
i += Math.max(shift[j],
j − last[text.charAt(i+j)]);
}
return − 1;
}
}
Laufzeitkomplexität
Da die Analyse der Laufzeit für den Boyer-Moore-Algorithmus etwas schwieriger ist, wollen wir nur kurz auf die wesentlichen Eigenschaften eingehen. In der Vorbereitungsphase beträgt der Aufwand für die Erstellung der shift-Tabelle O(m) mit einer ähnlichen Argumentation wie bereits beim KMP-Algorithmus, für die Erstellung der last-Tabelle O(m + |Σ|). Unter der Voraussetzung, dass das Muster nicht oder nur wenige Male im Text vorkommt, werden im schlechtesten Fall O(n) Vergleiche benötigt. Bei einem im Vergleich zur Länge des Musters großen Alphabet beträgt die Anzahl der Vergleiche sogar nur O(n/m). In den eher seltenen Fällen, wo ein Suffix des Musters sehr häufig im Text vorkommt (z.B. beim Suchen des Musters ABm−1 im Text Bn), ist der Aufwand O(n · m).
Pattern Matching
Mit den bisher betrachteten Algorithmen wird die Suche nach einer konkreten Zeichenfolge im Text unterstützt. Oft soll aber auch nach Zeichenfolgen gesucht werden, die einem allgemeineren Muster entsprechen. Dies ist beispielsweise notwendig, wenn die exakte Schreibweise des gesuchten Wortes nicht genau bekannt ist oder wenn mehrere »ähnliche« Vorkommen des Suchbegriffs gefunden werden sollen. Dieses Problem der Suche nach solchen allgemeineren Mustern wird als Pattern Matching (Musteranpassung) bezeichnet. Hierfür benötigen wir zunächst eine geeignete Notation, um eine – möglicherweise unendliche – Menge von Zeichenketten zu beschreiben, sowie einen Mechanismus oder Algorithmus zur eigentlichen Musteranpassung.
Reguläre Ausdrücke
Eine Notation zur Definition von Mustern, die eine Menge von möglichen Zeichenfolgen beschreiben, sind die regulären Ausdrücke (siehe auch Abschnitt 2.2.2). Ein solcher Ausdruck wird über den Symbolen eines Alphabets Σ durch Verwendung von folgenden Verknüpfungsoperatoren gebildet:
Verkettung
Oder
Hüllenbildung
An diesen wenigen Beispielen wird schon deutlich, dass reguläre Ausdrücke viele Textmuster beschreiben können. In der Praxis werden zur Vereinfachung noch weitere Operatoren eingesetzt, die u.a. die Angabe von Klassen von Zeichen (z.B. alle Ziffern) oder auch die Negation bzw. den Ausschluss von Zeichen ermöglichen. Allerdings lässt sich dies auch mit den oben eingeführten Operatoren ausdrücken.
Anwendung regulärer Ausdrücke
Anwendung finden reguläre Ausdrücke etwa in der Shell des UNIX-Betriebssystems zur Angabe von Dateinamen, in UNIX-Werkzeugen wie grep, die Textdateien anhand von regulären Ausdrücken durchsuchen können, in leistungsfähigen Texteditoren zur Suche bzw. Ersetzung oder in E-Mail-Programmen zur Filterung eingehender Nachrichten.
Nachdem wir mit den regulären Ausdrücken eine Notation zur Beschreibung von Mustern kennen gelernt haben, benötigen wir noch einen Mechanismus, der überprüft, ob ein Text ein gegebenes Muster enthält. Die Schwierigkeit dabei ist, dass wir aufgrund der Eigenschaften von regulären Ausdrücken keinen »einfachen« Algorithmus angeben können. Eine effiziente Form der Überprüfung regulärer Ausdrücke sind die sogenannten endlichen Automaten, eine Ausprägung der abstrakten Maschinen aus Kapitel 6.2. Ein solcher Automat besteht aus
Markierter, gerichteter Graph
Akzeptanz einer Zeichenfolge
Ein endlicher Automat lässt sich als markierter, gerichteter Graph darstellen, wobei die Knoten die Zustände und die markierten Kanten die Übergangsfunktion repräsentieren. Zu einem regulären Ausdruck kann nun ein solcher Automat konstruiert werden. Ausgehend vom Startzustand wird mit jedem gelesenen Zeichen die Übergangsfunktion ausgewertet und gegebenfalls ein neuer Zustand eingenommen. Ist ein Endzustand erreicht, so wurde der Ausdruck erkannt. Anders ausgedrückt, ein Automat akzeptiert eine Zeichenfolge genau dann, wenn es einen Pfad vom Startzustand zu einem Endzustand gibt und die Markierungen der Kanten des Pfades exakt diese Zeichenfolge bilden. Interessanterweise wird beim KMP-Algorithmus die Kodierung eines endlichen Automaten gerade als next-Tabelle genutzt.
Nichtdeterministischer endlicher Automat
Da die Übergangsfunktion eine Menge von Zuständen liefert, handelt es sich hierbei um einen nichtdeterministischen endlichen Automaten (NEA). Dies ist für die Erkennung regulärer Ausdrücke sinnvoll, weil durch die Oder- und die Hüllen-Operationen mehrere (d.h. zwei) Übergänge aus einem Zustand möglich sind. In Abbildung 17–8 ist ein Beispiel eines solchen Automaten für die Erkennung des Ausdrucks »A(A+B)*BA« dargestellt. Die Zustandsmenge ist S = {0, …, 3}, das Alphabet Σ = {A, B}, der Startzustand ist 0 und der Endzustand 3. Der Automat befindet sich damit zu Beginn im Zustand 0. Wird ein A-Zeichen gelesen, erfolgt ein Übergang in Zustand 1. Dort können beliebig viele A- oder B-Zeichen gelesen werden. Hier wird auch der Nichtdeterminismus deutlich: Beim Lesen eines B-Zeichens ist auch der Übergang in Zustand 2 möglich. Dort wird nur noch ein A akzeptiert, wobei der Endzustand eingenommen und die Eingabe akzeptiert wird.
Abb. 17–8 Beispiel für einen nichtdeterministischen endlichen Automaten
Mit dem Hilfsmittel NEA sind wir nun prinzipiell in der Lage, zu prüfen, ob eine Zeichenfolge zu einem gegebenen regulären Ausdruck passt. Die weiteren Aufgaben bestehen nur noch darin, zu diesem Ausdruck den entsprechenden Automaten zu konstruieren und ein Programm zur Simulation des Automaten zu implementieren. Wir wollen das erste Teilproblem anhand einiger einfacher Regeln lösen und für die zweite Teilaufgabe einen Algorithmus skizzieren.
Konstruktion eines NEA
Die Konstruktion eines NEA aus einem gegebenen regulären Ausdruck r beginnt mit der Zerlegung dieses Ausdrucks in seine Bestandteile. Zu jedem atomaren Symbol a ∊ Σ oder ε (dem leeren String) wird ein eigener Automat erstellt, der aus einem Startzustand, einem Endzustand sowie einer Kante besteht, die beide Zustände verbindet und mit dem jeweiligen Symbol markiert ist (Abbildung 17–9).
Abb. 17–9 Konstruktion eines NEA aus regulären Ausdrücken I
Diese einzelnen Automaten werden anschließend entsprechend den definierten Operationen verknüpft. So ergibt sich für den regulären Ausdruck r1+r2 mit den Automaten N (r1) und N (r2) der NEA aus Abbildung 17–10(a), der einen neuen Start- und einen neuen Endzustand besitzt sowie ε-Kanten zu bzw. von den »alten« Start- und Endzuständen der Teilautomaten. In ähnlicher Weise erfolgt die Verknüpfung für die Operationen Verkettung r1r2 (Abbildung 17–10(b)), wobei hier der Endzustand von N (r1) und der Startzustand von N (r2) verschmolzen werden, und Hüllenbildung (Abbildung 17–10(c)).
Unter Anwendung dieser Regeln ergibt sich für den Ausdruck »A*BA« der in Abbildung 17–11 dargestellte Automat, indem zunächst jeweils für A, B und A elementare Automaten konstruiert werden. Im zweiten Schritt wird der Automat für die Hülle von A erstellt und schließlich werden noch die Verkettungen umgesetzt.
Abb. 17–10 Konstruktion eines NEA aus regulären Ausdrücken II
Abb. 17–11 Aus »A* BA« konstruierter NEA
Repräsentation der Zustände und Übergänge
Wie kann nun ein solcher Automat simuliert werden? Zunächst benötigen wir eine geeignete Repräsentation für die Zustände und Übergänge. Hierfür bietet sich eine einfache Tabellendarstellung an, wobei für jeden Zustand (state) die mit einem gelesenen Symbol (symbol) durchzuführenden Übergänge zu den Folgezuständen (next) angegeben sind. Da es für die speziell nach obigen Regeln konstruierten Automaten aus einem Zustand bis zu zwei Übergänge geben kann, werden für ε-Übergänge entsprechend zwei Folgezustände next1 und next2 benötigt. Als Beispiel ist in Abbildung 17–12 die zum Automaten aus Abbildung 17–11 korrespondierende Darstellung angegeben.
Abb. 17–12 Repräsentation eines NEA
Simulation eines NEA
Bei der Simulation eines NEA muss dem nichtdeterministischen Verhalten Rechnung getragen werden. Es sind daher jeweils alle Zustände zu sichern und später der Reihe nach abzuarbeiten, die während des Verarbeitens eines bestimmten Symbols eingenommen werden können. Ein ähnliches Vorgehen wurde beispielsweise auch beim Breitendurchlauf eines Graphen (Abschnitt 16.3.1) gewählt und mithilfe einer Warteschlange realisiert.
In Programm 17.3 ist eine an [Sed02a] angelehnte Implementierung zur Simulation eines NEA angegeben. Diese Implementierung nutzt die Datenstruktur Deque als Kombination von Warteschlange und Kellerspeicher. Die Warteschlange wird benötigt, weil erst alle Zustände des aktuellen Zeichens untersucht werden müssen, bevor mit dem nächsten Zeichen fortgefahren wird – der neue Zustand wird am Ende der Warteschlange eingeordnet. Ein Kellerspeicher ist zur Verarbeitung von Nullzuständen mit ε-Übergängen notwendig, da diese zur sofortigen Untersuchung als erste Elemente eingeordnet werden sollen. In Java kann hierzu beispielsweise eine Liste verwendet werden, die das Einfügen und Herausnehmen von Elementen an beiden Enden unterstützt.
import java.util.LinkedList;
public class NEA {
public static final int SCAN = − 1;
// Klasse zur Repräsentation der Zustände
static class State {
public State(char s, int n1, int n2) {
symbol = s; next1 = n1; next2 = n2;
}
char symbol; // zu akzeptierendes Symbol
int next1, next2; // Nachfolgezustände
}
// "Programm" des NEA
State[ ] states = {
new State(’ ’, 1, 3), new State(’A’, 2, 2),
new State(’ ’, 3, 1), new State(’B’, 4, 4),
new State(’A’, 5, 5), new State(’ ’, 0, 0)
};
public NEA() {}
public boolean match(String s) {
LinkedList <Integer > deque =
new LinkedList <Integer > ();
// Initialisierung
int j = 0, state = states[0].next1;
if (states[0].next1 != states[0].next2)
deque.addFirst(new Integer(states[0].next2));
deque.addLast(new Integer(SCAN));
while (state != 0) {
if (state == SCAN) {
j++;
deque.addLast(new Integer(SCAN));
}
else if (states[state].symbol == ’ ’) {
// " leeres " Zeichen -> Nullzustand
int n1 = states[state].next1;
int n2 = states[state].next2;
deque.addFirst(new Integer(n1));
if (n1 != n2)
deque.addFirst(new Integer(n2));
}
else if (j < s.length() &&
states[state].symbol == s.charAt(j))
// Zeichen akzeptiert
deque.addLast(new Integer(states[state].next1));
if (deque.isEmpty() || j > s.length())
// kein Endzustand erreicht -> Fehler
return false;
// (!) neuen Zustand einnehmen
state = ((Integer) deque.removeFirst()).intValue();
}
// Endzustand: Eingabe akzeptieren
return true;
}
public static void main(String[ ] args) {
NEA nea = new NEA();
System.out.println("accept = " + nea.match("AABA"));
}
}
Da der Automat bei ε-Übergängen in einem beliebigen von mehreren möglichen Zuständen sein kann, werden diese jeweils in die Deque aufgenommen. Zur Unterscheidung der möglichen Zustände für das aktuelle Symbol der Zustände des nachfolgenden Symbols wird ein spezielles Symbol SCAN verwendet.
Mit der internen Klasse State werden die einzelnen Zustände und Übergänge des Automaten repräsentiert. Das »Programm« für den Automaten besteht somit aus einer Menge von Objekten dieser Klasse, die im Feld states abgelegt sind. Entsprechend ist noch eine Methode vorzusehen, die aus einem gegebenen regulären Ausdruck die Repräsentation des Automaten erzeugt.
Erkenner-Methode
Die eigentliche Erkenner-Methode ist die Methode match, die überprüft, ob die übergebene Zeichenkette s zum Muster des Automaten passt. Ausgehend vom Startzustand 0 läuft die Abarbeitung in einer while-Schleife so lange, bis entweder der Endzustand (gekennzeichnet durch einen Sprung in den Zustand 0) erreicht ist oder eine Nichtübereinstimmung mit dem Muster erkannt wurde. Letzteres ist der Fall, wenn kein Zustand mehr in der Warteschlange ist oder das Textende erkannt wurde, ohne dass ein Endzustand erreicht ist. Erfordert der aktuelle Zustand einen Vergleich mit dem Eingabetext – erkennbar an states[state].symbol != ’ ’ –, so wird das entsprechende Zeichen s.charAt(j) gelesen und bei einer Übereinstimmung mit dem Übergangssymbol der Nachfolgezustand eingenommen.
Abb. 17–13 Ablauf bei Erkennung von »AABA«
In Abbildung 17–13 ist der Ablauf der Simulation bei der Verarbeitung der Zeichenkette »AABA« dargestellt. Es sind jeweils der aktuelle Zustand (state), der Inhalt der Deque (deque) sowie die Position des gerade untersuchten Zeichens der Zeichenkette angegeben. Ein 
-Zeichen in der Spalte »Vergleich« markiert die Zustände, bei denen ein Zeichen der Eingabe untersucht wird. Der Inhalt der Deque ist dabei nach der Verarbeitung des jeweiligen Zeichens, aber vor dem Einnehmen des neuen Zustandes dargestellt (die mit (!) markierte Zeile in Programm 17.3).
Das beschriebene Programm ist im Prinzip wieder eine Simulation einer abstrakten Maschine, wie wir das bereits in Kapitel 6 anhand der Registermaschine oder dem Markov-Algorithmus kennen gelernt haben. Die Anwendung zur Erkennung regulärer Ausdrücke zeigt, dass solche Maschinen durchaus auch zur Lösung praktischer Probleme eingesetzt werden.
Java-Klassenbibliothek
Da Pattern Matching mit regulären Ausdrücken ein häufig vorkommendes Problem ist, gibt es in den Klassenbibliotheken der aktuellen Java-Version 1.4 einige Klassen, die dies bereits implementieren. Der einfachste Zugang ist dabei über die Klasse java.util.Pattern möglich. In dieser Klasse ist eine statische Methode boolean matches(String rexpr, String string) definiert, die nach dem regulären Ausdruck rexpr in der Zeichenkette string sucht und im Erfolgsfall den Wert true liefert. Auf diese Weise lässt sich durch die folgende Anweisung das gleiche Verhalten wie in Programm 17.3 erzielen:
boolean res = Pattern.matches("A*BA", "AABA");
Kompilieren von Mustern
In diesem Beispiel sind die Schritte der Konstruktion des Automaten sowie der Erkennung in einer Methode kombiniert. Darüber hinaus besteht auch noch die Möglichkeit, dies getrennt durchzuführen und somit einen einmal konstruierten Automaten zur Erkennung in mehreren Zeichenketten zu nutzen. Hierzu muss die Klassenmethode Pattern.compile(String rexpr) verwendet werden, die anhand eines gegebenen regulären Ausdrucks rexpr ein neues Pattern-Objekt erzeugt. Für dieses Objekt kann anschließend die Methode matcher(String string) aufgerufen werden, die ein Objekt der Klasse java.util.Matcher liefert. Mit dieser Klasse sind eine Reihe von Methoden zur Suche, aber auch zur Ersetzung von Teilen der Zeichenkette auf Basis des gefundenen regulären Ausdrucks definiert. Die einfachste Variante ist wiederum die Verwendung der Methode boolean matches():
Operatoren
Zur Konstruktion von regulären Ausdrücken stehen die in Abschnitt 17.4.1 vorgestellten Operatoren zur Verfügung, wobei jedoch die Oder-Verknüpfung durch ein »|« notiert wird. Darüber hinaus gibt es noch eine Vielzahl weiterer Operationen, z.B.
Eine vollständige Aufstellung der verfügbaren Operatoren kann der API-Dokumentation zur Klasse java.util.Pattern entnommen werden.
Ähnlichkeitsvergleich
Neben der Suche nach allgemeineren Mustern von Zeichenketten spielt in vielen Anwendungen auch die Suche nach einem ähnlichen Text zu einer gegebenen Zeichenkette eine wichtige Rolle. Hierbei wird ein »unscharfer« bzw. fehlertoleranter Vergleich durchgeführt, der auch mit Tippfehlern, Buchstabendrehern oder unterschiedlichen Schreibweisen umgehen kann. In den folgenden Abschnitten wollen wir dafür zwei bekannte Verfahren vorstellen.
Eine häufig eingesetzte Lösung ist die Verwendung der Editierdistanz, die nach ihrem Erfinder, dem russischen Mathematiker Levenshtein, auch Levenshtein-Distanz genannt wird. Dieses Maß beschreibt den Abstand zwischen zwei Zeichenketten in Form der Mindestanzahl von Editieroperationen, die notwendig sind, um die eine Zeichenkette in die andere zu überführen. Als Editieroperationen werden dabei das Einfügen, Löschen und Ersetzen einzelner Zeichen berücksichtigt. Einige Erweiterungen wie die Damerau-Levenshtein-Distanz lassen darüber hinaus auch noch die Transposition (d.h. das Vertauschen von zwei Zeichen) zu. In Abbildung 17–1 ist dies an einigen Beispielen illustriert, wobei jeweils auch die Operationen angegeben sind:
Hierbei ist zu beachten, dass die Transformation der ersten Zeichenkette in die zweite auch durch andere Operationen erreicht werden kann, wie etwa delete(M); insert(H) für das erste Beispiel. Allerdings beschreibt die Levenshtein-Distanz jeweils die minimale Anzahl von Operationen, d.h. in diesem Fall 1 (wie in Tabelle 17–1) statt 2.
Tab. 17–1 Beispiele für die Levenshtein-Distanz
Zeichenketten |
Distanz |
Operationen |
Maus – Haus |
1 |
update(M → H) |
Qualität – Quantität |
2 |
update(l → n); insert(t) |
Psychologie – Physiologie |
3 |
update(s → h); update(c → s); update(h → i) |
Ein verbreiteter Algorithmus zur Bestimmung der Levenshtein-Distanz zweier Zeichenketten der Länge m bzw. n basiert auf einer (m + 1) × (n + 1)-Matrix D und nutzt dynamische Programmierung (siehe Abschnitt 8.5). Jede Zelle (i, j) dieser Matrix beschreibt die Levenshtein-Distanz zwischen dem i- und dem j-Präfix der beiden Zeichenketten. Die einzelnen Zellenwerte lassen sich rekursiv wie folgt berechnen:
Die Matrix wird von links oben (Position (0, 0)) nach rechts unten aufgebaut. Jeder horizontale und vertikale Schritt entspricht dabei einer Editieroperation (mit Kosten +1), ein diagonaler Schritt wird entweder mit +1 (keine Übereinstimmung) oder 0 (Übereinstimmung) gewertet. Man kann sich dies sehr leicht in der Zeile 0 verdeutlichen: Um von der leeren Zeichenkette zum j Zeichen langen Präfix der anderen Zeichenkette zu kommen, werden j (Einfüge-)Operationen benötigt.
Abbildung 17–14 demonstriert dieses Prinzip am Beispiel des Vergleichs der beiden Zeichenketten »Qualität« und »Quantität«. Hierbei steht ε wieder für die leere Zeichenkette. Die markierten Zellen der Matrix stellen die gewählte Folge von Editieroperationen dar: In jedem Schritt wird der Weg mit den minimalen Kosten gewählt. In unserem Beispiel ist dies zu Beginn die Diagonale mit den 0-Werten. Die Ersetzung des »l« durch das »n« kostet dann eine Operation (auf der Diagonale +1). Danach muss ein »t« eingefügt werden (horizontaler Schritt mit +1), bevor auf der Diagonale fortgefahren werden kann. Unten rechts in der Zelle (m, n) kann dann die Levenshtein-Distanz des vollständigen Vergleichs abgelesen werden.
Abb. 17–14 Matrix zur Bestimmung der Levenshtein-Distanz
Betrachten wir abschließend noch eine Implementierung dieses Verfahrens (Programm 17.4). Nach dem Anlegen eines zweidimensionalen Feldes der Größe (m + 1) × (n + 1) werden die 0. Zeile und 0. Spalte initialisiert. Anschließend wird die Matrix zeilenweise durchlaufen und jede Zelle entsprechend der obigen Formel mit einem Wert belegt. Im Fall der Gleichheit der Zeichen an der Position i − 1 und j − 1 wird der Kostenwert 0, andernfalls 1 (Ersetzung) addiert. Das Ergebnis kann schließlich an der Position n, m ausgelesen und zurückgegeben werden.
public class Levenshtein {
public static int distance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[ ][ ] d = new int[m + 1][n + 1];
int i, j;
for (i = 0; i <= m; i++) d[i][0] = i;
for (j = 0; j <= n; j++) d[0][j] = j;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
int cost = (s1.charAt(i −1) == s2.charAt(j −1) ? 0 : 1);
d[i][j] = Math.min(
Math.min(d[i−1][j] + 1, // Zeichen gelöscht
d[i][j−1] + 1), // Zeichen eingefügt
d[i−1][j−1] + cost); // Zeichen ersetzt bzw. gleich
}
}
return d[m][n];
}
public static void main(String[ ] args) {
System.out.println(distance("Qualität", "Quantität"));
}
}
Die Nutzung der distance-Methode ist im Hauptprogramm wieder am Beispiel des Vergleichs von »Qualität« und »Quantität« dargestellt.
Ein n-Gramm ist die Menge aller Zeichenketten der Länge n einer gegebenen Zeichenkette. Hierbei muss gelten, dass die Länge der zu untersuchenden Zeichenkette mindestens n beträgt. Im folgenden Beispiel wollen wir das verdeutlichen.
Für die Zeichenkette »Qualität« ist die Menge aller n-Gramme mit n = 3:
Qualität3 := { __Q, _Qu, Qua, ual, ali, lit, itä, tät, ät_, t__ }.
Am Ende und Anfang der Zeichenketten werden hier durch Leerzeichen aufgefüllte n-Gramme genutzt, so dass auch Worte kürzer als n bearbeitet werden können.
Prinzipiell gilt dabei, dass ähnliche Zeichenketten, also Zeichenketten mit kleiner Editierdistanz, auch eine hohe Anzahl gemeinsamer Zeichenketten besitzen. Bei einer Editierdistanz von k gilt, dass mindestens max(|w|, |v|)−1−(k −1)·n gemeinsame n-Gramme zwischen den Zeichenketten w und v vorhanden sind.
Für den Abstand zweier Zeichenketten werden die jeweiligen Mengen der n-Gramme verglichen. Hierzu wird die Schnittmenge gebildet, die die Gemeinsamkeiten enthält. Die Ähnlichkeit sim zweier Worte w und v ergibt sich dann bei der Nutzung von 3-Grammen als
Die Ähnlichkeitswerte liegen im Intervall von 0 bis 1; der Wert 1 ergibt die größte Ähnlichkeit.
Für den Vergleich von »Qualität« und »Quantität« nutzen wir wieder 3-Gramme:
Qualität3 := { __Q, _Qu, Qua, ual, ali, lit, itä, tät, ät_, t__ }
und
Quantität3 := { __Q, _Qu, Qua, uan, ant, nti, tit, itä, tät, ät_, t__ }.
Als Schnittmenge erhalten wir
Qualität3 ∩ Quantität3 := { __Q, _Qu, Qua, itä, tät, ät_, t__ }.
Die Ähnlichkeit berechnet sich dann als 
. Für die Ähnlichkeit von »Qualität« mit »Quarantäne« würden wir hingegen als Ähnlichkeitswert nur 
erhalten. Bei der Nutzung von 2-Grammen statt 3-Grammen beim Vergleich von »Qualität« und »Quantität« ergibt sich 
als Wert.
Für die tatsächliche Berechnung der Ähnlichkeit mittels n-Grammen müssen wir eine effiziente Datenstruktur für die Darstellung der Mengen auswählen und eine Operation zur Berechnung der Schnittmengengröße implementieren.
Die Klasse NGrams aus dem Programm 17.5 implementiert den 3-Gramm-Vergleich mittels der in Java vordefinierten Hash-Implementierung von Mengen (Klasse HashSet), indem die 3-Gramme des ersten Wortes in eine Hashtabelle eingefügt werden und danach jedes 3-Gramm des zweiten Wortes gegen diese Hashtabelle getestet wird. Zur Vereinfachung der 3-Gramm-Bildung werden die Zeichenketten vor der Verarbeitung mit führenden bzw. abschließenden ‘_’-Zeichen versehen.
import java.util.HashSet;
public class NGrams {
public static double sim(String str1, String str2) {
String s1 = "__" + str1 + "__",
s2 = "__" + str2 + "__";;
int num = 0;
int l1 = 0, l2 = 0;
HashSet <String> set = new HashSet <String> ();
for (; l1 < str1.length() + 2; l1++) {
String gram = s1.substring(l1, l1 + 3);
set.add(gram);
}
for (; l2 < str2.length() + 2; l2++) {
String gram = s2.substring(l2, l2 + 3);
if (set.contains(gram)) num++;
}
return 2.0 * num / (l1 + l2);
}
}
Ähnlichkeitsvergleiche von Zeichenketten sind eine wichtige Technik in vielen Anwendungen, die eine fehlertolerante Suche erfordern. Typische Beispiele hierfür sind die Rechtschreibprüfung in Textverarbeitungsprogrammen, die Dublettenerkennung bei der Bereinigung großer Datenmengen (repräsentieren zwei Datensätze das gleiche Objekt wie etwa eine Person, auch wenn eventuell unterschiedliche Schreibweisen verwendet wurden?) oder auch der Vorschlag alternativer Suchbegriffe bei Websuchmaschinen.
