Robert Sedgewick: Algorithmen

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


20. Pattern Matching



Beschreibung von Mustern

Die von uns betrachteten Musterbeschreibungen erfolgen mit Hilfe von Symbolen, welche mittels der folgenden drei grundlegenden Operationen miteinander verknüpft sind.

  1. Verkettung (Concatenation). Dies ist die Operation, die im letzten Kapitel benutzt wurde. Falls zwei Zeichen im Muster benachbart sind, so liegt genau dann und nur dann eine Übereinstimmung vor, wenn die im Text gleichen beiden Zeichen benachbart sind. Zum Beispiel bedeutet AB, daß B auf A folgt.

  2. Oder (Or). Dies ist die Operation, die uns die Möglichkeit gibt, Alternativen im Muster vorzugeben. Wenn sich zwischen zwei Zeichen ein oder befindet, so liegt dann und nur dann eine Übereinstimmung vor, wenn eines der Zeichen im Text auftritt. Wir wollen diese Operation durch Benutzung des Symbols + bezeichnen und Klammern verwenden, um sie mit der Verkettung in beliebig komplexer Weise zu kombinieren. Zum Beispiel bedeutet A+B »entweder A oder B«; C(AC+B)D bedeutet »entweder CACD oder CBD«; (A+C)((B+C)D) bedeutet »entweder ABD oder CBD oder ACD oder CCD«.

  3. Hüllenbildung (Closure). Diese Operation gestattet es, Teile des Musters beliebig oft zu wiederholen. Bei der Hülle eines Symbols liegt dann und nur dann eine Übereinstimmung vor, wenn das Symbol beliebig oft (einschließlich 0 mal) erscheint. Die Hüllenbildung soll bezeichnet werden, indem nach dem zu wiederholenden Zeichen oder der zu wiederholenden, in Klammern eingeschlossenen Gruppe ein * gesetzt wird. Zum Beispiel stimmt AB* mit Zeichenfolgen überein, die aus einem A bestehen, dem eine beliebige Anzahl (oder kein) B folgt, während (AB)* mit Zeichenfolgen übereinstimmt, die aus sich abwechselnden A und B bestehen.

Eine Folge von Symbolen, die unter Verwendung dieser drei Operationen aufgebaut ist, wird regulärer Ausdruck genannt. Jeder reguläre Ausdruck beschreibt viele spezielle Textmuster. Unser Ziel besteht darin, einen Algorithmus zu entwickeln, mit dem bestimmt werden kann, ob irgendeines der Muster, die durch einen gegebenen regulären Ausdruck beschrieben werden, in einer gegebenen Text-Zeichenfolge auftritt.

Wir konzentrieren uns auf Verkettung, oder und Hüllenbildung, um die grundlegenden Prinzipien bei der Entwicklung eines Pattern Matching-Algorithmus für reguläre Ausdrücke aufzuzeigen. In realen Systemen werden aus Gründen der Zweckmäßigkeit gewöhnlich noch weitere Operationen verwendet. Zum Beispiel könnte -A »Übereinstimmung mit jedem Zeichen außer A« bedeuten. Diese Operation nicht (not) entspricht einem oder, das alle Zeichen außer A umfaßt, läßt sich jedoch viel leichter handhaben. Analog könnte »?« »Übereinstimmung mit einem beliebigen Buchstaben« bedeuten. Auch dies ist offensichtlich wesentlich kompakter als ein umfangreiches oder. Weitere Beispiele zusätzlicher Symbole, die die Vorgabe umfangreicher Muster einfacher machen, sind Symbole für den Anfang oder das Ende einer Zeile, einen beliebigen Buchstaben oder eine beliebige Zahl usw.

Diese Operationen können eine bemerkenswert einfache Beschreibung ermöglichen. Zum Beispiel stimmt die Beschreibung eines Musters ?*(ie + ei)?* mit allen Wörtern überein, in denen ie oder ei vorkommt; (1 + 01)*(0 + 1) beschreibt alle aus den Zeichen 0 und 1 bestehenden Zeichenfolgen, in denen keine zwei aufeinanderfolgenden Nullen auftreten. Offenbar gibt es viele verschiedene Musterbeschreibungen, die die gleichen Zeichenfolgen beschreiben; wir müssen versuchen, kurze Musterbeschreibungen vorzugeben, ebenso wie wir uns bemühen, effiziente Algorithmen zu schreiben.

Der Pattern Matching-Algorithmus, den wir untersuchen werden, kann als eine Verallgemeinerung der groben Methode der Suche in Zeichenfolgen von links nach rechts (der ersten in Kapitel 19 betrachteten Methode) angesehen werden. Der Algorithmus sucht nach der am weitesten links stehenden Teil-Zeichenfolge innerhalb der Text-Zeichenfolge, die mit der Beschreibung des Musters übereinstimmt, indem er die Text-Zeichenfolge von links nach rechts durchläuft und bei jeder Position prüft, ob eine bei dieser Position beginnende Teil-Zeichenfolge existiert, die mit der Beschreibung des Musters übereinstimmt.


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