Komplexität der Regex-Substitution

Question

Ich habe nirgendwo eine Antwort darauf bekommen.Wie hoch ist die Laufzeitkomplexität einer Regex-Übereinstimmung und -Ersetzung?

Bearbeiten:Ich arbeite in Python.Ich würde aber gerne allgemein etwas über die gängigsten Sprachen/Tools (Java, Perl, Sed) wissen.

Answer 1

Aus rein theoretischer Sicht:

Die mir bekannte Implementierung würde darin bestehen, einen deterministischen endlichen Automaten zu erstellen, um den regulären Ausdruck zu erkennen.Dies erfolgt in O(2^m), wobei m die Größe des regulären Ausdrucks ist, unter Verwendung eines Standardalgorithmus.Sobald dies erstellt ist, verläuft das Durchlaufen einer Zeichenfolge linear in der Länge der Zeichenfolge – O(n), wobei n die Zeichenfolgenlänge ist.Eine Ersetzung einer in der Zeichenfolge gefundenen Übereinstimmung sollte eine konstante Zeit sein.

Insgesamt gehe ich also von O(2^m + n) aus.

Answer 2

Weitere theoretische Informationen von möglicherweise Interesse.

Nehmen Sie der Übersichtlichkeit halber die Standarddefinition für einen regulären Ausdruck an

http://en.wikipedia.org/wiki/Regular_Language

aus der formalen Sprachtheorie.Praktisch bedeutet dies, dass das einzige Baustoff Alphabetsymbole, Operatoren von Verkettung, Wechsel und Kleene-Verschluss zusammen mit der Einheit und Nullkonstanten (die aus gruppentheoretischen Gründen erscheinen) sind.Im Allgemeinen ist es eine gute Idee, diesen Begriff trotz der täglichen Praxis in Skriptsprachen nicht zu überladen, was zu Unklarheiten führt.

Es gibt eine NFA-Konstruktion, die das Matching-Problem für einen regulären Ausdruck R und einen Eingangstext t in o (| r | | t |) Zeit und o (| r |) Raum löst, wo |-| ist die Längenfunktion.Dieser Algorithmus wurde von Myers weiter verbessert

http://doi.acm.org/10.1145/128749.128755

zur Zeit- und Raumkomplexität O(|r| |t| / log |t|) durch Verwendung von Automatenknotenlisten und dem Vier-Russen-Paradigma.Dieses Paradigma scheint nach vier russischen Jungs benannt zu sein, die ein bahnbrechendes Papier geschrieben haben, das nicht online ist.Das Paradigma wird jedoch in diesen Berechnung biologischen Vorlesungsnotizen veranschaulicht

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

Ich finde es lustig, ein Paradigma durch die Nummer und die Nationalität der Autoren anstelle ihrer Nachnamen zu benennen.

Das Matching-Problem für reguläre Ausdrücke mit zusätzlichen Backreferenzen ist NP-Complete, was von AHO nachgewiesen wurde

http://portal.acm.org/citation.cfm?id=114877

durch eine Reduktion des Scheitelpunktüberdeckungsproblems, das ein klassisches NP-vollständiges Problem ist.

Um regelmäßige Ausdrücke mit Backreferenzen zu entsprechen, konnten wir Backtracking (ähnlich wie die Perl Regex -Engine) einsetzen, um die möglichen Unterwörter des Eingangstextes T zu verfolgen, der den Variablen in R zugewiesen werden kann.Es gibt nur O (| T |^2) Subwords, die einer Variablen in r zugewiesen werden können.Wenn es N -Variablen in r gibt, gibt es mögliche Zuordnungen o (| t |^2n).Sobald eine Zuordnung von Substrings zu Variablen behoben ist, reduziert sich das Problem auf die einfache reguläre Ausdrucksübereinstimmung.Daher ist die schlimmste Komplexität für die Übereinstimmung mit regelmäßigen Ausdrücken mit Backreferenzen O (| t |^2n).

Beachten Sie jedoch, dass regelmäßige Ausdrücke mit Backreferenzen REGEXEN noch nicht voll ausgestattet sind.

Nehmen wir zum Beispiel das Symbol "egal" abgesehen von anderen Betreibern.Es gibt mehrere Polynomalgorithmen, die entscheiden, ob ein Satz von Mustern einem Eingabetxt übereinstimmt.Zum Beispiel Kucherov und Rusinowitch

