Robert Sedgewick: Algorithmen

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


20. Pattern Matching



Simulation des Automaten

Der letzte Schritt bei der Entwicklung eines allgemeinen Algorithmus zur Anpassung eines mit Hilfe eines regulären Ausdrucks beschriebenen Musters besteht in der Erstellung eines Programms, das in gewisser Weise die Arbeitsweise eines nichtdeterministischen Pattern Matching-Automaten simuliert. Die Idee, ein Programm zu erstellen, das die richtige Antwort »erraten« kann, erscheint lächerlich. In diesem Falle zeigt es sich jedoch, daß wir alle möglichen Anpassungen in einer systematischen Weise verfolgen können, so daß wir schließlich die richtige finden.

Eine Möglichkeit wäre, ein rekursives Programm zu entwickeln, das den nichtdeterministischen Automaten nachahmt (aber vielmehr alle Möglichkeiten ausprobiert, anstatt die richtige zu erraten). Statt dieses Ansatzes untersuchen wir eine nichtrekursive Implementation, die die grundlegenden Funktionsprinzipien der Methode verdeutlicht, indem sie die betrachteten Zustände in einer sehr speziellen Datenstruktur ablegt, die Warteschlange mit zweiseitigem Zugriff (»double-ended queue«, kurz und im folgenden »deque«) genannt wird.

Die Idee besteht darin, alle Zustände zu registrieren, die eingenommen werden könnten, während der Automat das aktuelle Zeichen »betrachtet«. Alle diese Zustände werden der Reihe nach abgearbeitet: Nullzustände führen zu zwei (oder weniger) Zuständen, Zustände für Zeichen, die mit dem aktuellen Eingabewert nicht übereinstimmen, werden eliminiert, und Zustände für Zeichen, die mit dem aktuellen Eingabewert übereinstimmen, führen zu neuen Zuständen, die zu verwenden sind, wenn der Automat das nächste eingegebene Zeichen untersucht. Demzufolge wollen wir eine Liste aller Zustände führen, in denen sich der nichtdeterministische Automat an einer bestimmten Stelle im Text befinden könnte. Das Problem besteht darin, für diese Liste eine geeignete Datenstruktur zu entwickeln.

Die Verarbeitung von Nullzuständen scheint einen Stapel zu erfordern, da wir genau wie bei der Beseitigung der Rekursion im wesentlichen eines von zwei zu erledigenden Dingen aufschieben (daher sollte der neue Zustand an den Anfang der aktuellen Liste gesetzt werden, damit er nicht unaufhörlich aufgeschoben wird). Die Verarbeitung der anderen Zustände scheint eine Warteschlange zu erfordern, da wir keine Zustände für das nächste eingegebene Zeichen untersuchen wollen, bevor wir nicht mit dem aktuellen Zeichen fertig sind (so daß der neue Zustand an das Ende der aktuellen Liste gesetzt werden sollte). Anstatt zwischen diesen zwei Datenstrukturen zu wählen, benutzen wir beide! Warteschlangen mit zweiseitigem Zugriff kombinieren die Merkmale von Stapeln und Warteschlangen: Eine deque ist eine Liste, der Elemente an beiden Seiten hinzugefügt werden können. (Genau genommen benutzen wir eine »ausgabebeschränkte deque«, da wir Elemente stets vom Anfang entnehmen und nicht vom Ende.)

Eine entscheidende Eigenschaft des Automaten ist, daß er keine »Schleifen« haben darf, die nur aus Nullzuständen bestehen, da er sich andernfalls nichtdeterministisch entscheiden könnte, immer wieder die Schleife zu durchlaufen. Es zeigt sich, daß hieraus folgt, daß die Anzahl der Zustände in der deque zu einem beliebigen Zeitpunkt kleiner ist als die Anzahl der Zeichen in der Beschreibung des Musters.

