Mit den Daten im Takt bleiben

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Wir betrachten ein längeres Beispiel, das etwas gesucht ist, aber ein paar wichtige Punkte sehr gut veranschaulicht: Es zeigt, warum es wichtig ist, dass die Regex mit den Daten, die abgesucht werden, im Takt bleibt (und dazu die Methoden liefert).

Nehmen wir an, die zu untersuchenden Daten seien eine Reihe von (deutschen, fünfstelligen) Postleitzahlen, die alle zusammengeschrieben sind. Die Aufgabe besteht darin, alle Postleitzahlen zu finden, die mit 66 beginnen. Hier sehen Sie einige Beispieldaten, die gesuchten Postleitzahlen sind fett gedruckt:

03824531669411615213661829503566706752010217663235

Wir gehen zunächst von der Idee aus, ˹\d\d\d\d\d˼ wiederholt anzuwenden. In Perl geht das ganz einfach: Mit @plz = m/\d\d\d\d\d/g wird ein Array erzeugt, bei dem jedes Element eine Postleitzahl ist (natürlich unter der Annahme, dass die Daten im Standardsuchraum $_ vorliegen, siehe Anmerkung zu Zeile 1 von »Verdoppelte Wörter« unter Perl). Bei anderen Sprachen wird dazu die »find«-Methode für reguläre Ausdrücke in einer Schleife aufgerufen. Ich konzentriere mich im Folgenden mehr auf die regulären Ausdrücke als darauf, wie sie in einer bestimmten Sprache angewendet werden; ich werde Perl für die Beispiele benutzen.

Zurück zum ˹\d\d\d\d\d˼. Folgendes wird sich gleich als wichtig erweisen: Die Regex passt immer und sofort, bis die ganzen Daten erschöpft sind – das Getriebe muss nie ein Zeichen weiterschalten, weil alle Daten Ziffern sind (ich nehme hier an, dass die Daten den Spezifikationen entsprechen; eine Annahme, die in der Praxis manchmal stimmt – und häufig nicht).

Also ist es ziemlich klar, dass eine Änderung von ˹\d\d\d\d\d˼ zu ˹66\d\d\d˼ gar nichts bringt – sobald ein Fehlschlag auftritt, schiebt das Getriebe die Regex um ein Zeichen weiter, und die Maschinerie gerät außer Takt: Es wird nach ˹66...˼ gesucht und nicht nach dem Anfang einer Fünfergruppe. Mit ˹66\d\d\d˼ wird ein falscher Treffer bei ›...5316694116...‹ gefunden, und das ist keine Postleitzahl.

Man könnte nun einen Zirkumflex oder ein ˹\A˼ vorne in die Regex einsetzen, aber das würde eine Postleitzahl nur dann erkennen, wenn sie zuvorderst im String auftritt. Wir müssen eine Methode finden, bei der die Regex im Takt bleibt, bei der aber unerwünschte Postleitzahlen ignoriert werden. Dazu müssen wir ganze Postleitzahlen »von Hand« überspringen – und nicht nur einzelne Ziffern, wie es das Getriebe automatisch tut.

Mit erwarteten Daten im Takt bleiben

Hier sind ein paar Möglichkeiten aufgelistet, wie die uninteressanten Postleitzahlen übersprungen werden können. Jeder der aufgezählten Ausdrücke kann vor dem Unterausdruck eingesetzt werden, der auf das passt, was uns eigentlich interessiert (˹(66\d\d\d)˼). Wir verwenden nicht-einfangende Klammern für die Postleitzahlen, die uns nicht interessieren, so dass die interessanten mit den einfangenden Klammern in $1 aufgefangen werden.

˹(?:[^6]\d\d\d\d|\d[^6]\d\d\d)*...˼

Diese Methode überspringt Postleitzahlen, sofern sie mit etwas anderem als 66 beginnen (vorsichtiger wäre vielleicht ˹[0-57-9]˼ statt ˹[^6]˼, aber ich nehme wie gesagt an, dass die Daten nur aus Ziffern bestehen). Übrigens – ˹(?:[^6][^6]\d\d\d)*˼ würde nicht funktionieren, weil es unerwünschte Postleitzahlen wie 65432 nicht erkennt und damit nicht überspringt.

˹(?:(?!66)\d\d\d\d\d)*...˼

Diese Methode überspringt Postleitzahlen, sofern sie nicht mit 66 beginnen. Die deutsche Umschreibung sieht fast gleich aus wie bei der vorherigen Lösung, aber die regulären Ausdrücke unterscheiden sich ziemlich. In diesem Fall erzeugt eine erwünschte Postleitzahl (eine, die mit 66 beginnt) bei ˹(?!66)˼ einen Fehlschlag, und damit endet auch das Überspringen von uninteressanten Postleitzahlen.

˹(?:\d\d\d\d\d)*?...˼

Bei dieser Methode wird ein nicht-gieriger Quantor benutzt, und Postleitzahlen werden nur übersprungen, wenn es nicht anders geht; das heißt, wenn es von einem später folgenden Unterausdruck, der passen soll, erzwungen wird. Aufgrund des minimalen Matchings wird ˹(?:\d\d\d\d\d)˼ überhaupt nur angewandt, wenn der darauf folgende Teil nicht passt (dann allerdings mehrfach, bis eben dieser folgende Teil einen lokalen Treffer findet).

Wir kombinieren die letzte Lösung mit ˹(66\d\d\d)˼ und bekommen:

@plz = m/(?:\d\d\d\d\d)*?(66\d\d\d)/g;

