50
Was ist die Komplexität in Bezug auf die Stringlänge, die für einen Vergleich eines regulären Ausdrucks in einer Zeichenfolge erforderlich ist?Was ist die Komplexität des regulären Ausdrucks?
A
Antwort
41
Die Antwort hängt davon ab, was genau Sie mit "regulären Ausdrücken" meinen. Klassische Regexe können compiled in Deterministic Finite Automata sein, die eine Zeichenfolge der Länge N in O(N) Zeit entsprechen können. Bestimmte Erweiterungen der Regex-Sprache ändern das zum Schlechteren.
Sie können das folgende Dokument von Interesse finden: Regular Expression Matching Can Be Simple And Fast.
+5
Ich liebe diesen Artikel. – tchrist
+0
Ich glaube nicht, dass es möglich wäre, die Testdaten für diesen Artikel zu bekommen? Mein Arbeitsplatz benutzt perlregex die ganze Zeit. Wären sie wirklich so langsam, würde unsere Hardware komplett ausfallen. – DeepDeadpool
7
unbegrenzt - Sie können einen regulären Ausdruck erstellen, der nie endet, in einer leeren Eingabezeichenfolge.
+0
Nur aus Neugier, könntest du ein Beispiel geben, Alex? –
+4
siehe man perlre - "'foo' = ~ m {(o?) *} X;". Perl hat einen speziellen Code, um in diesem Fall eine unendliche Rekursion zu erkennen und auszubrechen. –
5
Wenn Sie normal verwenden (TCS: keine Rückreferenz, Verkettung, Alternation, Kleene Stern) Regexp und Regexp ist bereits kompiliert, dann ist es O (n).
1
Wenn Sie nach engen asymptotischen Grenzen auf RegEx suchen (ohne Rücksicht auf den Ausdruck selbst), dann gibt es keinen. Wie Alex hervorhebt, können Sie eine Regex, die O (1) ist, oder eine Regex, die Omega (Unendlichkeit) ist, erstellen. Als reiner mathematischer Algorithmus wäre eine Engine für reguläre Ausdrücke viel zu kompliziert, um irgendeine Art von formaler asymptotischer Analyse durchzuführen (abgesehen von der Tatsache, dass eine solche Analyse im Grunde wertlos wäre).
Die Wachstumsrate eines bestimmten Ausdrucks (da dies tatsächlich ohnehin einen Algorithmus darstellt) wäre viel aussagekräftiger, wenn auch nicht unbedingt einfacher zu analysieren.
+0
Das sind Erweiterungen von formalen regulären Ausdrücken. Reguläre Ausdrücke, die gewöhnliche Konstrukte enthalten (z. B. keine Look-ahead-/Rückwärtsmuster), können nachweislich immer bei einer Eingabe in einer O-Länge (Länge der Eingabezeichenfolge) enden. –
+0
@clement Selbst die meisten Erweiterungen drücken den RE nicht über ein DFA hinaus. Zum Beispiel kann Python Regex immer von einem DFA modelliert werden. Wie auch immer, sobald Sie anfangen, mit Perl Regex zu arbeiten (und ich glaube, Javascript?), Wird es ein anderes Tier, das stattdessen einem TM entspricht. – BlackVegetable
Die Komplexität hängt mehr von der Art der Regex als von der Länge der Zeichenfolge ab. – LukeH
@LukeH Alternativ hängt es von der verwendeten Programmiersprache ab. Zum Beispiel kann Python Regex niemals die Computerleistung eines DFA überschreiten, aber Perl Regex kann Turing vollständig sein. – BlackVegetable
mögliches Duplikat von [Komplexität der Regex-Substitution] (http://stackoverflow.com/questions/21669/complexity-of-regex-substitution) – Kevin