Regulärer Ausdruck, der nie ausgeführt wird
Ich habe einen kleinen, naiven regulären Ausdruck geschrieben, der Text in Klammern finden sollte:
re.search(r'\((.|\s)*\)', name)
Ich weiß, dass dies aus ein paar Gründen nicht der beste Weg ist, aber es hat gut funktioniert. Was ich suche, ist einfach eine Erklärung dafür, warum dieser Ausdruck für einige Streicher exponentiell länger wird und dann nie endet. Nachdem wir diesen Code monatelang ausgeführt hatten, blieb einer unserer Server plötzlich stecken und entsprach einer Zeichenfolge ähnlich der folgenden:
%Vor%Ich habe damit experimentiert und festgestellt, dass sich die Zeit für jeden Raum zwischen "y" und "z" verdoppelt:
%Vor%Aber auch andere Zeichen als ein Leerzeichen haben nicht den gleichen Effekt:
%Vor%Hinweis: Ich suche keinen besseren regulären Ausdruck oder eine andere Lösung für dieses Problem. Wir benutzen es nicht mehr.
2 Antworten
Katastrophales Backtracking
Wie CaffGeeks Antwort richtig andeutet, liegt das Problem an einer Form katastrophaler Rückverfolgung . Die beiden Alternativen entsprechen einem Leerzeichen (oder Tab) und dies wird beliebig oft gierig angewendet. Außerdem stimmt der Punkt mit den schließenden Klammern überein, so dass der Ausdruck, sobald der öffnende Teil übereinstimmt, immer mit dem Ende des Strings übereinstimmt, bevor er mühsam zurückgelenkt werden muss, um die schließende Klammer zu finden. Und während dieses Backtracking-Prozesses wird die andere Alternative an jedem Ort ausprobiert (was auch für Leerzeichen oder Tabs erfolgreich ist). Somit muss jede mögliche passende Kombinationssequenz versucht werden, bevor der Motor eine Position zurückverfolgen kann. Mit vielen Leerzeichen nach dem Schließen, summiert sich das schnell. Das spezifische Problem für den Fall, dass ein passender ClosePar vorhanden ist, kann gelöst werden, indem einfach der Sternquantifizierer faul gemacht wird (dh r'\((.|\s)*?\)' ), aber das Runaway Regex Problem existiert immer noch für den nicht übereinstimmenden Fall, in dem eine Öffnung vorhanden ist kein passender Schlüssel in der Betreffzeile.
Der ursprüngliche Regex ist wirklich, wirklich schlecht! (und stimmt auch nicht korrekt ab, wenn mehrere Parens geschlossen sind.)
Der korrekte Ausdruck, der den innersten Klammern entspricht (was sowohl für übereinstimmende als auch für nicht übereinstimmende Fälle sehr schnell ist), ist natürlich:
%Vor%Alle Regex-Autoren sollten MRE3!
lesenDies alles wird ausführlich (mit gründlichen Beispielen und empfohlenen Best Practices) in Jeffrey Friedls must-rege-for-regex-Autoren erklärt: Reguläre Ausdrücke beherrschen (3. Edition) . Ich kann ehrlich sagen, dass dies das nützlichste Buch ist, das ich je gelesen habe. Reguläre Ausdrücke sind ein sehr mächtiges Werkzeug, aber wie eine geladene Waffe muss mit großer Sorgfalt und Präzision angewendet werden (oder Sie schießen sich in den Fuß!)
Wahrscheinlich ein ReDos-Problem.
Siehe: Ссылка
Es ist möglich, bei schlecht konstruierten Regexes einen Denial-of-Service für reguläre Ausdrücke zu erstellen.
Zum Beispiel von hier: Ссылка
Dieser Regex ^(a+)+$
Für die Eingabe aaaaX gibt es im obigen Diagramm 16 mögliche Pfade. Aber für aaaaaaaaaaaaaaaaX gibt es 65536 mögliche Pfade, und die Anzahl ist doppelt für jedes zusätzliche a. Dies ist ein Extremfall, in dem der naive Algorithmus problematisch ist, da er viele Pfade durchlaufen muss und dann fehlschlägt.
Ich vermute, dass ein großer Teil des Problems mit Ihrer Regex diese (.|\s) ist, was etwas verwirrend ist, da \s bereits in . enthalten ist. Erstellt jedoch einen Optionspunkt.
EDIT: Ich denke, das war eine der besseren Erklärungen für das Thema, das ich gelesen habe.