Das pickt die ›66xxx‹-er Postleitzahlen heraus und überspringt dazwischen aktiv (also nicht mit dem normalen Verhalten des Getriebes) die uninteressanten Zahlen. (In einem Listenkontext liefert »@array = m/.../g« eine Liste der Textstücke, die in allen Iterationen von einfangenden Klammerausdrücken erkannt wurden; siehe Alle Treffer herauspflücken – Listenkontext mit dem /g-Modifikator.) Diese Regex funktioniert mit dem /g-Modifikator, weil wir dafür gesorgt haben, dass die »aktuelle Position« nach jeder Iteration des /g eine Position am Anfang einer neuen Postleitzahl ist.

Den Takt auch bei Unerwartetem nicht verlieren

Haben wir wirklich sichergestellt, dass die Regex nur am Anfang einer Postleitzahl getestet wird? Nein! Wir überspringen zwar »von Hand« uninteressante Postleitzahlen zwischen jeweils zweien, die mit 66 beginnen, aber wenn die Regex bei der letzten interessanten PLZ angelangt ist, passt sie nicht mehr. Dann wird, wie immer, das Getriebe ein Zeichen weiterschalten und die Regex bei einer Position mitten in einer Postleitzahl anwenden – und unser Ansatz verlässt sich darauf, dass das nie passiert!

Betrachten wir noch einmal unsere Beispieldaten:

03824 53166 94116 15213661829503566706▵7▵5▵2▵010217663235

Hier sind die gefundenen Treffer fett gedruckt (der dritte davon ist der unerwünschte), die aktiv übersprungenen Postleitzahlen sind unterstrichen, und die durch das Weiterschalten des Getriebes erreichten Positionen sind markiert. Nach dem Treffer 66706 findet die eigentliche Regex keine weiteren Treffer mehr. Ist damit das Matching beendet? Nein, natürlich nicht. Das Getriebe nimmt seine Arbeit auf, schaltet Zeichen für Zeichen weiter und setzt die Regex bei jedem Zeichen neu an; wir geraten also außer Takt mit den eigentlichen Postleitzahlen. Nach dem vierten Zeichen überspringt die Regex 10217 und betrachtet 66323 fälschlicherweise als Postleitzahl.

Alle unsere drei Lösungen funktionieren nur dann zuverlässig, wenn sie am Anfang einer Postleitzahl angesetzt werden, aber das normale Verhalten des Getriebes durchkreuzt das. Man kann hier Abhilfe schaffen, indem man verhindert, dass das Getriebe weiterschaltet, oder dadurch, dass dieses Weiterschalten nicht zeichenweise passiert.

Bei den ersten zwei Methoden können wir das Weiterschalten dadurch verhindern, dass wir den Teil ˹(66\d\d\d)˼ durch Anhängen von ˹?˼ optional machen. Wir benutzen dazu die Tatsache, dass die vorangestellten Unterausdrücke ˹(?:(?!66)\d\d\d\d\d)*...˼ oder auch ˹(?:[^6]\d\d\d\d|\d[^6]\d\d\d)*...˼ nur dann verlassen werden, wenn wir gerade vor einer gesuchten Postleitzahl stehen oder wenn überhaupt keine Postleitzahlen mehr folgen (deshalb können wir diese Methode nicht mit dem dritten Ansatz verwenden). Das folgende ˹(66\d\d\d)?˼ erkennt also eine der gesuchten Postleitzahlen, wenn eine vorliegt, erzwingt aber kein Backtracking.

Auch diese Lösung ist nicht ganz unproblematisch. Die Regex passt jetzt auch (auf den Leerstring), wenn gar keine Postleitzahl gefunden wurde, deshalb müssen wir diese leeren Treffer mit den Mitteln der Programmiersprache ausschließen. Sie ist aber schnell, weil nur wenig Backtracking involviert ist und weil das Getriebe die Regex nie an einer neuen Position ansetzen muss.

Mit \G im Takt bleiben

Als allgemeinere Lösungsmethode können wir einfach ein ˹\G˼ (siehe Beginn der neuen (oder Ende der letzten) Mustersuche: \G) vor irgendeinen der drei Ausdrücke setzen. Wir hatten jeden der drei Unterausdrücke so konzipiert, dass er immer gerade nach einer Postleitzahl endet, also nach einer Fünfergruppe. Mit dem ˹\G˼ schaltet das Getriebe nicht weiter, denn bei den meisten Regex-Dialekten passt es nur, wenn der neue Treffer direkt an den vorherigen anschließt, ohne dass das Getriebe weiterschaltet. (Bei Ruby allerdings bezieht sich das ˹\G˼ auf den »Anfang des neuen Treffers«, nicht auf das »Ende des letzten Treffers«, siehe Ende der letzten Mustersuche oder Anfang der aktuellen?.)

Mit der zweiten Variante erhalten wir eine Lösung, bei der wir nicht hinterher leere Treffer aussondern müssen:

@plz = m/\G(?:(?!66)\d\d\d\d\d)*(66\d\d\d)/g;

Dieses Beispiel mit \G im größeren Zusammenhang

Ich weiß sehr wohl, dass dieses Beispiel konstruiert ist. Dennoch hat es uns eine Reihe von wertvollen Ideen vermittelt, wie man eine Regex mit den Daten synchronisiert. Wenn mir ein derartiges Problem in der Praxis begegnen würde, würde ich es wahrscheinlich nicht allein mit regulären Ausdrücken lösen. Vielleicht würde ich mit ˹\d\d\d\d\d˼ Fünfergruppen von Ziffern herauslösen und testen, ob diese mit ›66‹ beginnen. In Perl könnte das etwa so aussehen:

Im Kasten Ein Beispiel für den Gebrauch von \G in Perl ist ein besonders interessantes Beispiel für den Gebrauch von \G beschrieben, das allerdings Features benutzt, die es momentan nur in Perl gibt.