http://dx.doi.org/10.1007/3-540-60044-2_46

Definieren Sie ein Muster als Wort w_1@w_2@...@w_n, wobei jedes w_i ein Wort (kein regulärer Ausdruck) ist und „@“ ein „egal“-Symbol variabler Länge ist, das in keinem der w_i enthalten ist.Sie leiten einen o ((| t | + | p |) log | p |) Algorithmus zum Abpassen einer Menge von Mustern P gegen einen Eingabetxt t ab, wobei | t | ist die Länge des Textes und | p | ist die Länge aller Wörter in P.

Es wäre interessant zu wissen, wie sich diese Komplexitätsmaßnahmen verbinden und was das Komplexitätsmaß für das Matching -Problem für reguläre Ausdrücke mit Backreferenzen, "egal" und andere interessante Merkmale praktischer regulärer Ausdrücke ist.

Leider habe ich kein Wort über Python gesagt ...:) :)

Answer 3

Hängt davon ab, was Sie als Regex definieren.Wenn Sie die Operatoren Verkettung, Alternative und Kleene-Stern zulassen, kann die Zeit tatsächlich sein O(m*n+m), Wo m ist die Größe einer Regex und n ist die Länge der Zeichenfolge.Sie tun dies, indem Sie einen NFA konstruieren (der linear ist). m) und es dann zu simulieren, indem die Menge der Zustände, in denen Sie sich befinden, beibehalten und aktualisiert wird (in O(m)) für jeden Eingabebuchstaben.

Dinge, die das Parsen von Regex erschweren:

• Klammern und Rückverweise:Die Erfassung ist mit dem oben genannten Algorithmus immer noch in Ordnung, würde jedoch die Komplexität erhöhen und wäre daher möglicherweise nicht durchführbar.Rückverweise erhöhen die Erkennungsleistung des regulären Ausdrucks und seine Schwierigkeit ist gut
• positiver Ausblick:ist nur ein anderer Name für Schnittmenge, was die Komplexität des oben genannten Algorithmus auf erhöht O(m^2+n)
• negativer Ausblick:eine Katastrophe für den Bau des Automaten (O(2^m), möglicherweise PSPACE-vollständig).Aber es sollte immer noch möglich sein, mit dem dynamischen Algorithmus so etwas anzugehen O(n^2*m)

Beachten Sie, dass sich die Dinge bei einer konkreten Umsetzung verbessern oder verschlechtern können.Als Faustregel gilt, dass einfache Funktionen schnell genug und eindeutig sein sollten (z. B.nicht wie a*a*) Regexes sind besser.

Answer 4

Um näher auf die Antwort von theprise einzugehen: Für die Konstruktion des Automaten ist O(2^m) der schlimmste Fall, obwohl es wirklich von der Form des regulären Ausdrucks abhängt (für einen sehr einfachen Ausdruck, der mit einem Wort übereinstimmt, liegt er in O( m), beispielsweise unter Verwendung der Knuth-Morris-Pratt-Algorithmus).

Answer 5

Hängt von der Implementierung ab.Welche Sprache/Bibliothek/Klasse?Es mag einen Best Case geben, dieser wäre jedoch sehr spezifisch für die Anzahl der Funktionen in der Implementierung.

Answer 6

Sie können Platz gegen Geschwindigkeit eintauschen, indem Sie anstelle eines DFA einen nichtdeterministischen endlichen Automaten erstellen.Dies kann in linearer Zeit durchlaufen werden.Im schlimmsten Fall könnte dies natürlich O(2^m) Platz erfordern.Ich gehe davon aus, dass sich der Kompromiss lohnt.

Answer 7

Wenn Sie nach Matching und Substitution suchen, bedeutet das Gruppierung und Rückverweise.

Hier ist ein Perl-Beispiel, in dem Gruppierung und Rückreferenzen verwendet werden können, um ein NP-Vollständigkeitsproblem zu lösen: http://perl.plover.com/NPC/NPC-3SAT.html

Dies (gepaart mit einigen anderen theoretischen Kleinigkeiten) bedeutet, dass die Verwendung regulärer Ausdrücke zum Abgleichen und Ersetzen NP-vollständig ist.

Beachten Sie, dass sich dies von der formalen Definition eines regulären Ausdrucks unterscheidet – der nicht über den Begriff der Gruppierung verfügt – und in polynomieller Zeit übereinstimmt, wie in den anderen Antworten beschrieben.