Ich versuche in Python eine Regexp zu finden, die mit einem beliebigen Zeichen übereinstimmen muss, aber drei oder mehr aufeinander folgende Kommas oder Semikola vermeidet. Mit anderen Worten, nur bis zu zwei aufeinanderfolgende Kommas oder Semikolons sind erlaubt.
So habe ich das zur Zeit:
%Vor%Und es scheint zu funktionieren wie erwartet:
%Vor%Aber wie ich anfange, die Länge des Eingabetextes zu erhöhen, scheint die Regexp viel mehr Zeit zu benötigen, um eine Antwort zu geben.
%Vor%Und schließlich bleibt es in diesem Stadium völlig stecken und die CPU-Auslastung steigt auf 100%.
Ich bin mir nicht sicher, ob die Regexp optimiert werden kann oder etwas anderes involviert ist, jede Hilfe wird geschätzt.
Sie stoßen auf katastrophales Backtracking .
Der Grund dafür ist, dass Sie die Trennzeichen optional gemacht haben und daher der [^,;]+ -Teil (der sich selbst in einer Wiederholungsgruppe befindet) Ihrer Regex viele Permutationen (von baaaaaaaz ) ausprobieren wird, bevor Sie es schließlich tun müssen gestehen Versagen zu, wenn man mit mehr als zwei Kommas konfrontiert wird.
RegexBuddy bricht den Match-Versuch nach 1.000.000 Schritten der Regex-Engine mit Ihrer letzten Testreihe ab. Python wird es weiter versuchen.
Stellen Sie sich die Zeichenfolge baaz,,, vor:
Wenn Sie Ihre Regex testen, muss die Regex-Engine alle diese Punkte überprüfen:
baaz,,<failure> baa + z,,<failure>
ba + az,,<failure>
ba + a + z,,<failure>
b + aaz,,<failure>
b + aa + z,,<failure>
b + a + az,,<failure>
b + a + a + z,,<failure>
vor dem Erklären des Gesamtfehlers. Sehen Sie, wie das exponentiell mit jedem zusätzlichen Zeichen wächst?
Ein Verhalten wie dieses kann mit Possessivquantifizern oder Atomgruppen vermieden werden, die beide von Pythons aktueller Regex-Engine leider nicht unterstützt werden. Aber Sie können leicht eine umgekehrte Überprüfung durchführen:
%Vor% ohne eine Regex zu benötigen. Wenn ,;, und die Likes ebenfalls auftreten und ausgeschlossen werden sollen, verwenden Sie die Lösung von Andrew.
Ich denke, das Folgende sollte tun, was Sie wollen:
%Vor% Dies schlägt fehl, wenn die Zeichenfolge drei oder mehr , oder ; in einer Zeile enthält. Wenn Sie wirklich wollen, dass es einem Zeichen entspricht, fügen Sie am Ende ein . hinzu.
Dies verwendet negatives Lookahead , was dazu führt, dass die gesamte Übereinstimmung fehlschlägt, wenn die Regex .*[,;]{3} übereinstimmen würde .
Versuchen Sie diesen regulären Ausdruck:
%Vor%Es passt wiederholt:
, noch ; oder , , auf die entweder kein weiteres , oder ein ,, folgt, gefolgt von einem weiteren , oder ; , auf die entweder kein weiteres ; oder ein ;; folgt, auf das kein weiteres ; folgt
bis das Ende erreicht ist. Es ist sehr effizient, da es früh versagt, ohne viel Rückverfolgung zu machen.