Robert Sedgewick: Algorithmen

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


20. Pattern Matching



Automaten für das Pattern Matching

Wir erinnern uns daran, daß wir den Algorithmus von Knuth-Morris-Pratt als einen auf der Grundlage des Suchmusters konstruierten endlichen Automaten betrachten können, der den Text durchsucht. Die Methode, die wir für das Pattern Matching regulärer Ausdrücke anwenden wollen, ist eine Verallgemeinerung dieser Sichtweise.

Der endliche Automat für den Algorithmus von Knuth-Morris-Pratt geht von einem Zustand in den anderen über, indem er ein Zeichen aus der Text-Zeichenfolge untersucht und dann in einen Zustand übergeht, wenn eine Übereinstimmung vorliegt, und in einen anderen, wenn das nicht der Fall ist. Eine Nichtübereinstimmung an irgendeiner Stelle bedeutet, daß das Muster in dem an dieser Stelle beginnenden Text nicht auftreten kann. Der Algorithmus selbst kann als eine Simulation des Automaten angesehen werden. Die Eigenschaft des Automaten, die bewirkt, daß er leicht simuliert werden kann, ist, daß er deterministisch ist: Jeder Übergang von einem Zustand in einen anderen wird vollständig durch das nächste eingegebene Zeichen bestimmt.

Um reguläre Ausdrücke zu behandeln, ist es erforderlich, einen leistungsfähigeren abstrakten Automaten zu betrachten. Aufgrund der Operation oder kann der Automat nicht durch Untersuchung von nur einem Zeichen feststellen, ob das Muster an einer gegebenen Stelle auftreten kann oder nicht; aufgrund der Hüllenbildung kann er noch nicht einmal feststellen, wie viele Zeichen betrachtet werden müßten, bevor eine Nichtübereinstimmung entdeckt wird. Der natürlichste Weg zur Überwindung dieser Probleme besteht darin, den Automaten mit der Fähigkeit eines nichtdeterministischen Vorgehens auszustatten: Bei Vorhandensein von mehreren Wegen, auf denen man versuchen kann, das Muster anzupassen, sollte der Automat den richtigen »erraten«! Es scheint unmöglich zu sein, diese Operation zu gestatten, doch wie wir sehen werden, kann man leicht ein Programm schreiben, um die Aktionen eines solchen Automaten zu simulieren.

Abbildung 20.1 zeigt einen nichtdeterministischen endlichen Automaten, der verwendet werden könnte, um in einer Text-Zeichenfolge die Musterbeschreibung (A*B+AC)D zu suchen. (Die Zustände sind in einer Weise numeriert, die weiter unten verständlich wird.) Wie der deterministische Automat aus dem vorangegangenen Kapitel kann der Automat aus einem mit einem Zeichen markierten Zustand in den Zustand übergehen, auf den dieser Zustand »zeigt«, indem er dieses Zeichen in der Text-Zeichenfolge anpaßt (und durchläuft). Was den Automaten nichtdeterministisch macht, ist, daß es einige Zustände gibt (Nullzustände genannt), die nicht nur mit keinem Zeichen markiert sind, sondern auch auf zwei unterschiedliche Nachfolge-Zustände »zeigen« können. (Einige Nullzustände, wie etwa Zustand 4 im Diagramm, sind »no-op«-Zustände mit einem Ausgang, die auf die Arbeitsweise des Automaten keinen Einfluß haben. Wie wir sehen werden, erleichtern sie die Implementation des Programms, das den Automaten simuliert. Zustand 9 ist ein Nullzustand ohne Ausgänge, der den Automaten anhält.) Wenn sich der Automat in einem solchen Zustand befindet, kann er in jeden beliebigen Nachfolge-Zustand übergehen, unabhängig von der Eingabe (ohne irgend etwas zu durchlaufen). Der Automat hat die Fähigkeit zu erraten, welcher Übergang für die gegebene Text-Zeichenfolge zu einer Übereinstimmung führen wird (wenn es überhaupt einen gibt). Wir bemerken, daß es keine »Nichtübereinstimmungs«-Übergänge gibt wie im vorangegangenen Kapitel; dem Automaten mißlingt es nur dann, eine Übereinstimmung zu finden, wenn es keine Möglichkeit gibt, eine zu einer Übereinstimmung führende Folge von Übergängen auch nur zu erraten.

Abbildung 20.1
Abbildung 20.1 Ein nichtdeterministischer Mustererkennungsautomat für (A*B+AC)D.

