Gestern war StackOverflow eine halbe Stunde lang nicht verfügbar. Später schrieben sie einen Blog-Beitrag darüber , in dem sie ausführlich darlegten, dass das Problem auf eine unerwartet hohe Komplexität des Abgleichs regulärer Ausdrücke zurückzuführen sei.
Kurz gesagt, der reguläre Ausdruck a+bwird beim Ausführen der Zeichenfolge aaaaaaaaaaaaaacin der Zeit wobei die Anzahl der Zeichen ist, da Backtracking verwendet wird.a
Sie können das Problem mit dem folgenden Python-Code reproduzieren, dessen Ausführung auf meinem Computer mehr als 4 Sekunden dauert:
import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x')
print(time.time() - start)
Das war sehr überraschend für mich; Ich hätte gedacht, dass ein Regex-Matcher effizienter arbeitet, z. B. indem er einen DFA aus dem Regex erstellt und dann die gewünschte Zeichenfolge durchläuft, was ich für (ohne die DFA-Konstruktion).
(Zum Beispiel geht das Buch Einführung in Algorithmen von Cormen, Leiserson, Rivest einen ähnlichen Algorithmus auf dem Weg zur Einführung des Knuth-Morris-Pratt-Algorithmus durch).
Meine Frage: Gibt es etwas inhärent Schwieriges beim Abgleichen regulärer Ausdrücke, das keinen -Algorithmus zulässt , oder sprechen wir einfach von einer ineffizienten Implementierung (in Python, in was auch immer StackOverflow verwendet, usw.)?
quelle
Antworten:
Wenn Sie nur reguläre Ausdrücke analysieren wollten, hätten Sie solche Probleme nicht (es sei denn, Sie wären ein wirklich inkompetenter Programmierer, denke ich). Vorsichtsmaßnahmen umfassen die Zeit, die zum Erstellen eines Automaten benötigt wird. Ein asymptotisch schlechterer Algorithmus kann in der Praxis in vielen Fällen den Automatenansatz übertreffen.
Das eigentliche Problem ist wahrscheinlich , dass sie mit Bibliotheksfunktionen , die Angebote zu bekommen regexps , die Art und Weise mächtiger als einfache reguläre Ausdrücke. Funktionen wie übereinstimmende Gruppen führen zu einer weiteren Komplexität.
In diesem Fall traten Probleme auf, weil diese Engines mit Teilzeichenfolgen übereinstimmen (mit einfachen regulären Ausdrücken stimmen wir normalerweise nur mit ganzen Eingaben überein) und Backtracking verwenden . lange Teilübereinstimmungen, die schließlich nicht übereinstimmen, verursachen lange Rückverfolgungen. Im Wesentlichen ist dies der schlechteste Fall für einen naiven String-Matching mit quadratischer Zeit.
Kann das verbessert werden? Könnte sein. Unter Verwendung der Ideen aus String-Matching-Automaten würden wir nicht zum zweiten Symbol zurückkehren, sondern zum Anfang des längsten Suffix, das einem Präfix des Musters entspricht. Aber da das Muster nicht mehr festgelegt ist, ist es sicherlich nicht trivial, die Ideen zu erweitern.
quelle