Atomare Gruppen und possessive Quantoren verwenden

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

Unsere ursprüngliche Regex mit dem unendlichen Matching hatte eigentlich nur bei einem Fehlschlag ein Problem. Wenn es einen Treffer gibt, ist sie an sich recht schnell, weil der Unterausdruck ˹[^\\"]+˼ (der normale Teil) den größten Teil des Suchstrings bewältigt. Weil ˹[...]+˼ in der Regel sehr gut optimiert wird (siehe dazu Optimierungen der Regex-Maschine) und dieser Teil der Regex den größten Teil des Suchstrings konsumiert, bleibt für die relativ langsame Alternation und den äußeren Quantor ˹(...)*˼ nur wenig zu tun.

Das Problem ist also, dass ˹"(\\.|[^\\"]+)*"˼ bei einem Fehlschlag stecken bleibt, weil durch das Backtracking immer wieder die gleichen sinnlosen abgespeicherten Zustände getestet werden. Wir wissen, dass die Zustände zu nichts führen, weil sie mit endlosen Permutationen immer wieder das Gleiche testen. (Wenn ˹abc˼ nicht auf ›foo‹ passt, passen auch ˹abc˼ oder ˹abc˼ nicht, ganz zu schweigen von ˹abc˼, ˹abc˼ oder ˹abc˼.) Wenn wir diese gespeicherten Zustände beseitigen könnten, würde die Maschine den Fehlschlag viel schneller erkennen.

Wir können diese Zustände auf zwei Arten beseitigen (oder ignorieren): mit atomaren Klammern oder mit possessiven Quantoren.

Bevor wir zum Backtracking bzw. dessen Vermeidung kommen, möchte ich die Reihenfolge der Alternativen vertauschen, und zwar von ˹"(\\.|[^\\"]+)*"˼ nach ˹"([^\\"]+|\\.)*"˼. So kommt der »normal«-Teil zuerst. Wie in den letzten Kapiteln immer wieder erwähnt wurde, muss man sehr genau auf die Reihenfolge der Alternativen achtgeben, wenn sie den gleichen Text erkennen könnten. In diesem Fall schließen sich aber die Alternativen gegenseitig aus (keine kann auf den Text passen, der von der anderen erkannt würde), daher können wir die Reihenfolge so wählen, wie sie uns am klarsten oder am effizientesten erscheint.

Ewiges Matching mit possessiven Quantoren vermeiden

Unsere »unendliche« Regex ˹"([^\\"]+|\\.)*"˼ enthält zwei Quantoren. Wir können den einen zu einem possessiven Quantor machen oder den anderen oder beide. Spielt das eine Rolle? Nun, die wesentlichen Backtrack-Probleme rühren von Zuständen her, die von ˹[...]+˼ abgespeichert wurden, also war meine erste Idee, diesen Quantor possessiv zu machen. Das ergibt eine Regex, die auch dann recht schnell ist, wenn kein Treffer gefunden wird. Andererseits werden, wenn wir ˹(...)*˼ possessiv machen, alle innerhalb der Klammer erzeugten Zustände fortgeworfen, also die von der Klammer mit dem Plus und die Zustände, die von der Alternation herrühren. Vielleicht bringt das mehr?

Wir müssen uns gar nicht entscheiden, weil beide Quantoren possessiv gemacht werden können. Welche der drei Möglichkeiten am schnellsten ist, hängt wahrscheinlich sehr von der Optimierung der possessiven Quantoren ab. Da nur das Java-Regex-Package von Sun die possessiven Quantoren implementiert, sind die Vergleichsmöglichkeiten begrenzt; ich habe bei einigen Tests für jede der drei Möglichkeiten gute Resultate erhalten. Offenbar hat Sun die possessiven Quantoren sehr gut optimiert.

Ewiges Matching mit atomaren Klammern vermeiden

Es ist verlockend, die normalen Klammern in ˹"([^\\"]+|\\.)*"˼ durch atomare zu ersetzen: ˹"(?>[^\\"]+|\\.)*"˼. Man muss aber hier begreifen, dass sich ˹(?>...|...)*˼ in Bezug auf die weggeworfenen Zustände sehr stark vom possessiven ˹(...|...)*+˼ aus dem vorherigen Abschnitt unterscheidet.

Beim possessiven ˹(...|...)*+˼ bleiben nach dem Matching des Unterausdrucks keinerlei gespeicherte Zustände zurück. Bei der atomaren Gruppe ˹(?>...|...)*˼ dagegen werden nur die Zustände beseitigt, die sich durch die Anwendung der Alternativen und der Alternation an sich ergeben. Der Stern befindet sich außerhalb des atomaren Konstrukts; alle »Diese Möglichkeit überspringen«-Zustände können von späterem Backtracking immer noch erreicht werden. Wenn wir auch diese vermeiden wollen, müssen wir eine zusätzliche atomare Klammer der Art ˹(?>(...|...)*)˼ verwenden. Nur diese erfüllt die gleiche Aufgabe wie das possessive ˹(...|...)*+˼ aus dem letzten Abschnitt.

˹(...|...)*+˼ und ˹(?>...|...)*˼ sind sehr gute Lösungen für das Problem des ewigen Matchings, aber die Zustände, die weggeworfen werden, sind nicht die gleichen. (Mehr über Gemeinsamkeiten und Unterschiede finden Sie unter Schnellere Fehlschläge mit atomaren Gruppen.)

  

<< zurück

vor >>