Was ist die Komplexität des regulären Ausdrucks?

74

Wie komplex ist die Zeichenfolgenlänge, die für einen Vergleich regulärer Ausdrücke für eine Zeichenfolge erforderlich ist?

regex complexity-theory big-o Ahmad Farid
quelle
3
Die Komplexität hängt mehr von der Art des regulären Ausdrucks selbst 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 vollständig sein.
BlackVegetable
mögliches Duplikat der Komplexität der Regex-Substitution
Kevin

Antworten:

70

Die Antwort hängt davon ab, was Sie genau unter "regulären Ausdrücken" verstehen. Klassische Regexes kann kompiliert in deterministischen Finite Automata , die eine Zeichenfolge der Länge entsprechen können Nin der O(N)Zeit. Bestimmte Erweiterungen der Regex-Sprache ändern dies zum Schlechten.

Möglicherweise finden Sie das folgende Dokument von Interesse: Der Abgleich regulärer Ausdrücke kann einfach und schnell sein .

NPE
quelle
9
Ich liebe diesen Artikel.
Tchrist
Ich nehme nicht an, dass es möglich wäre, die für diesen Artikel verwendeten Testdaten abzurufen. Mein Arbeitsplatz verwendet ständig Perl-Regex. Wären sie wirklich so langsam, würde unsere Hardware komplett ausfallen.
DeepDeadpool
9

unbegrenzt - Sie können einen regulären Ausdruck, der niemals endet, in einer leeren Eingabezeichenfolge erstellen.

Alex Brown
quelle
2
Könnten Sie aus Neugier ein Beispiel geben, Alex?
5
siehe man perlre - "'foo' = ~ m {(o?) *} x;". Perl verfügt über einen speziellen Code, um in diesem Fall eine unendliche Rekursion zu erkennen und auszubrechen.
Alex Brown
7

Wenn Sie normales (TCS: keine Rückreferenz, Verkettung, Wechsel, Kleene-Stern) Regexp verwenden und Regexp bereits kompiliert ist, ist es O (n).

Royas
quelle
0

Wenn Sie nach engen asymptotischen Grenzen für RegEx suchen (ohne Rücksicht auf den Ausdruck selbst), gibt es keine. Wie Alex betont, können Sie einen regulären Ausdruck erstellen, der O (1) ist, oder einen regulären Ausdruck, der Omega (unendlich) ist. Als rein mathematischer Algorithmus wäre eine Engine für reguläre Ausdrücke viel zu kompliziert, um irgendeine formale asymptotische Analyse durchzuführen (abgesehen von der Tatsache, dass eine solche Analyse grundsätzlich wertlos wäre).

Die Wachstumsrate eines bestimmten Ausdrucks (da dies ohnehin einen Algorithmus darstellt) wäre weitaus aussagekräftiger, wenn auch nicht unbedingt einfacher zu analysieren.

Adam Robinson
quelle
1
Dies berücksichtigt Erweiterungen formaler regulärer Ausdrücke. Es kann nachgewiesen werden, dass reguläre Ausdrücke mit üblichen Konstrukten (z. B. keine Vorausschau- / Rückwärtsmuster) bei jeder Eingabe in einer O-Zeit (Länge der Eingabezeichenfolge) immer enden.
Clément
@clement Selbst die meisten Erweiterungen verschieben den RE nicht über einen DFA hinaus. Beispielsweise kann Python Regex immer von einem DFA modelliert werden. Sobald Sie jedoch mit Perl Regex (und ich glaube Javascript?) Arbeiten, wird es zu einem anderen Tier, das stattdessen einem TM entspricht.
BlackVegetable
Ähm, nein. Die Komplexität eines echten regulären Ausdrucks ist gut definiert.
Charlie Martin