Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


20. Pattern Matching



Oft ist es wünschenswert, eine Suche nach einem nur unvollständig spezifizierten Muster vorzunehmen. Zum Beispiel kann es vorkommen, daß Benutzer eines Texteditors nur einen Teil eines Musters vorgeben wollen, oder ein Muster, welches zu mehreren verschiedenen Wörtern passen würde, oder daß sie festlegen wollen, daß eine beliebige Anzahl bestimmter spezifischer Zeichen ignoriert werden soll. Im vorliegenden Kapitel untersuchen wir, wie ein Pattern Matching (Musteranpassung) dieser Art effizient realisiert werden kann.

Die Algorithmen aus dem vorangegangenen Kapitel sind ganz entscheidend von der vollständigen Vorgabe des Musters abhängig, so daß wir andere Methoden benutzen müssen. Die grundlegenden Mechanismen, die wir betrachten werden, ermöglichen die Entwicklung eines sehr leistungsfähigen Verfahrens zur Suche in Zeichenfolgen, welches komplizierte Muster aus M Zeichen an Text-Zeichenfolgen aus N Zeichen anpassen kann, in einer Zeit, die im ungünstigsten Fall proportional zu MN2 ist, in typischen Anwendungsfällen jedoch wesentlich schneller abläuft.

Zunächst müssen wir eine Methode entwickeln, um die Muster zu beschreiben; eine »Sprache«, die benutzt werden kann, um die obengenannten Probleme der partiellen Suche in Zeichenfolgen exakt zu spezifizieren. Diese Sprache wird leistungsfähigere elementare Operationen umfassen als die im vorangegangenen Kapitel verwendete einfache Operation »Überprüfen, ob das i-te Zeichen der Text-Zeichenfolge mit dem j-ten Zeichen des Musters übereinstimmt«. In diesem Kapitel betrachten wir drei grundlegende Operationen, die sich auf einen imaginären Automatentypus beziehen, der Muster in einer Text-Zeichenfolge suchen kann. Unser Algorithmus des Pattern Matching wird eine Methode sein, die die Arbeitsweise dieses Automatentypus simuliert. Im folgenden Kapitel sehen wir dann, wie man von der Vorgabe des Musters, die der Anwender benutzt, um seine Suchaufgabe zu beschreiben, zu der vom Algorithmus verwendeten Vorgabe für den Automaten gelangen kann, um die Suche tatsächlich auszuführen.

Wie wir sehen werden, steht die Lösung, die wir für das Problem des Pattern Matching entwickeln werden, in engem Zusammenhang mit grundlegenden Vorgängen in der Informatik. Zum Beispiel ist die Methode, die wir in unserem Programm anwenden, um die sich aus einer gegebenen Beschreibung eines Musters ergebende Suchaufgabe zu lösen, vergleichbar mit der Methode, die das Pascal-System für die Lösung der Berechnungsaufgabe anwendet, die sich aus einem gegebenen Pascal-Programm ergibt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]