Der Automat hat einen eindeutigen Anfangszustand (dargestellt mit Hilfe der frei beginnenden Linie links) und einen eindeutigen Endzustand (das kleine Quadrat rechts). Wenn der Automat im Anfangszustand gestartet wird, ist er in der Lage, jede durch das Muster beschriebene Zeichenfolge zu »erkennen«, indem er Zeichen liest und seinen Zustand gemäß seinen Regeln verändert, wobei er am Ende zum »Endzustand« gelangt. Da der Automat die Fähigkeit zum nichtdeterministischen Vorgehen hat, kann er die Folge der Zustandsänderungen erraten, die zu einer Lösung führen kann. (Wenn wir jedoch versuchen, den Automaten auf einem gewöhnlichen Computer zu simulieren, müssen wir alle Möglichkeiten ausprobieren.) Um zum Beispiel zu bestimmen, ob seine Musterbeschreibung (A*B+AC)D in der Text-Zeichenfolge

CDAABCAAABDDACDAAC

auftreten kann, würde der Automat sofort einen Mißerfolg melden, wenn er beim ersten oder zweiten Zeichen gestartet würde; bei den nächsten beiden Zeichen würde er etwas arbeiten, bevor er einen Mißerfolg melden würde; beim fünften und sechsten Zeichen würde er sofort einen Mißerfolg melden; wenn er beim siebenten Zeichen gestartet würde, würde er die in Abbildung 20.2 dargestellte Folge von Zustandsübergängen erraten, um AAABD zu erkennen.

Abbildung 20.2
Abbildung 20.2 Erkennung von AAABD.

Für einen gegebenen regulären Ausdruck können wir den Automaten konstruieren, indem wir für die einzelnen Komponenten des Ausdrucks Teilautomaten herstellen und für jede der drei Operationen Verkettung, oder und Hüllenbildung die Art und Weise definieren, wie zwei Teilautomaten zu einem größeren Automaten zusammengesetzt werden.

Wir beginnen mit dem trivialen Automaten für die Erkennung eines speziellen Zeichens. Es ist zweckmäßig, diesen als einen Automaten mit zwei Zuständen darzustellen: mit einem Anfangszustand (welcher auch das Zeichen erkennt) und einem Endzustand, wie es Abbildung 20.3 zeigt.

Abbildung 20.3
Abbildung 20.3 Automat mit zwei Zuständen zur Erkennung eines Zeichens.

Um nunmehr den Automaten für die Verkettung von zwei Ausdrücken aus den Automaten für die einzelnen Ausdrücke zu bilden, vereinigen wir einfach den Endzustand des ersten mit dem Anfangszustand des zweiten Automaten, wie es Abbildung 20.4 zeigt.

Abbildung 20.4
Abbildung 20.4 Konstruktion eines
Zustandsautomaten: Verkettung.

In ähnlicher Weise wird der Automat für die Operation oder konstruiert, indem ein neuer Nullzustand hinzugefügt wird, der auf die beiden Anfangszustände zeigt, und indem man einen Endzustand auf den anderen zeigen läßt, der dann zum Endzustand des kombinierten Automaten wird, wie es Abbildung 20.5 zeigt.

Abbildung 20.5
Abbildung 20.5 Konstruktion eines Zustandsautomaten: oder.

Schließlich wird der Automat für die Hüllenbildung gebildet, indem man den Endzustand zum Anfangszustand macht und ihn zurück zum alten Anfangszustand sowie zu einem neuen Endzustand zeigen läßt, wie es in Abbildung 20.6 dargestellt ist.

Abbildung 20.6
Abbildung 20.6 Konstruktion eines Zustandsautomaten: Hüllenbildung.

Durch sukzessive Anwendung dieser Regeln kann für jeden beliebigen regulären Ausdruck ein ihm entsprechender Automat gebildet werden. Die Zustände für das obige Beispiel sind entsprechend der Reihenfolge ihrer Erzeugung numeriert (wenn der Automat konstruiert wird, indem das Muster von links nach rechts durchlaufen wird), so daß die Konstruktion des Automaten mit Hilfe der obigen Regeln leicht verfolgt werden kann. Beachten Sie, daß wir für jeden Buchstaben in dem regulären Ausdruck einen trivialen Automaten mit zwei Zuständen haben und daß jedes + und * die Erzeugung eines Zustands bewirkt (Verkettung bewirkt das Löschen eines Zustands), so daß die Anzahl der Zustände mit Sicherheit weniger als doppelt so groß ist wie die Anzahl der Zeichen in dem regulären Ausdruck.


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