Das unten angegebene Programm verwendet eine deque, um die Aktionen eines nichtdeterministischen Automaten für das Pattern Matching von der oben beschriebenen Art zu simulieren. Während ein spezielles Zeichen in der Eingabe untersucht wird, kann sich der nichtdeterministische Automat in einem beliebigen von verschiedenen möglichen Zuständen befinden; das Programm registriert diese in einer deque, wobei es, wie in Kapitel 3, Prozeduren push, put und pop verwendet. Es könnte eine Darstellung als Feld (wie in der Warteschlangen-Implementation in Kapitel 3) oder als verkettete Liste (wie in der Stapel-Implementation in Kapitel 3) benutzt werden; auf die Implementation wird verzichtet.

Die Hauptschleife des Programms entnimmt der deque einen Zustand und führt die geforderte Aktion aus. Wenn ein Zeichen anzupassen ist, wird die Eingabe hinsichtlich des geforderten Zeichens geprüft; wenn es gefunden wird, wird der Zustandsübergang vorgenommen, indem der neue Zustand am Ende der deque eingefügt wird (so daß alle Zustände, die das aktuelle Zeichen betreffen, vor denen bearbeitet werden, die das nächste betreffen). Wenn es sich um einen Nullzustand handelt, so werden die beiden möglichen zu simulierenden Zustände am Anfang der deque gesetzt. Die das aktuelle eingegebene Zeichen betreffenden Zustände werden von denen, die das nächste betreffen, durch eine Markierung scan=-1 in der deque getrennt; wenn scan vorgefunden wird, wird der auf die eingegebene Zeichenfolge weisende Zeiger vorgestellt. Die Schleife bricht ab, wenn das Ende der Eingabe erreicht ist (keine Übereinstimmung gefunden), der Zustand 0 erreicht wird (zulässige Übereinstimmung gefunden) oder nur ein Element, die Markierung scan, in der deque verblieben ist (keine Übereinstimmung gefunden). Dies führt unmittelbar zu der folgenden Implementation;

    function match(j: integer): integer;
      const scan=-1;
      var state,n1,n2: integer;
      begin
      dequeinit; put(scan);
      match:=j-1; state:=next1[0];
      repeat
        if state=scan then
          begin j:=j+1; put(scan) end
        else if ch[state]=a[j] then
          put(next1[state])
        else if ch[state]=' ' then
          begin
          n1:=next1[state]; n2:=next2[state];
          push(n1); if n1<>n2 then push(n2)
          end;
        state:=pop;
      until (j>N) or (state=0) or (dequeempty);
      if state=0 then match:=j-1;
      end;

Diese Funktion verwendet die Position j in der Text-Zeichenfolge a, bei der sie beginnen sollte, eine Übereinstimmung herzustellen, als Argument. Sie gibt den Index des letzten Zeichens in der gefundenen Reihe übereinstimmender Zeichen zurück (wenn es solche Zeichen gibt; andernfalls gibt sie j - 1 zurück).

Abbildung 20.8 zeigt den Inhalt der deque jedesmal, wenn ein Zustand entnommen wird, wenn wir unseren Beispiel-Automaten mit der Text-Zeichenfolge AAABD arbeiten lassen. Für dieses Diagramm wird eine Darstellung als Feld zugrunde gelegt, wie sie für Warteschlangen in Kapitel 3 verwendet wurde; das Pluszeichen wird benutzt, um scan darzustellen. Jedesmal, wenn die Marke scan das vordere Ende der deque (im Diagramm unten) erreicht, wird der Zeiger j inkrementiert und auf das nächste Zeichen im Text positioniert. Demzufolge beginnen wir mit Zustand 5, während das erste Zeichen im Text (das erste A) durchlaufen wird. Zuerst führt Zustand 5 zu den Zuständen 2 und 6, dann führt Zustand 2 zu den Zuständen 1 und 3, die beide das gleiche Zeichen durchlaufen müssen und am Anfang der deque eingefügt werden. Danach führt Zustand 1 zu Zustand 2, jedoch am Ende der deque (für das nächste eingegebene Zeichen). Zustand 3 führt nur dann zu einem weiteren Zustand, wenn ein B durchlaufen wird, und wird daher ignoriert, da ein A durchlaufen wird. Wenn die Marke scan schließlich das vordere Ende der deque erreicht, sehen wir, daß sich der Automat nach dem Durchlaufen des ersten A entweder im Zustand 2 oder im Zustand 7 befinden könnte. Danach probiert das Programm die Zustände 2, 1, 3 und 7 aus, während es das zweite A »untersucht«, und stellt fest, wenn scan zum zweiten Mal das vordere Ende der deque erreicht, daß Zustand 2 nach dem Durchlaufen von AA die einzige Möglichkeit ist. Während nun das dritte A untersucht wird, sind die einzigen Möglichkeiten die Zustände 2, 1 und 3 (die Möglichkeit AC ist bereits ausgeschlossen). Diese drei Zustände werden erneut ausprobiert und führen schließlich nach dem Durchlaufen von AAAB zu Zustand 4. Das Programm fährt fort, indem es zum Zustand 8 übergeht, D durchläuft und in den Endzustand gelangt. Es ist eine Übereinstimmung gefunden worden, und was noch wichtiger ist, alle Übergänge, die mit der Text-Zeichenfolge vereinbar sind, sind betrachtet worden.

Abbildung 20.8
Abbildung 20.8 Inhalt der deque während der Erkennung von AAABD.

Eigenschaft 20.1 Die Simulation der Arbeitsweise eines Automaten mit M Zuständen bei der Suche nach Mustern in einer Text-Zeichenfolge aus N Zeichen kann im ungünstigsten Fall mit weniger als NM Zustandsübergängen erfolgen.

Die Laufzeit von match hängt offenbar sehr stark von dem Muster ab, das angepaßt werden soll. Für jedes der eingegebenen N Zeichen könnte es jedoch scheinen, daß höchstens M Zustände des Automaten verarbeitet werden, so daß die Laufzeit im ungünstigsten Fall proportional zu MN sein sollte (für jede Startposition im Text). Leider trifft dies für match in der obigen Implementation nicht zu, da das Programm, wenn es einen Zustand in die deque aufnimmt, nicht prüft, ob er sich bereits dort befindet, so daß die deque mehrfache Kopien ein und desselben Zustands enthalten kann. Dies mag für praktische Anwendungen keine großen Auswirkungen haben, doch der Effekt kann in einfachen pathologischen Fällen rasch gigantische Ausmaße annehmen, wenn er nicht kontrolliert wird. Zum Beispiel kann dieses Problem zu einer deque mit 2N-1 Zuständen führen, wenn das Muster (A*A)* an eine Zeichenfolge aus N Zeichen A angepaßt wird. Um dies zu vermeiden, muß match dahingehend geändert werden, daß niemals Zustände mehrmals in die deque aufgenommen werden (so daß damit gewährleistet wird, daß für jedes eingegebene Zeichen höchstens M Zustände verarbeitet werden). Dies kann durch explizite Überprüfung oder durch ein durch state indiziertes Feld realisiert werden. Mit dieser Änderung ist die Gesamtanzahl, wenn bestimmt werden soll, ob irgendein Abschnitt der Text-Zeichenfolge durch das Muster beschrieben wird, O(MN2). w.z.b.w.

Nicht alle nichtdeterministischen Automaten können so effizient simuliert werden, wie in Kapitel 40 ausführlicher untersucht wird; die Verwendung eines einfachen hypothetischen Automaten für das Pattern Matching führt jedoch für diese Anwendung zu einem sehr sinnvollen Algorithmus für ein recht kompliziertes Problem. Allerdings benötigen wir, um den Algorithmus zu vervollständigen, ein Programm, das beliebige reguläre Ausdrücke in »Automaten« umsetzt, die dann durch das obige Programm interpretiert werden können. Im folgenden Kapitel betrachten wir die Implementation eines solchen Programms im Rahmen einer allgemeineren Untersuchung von Compilern und Techniken der Syntaxanalyse.


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