Regulärer Ausdruck Implementierungsdetails

A question that I answered hat mich gefragt:Regulärer Ausdruck Implementierungsdetails

Wie reguläre Ausdrücke in Python implementiert? Welche Art von Effizienzgarantien gibt es? Ist die Implementierung "Standard" oder unterliegt sie Änderungen?

Ich dachte, dass reguläre Ausdrücke als DFAs implementiert werden würden, und waren daher sehr effizient (erfordert höchstens einen Scan der Eingabezeichenfolge). Laurence Gonsalves hat einen interessanten Punkt angesprochen, dass nicht alle reguläre Python-Ausdrücke regulär sind. (Sein Beispiel ist r "(a +) b \ 1", was einer Anzahl von a's, a b und dann der gleichen Anzahl von a's wie vorher entspricht). Dies kann eindeutig nicht mit einem DFA implementiert werden.

Also, um zu wiederholen: Was sind die Implementierungsdetails und Garantien von Python regulären Ausdrücken?

Es wäre auch schön, wenn jemand (angesichts der Implementierung) eine Erklärung geben könnte, warum die regulären Ausdrücke "cat | catdog" und "catdog | cat" zu unterschiedlichen Suchergebnissen in der Zeichenfolge führen " catdog ", wie in der question that I referenced before erwähnt.

Quelle

2009-05-09 Tom

Die heutigen regulären Ausdruck Implementierungen haben weit mehr Funktionen als die klassische Definition von regulären Ausdrücken beschreibt. – Gumbo

@Gumbo: In der Tat tun sie ... das ist der Grund für meine Frage. Ich bin neugierig auf eine bestimmte Implementierung, da es nicht sicher ist anzunehmen, dass ein DFA verwendet wird (wegen dieser zusätzlichen Funktionen). – Tom

Verwenden Sie die Quelle Luke (http://svn.python.org/view/python/trunk/Lib/re.py?view=markup). Es scheint tatsächlich ziemlich gut dokumentiert zu sein. –

Pythons Re-Modul basierte auf PCRE, aber hat sich auf ihre eigene Implementierung bewegt.

Hier ist der Link zum C code.

Es scheint, als ob die Bibliothek auf rekursive Rückverfolgung basiert, wenn ein falscher Pfad erstellt wurde.

alt text

Regulärer Ausdruck und Textgröße n
a? ⁿ ein ⁿ ein ⁿ

Beachten Sie passend, dass dieser Graph nicht repräsentativ für den normalen Regex sucht ist.

http://swtch.com/~rsc/regexp/regexp1.html

Quelle

2009-05-09 23:03:17 Unknown

(Ich merke, dass dieser Kommentar zu spät ist) Ich mag deine Erklärung, außer dass ich nicht glaube, dass der letzte Teil korrekt ist, wenn man "cat | catdog" vergleicht. Die Verwendung von "cat | catdog" erzeugt "cat" als Ergebnis und "catdog | cat" erzeugt als Ergebnis "catdog". Grundsätzlich kommt es auf die Reihenfolge an. Es gibt zwei Dinge. Zuallererst findet 'findall' nur alle nicht überlappenden Übereinstimmungen. Du solltest also nicht "Katze" UND "Katzenhund" erwarten. Zweitens, wenn ich dies umsetze, denke ich, es ist leicht zu sagen, dass die NFA in eine DFA umgewandelt werden kann, und Sie hätten dann "c -> a -> * t * -> d -> o -> * g *" wo Sternchen bezeichnen einen Endzustand. – Tom

(Fortsetzung ...): Im Grunde ist das "t" ein Endzustand, und ich denke, dass die Suche immer nur "Katze" zurückgeben sollte, denn das ist so weit wie nötig, um ein Spiel zu finden. Trotzdem war deine Antwort hilfreich und ich werde sie akzeptieren (Monate später :-). – Tom

DFAs sind jedoch kein perfekter Ansatz. Die Übereinstimmung von '[ab] * b [ab]^n 'erfordert' O (2^n) 'Speicher unter Verwendung eines DFA, aber kann in linearer Zeit und Speicher unter Verwendung eines NFA erfolgen. –

Es gibt keine „Effizienz garantiert“ auf Python REs mehr als auf jedem anderen Teil der Sprache (C++ 's Standard-Bibliothek ist der einzige weit verbreitete Sprache Standard Ich weiß, dass solche Standards zu etablieren versucht - aber es gibt keine Standards, nicht einmal in C++, was besagt, dass, zum Beispiel, das Multiplizieren von zwei Ints eine konstante Zeit dauern muss oder ähnliches); Es gibt auch keine Garantie, dass große Optimierungen zu keinem Zeitpunkt angewendet werden.

Heute stellte F. Lundh (ursprünglich für die Implementierung von Pythons aktuellem RE-Modul usw. verantwortlich) Unladen Swallow bei Pycon Italia vor und erwähnte, dass eine der Möglichkeiten, reguläre Ausdrücke direkt in den LLVM-Zwischencode zu kompilieren (Da ihr eigener Bytecode-Flavor von einer Ad-hoc-Laufzeit interpretiert wird) - da normaler Python-Code auch in LLVM kompiliert wird (in einer bald erscheinenden Version von Unladen Swallow), könnte ein RE und sein umgebender Python-Code dann zusammen optimiert werden, manchmal sogar ziemlich aggressiv. Ich bezweifle, dass so etwas bald "produktionsfertig" sein wird.

Quelle

2009-05-10 21:01:56

Matching regular expressions with backreferences is NP-hard, die mindestens so hart wie NP-Complete ist. Das bedeutet im Grunde, dass es so schwierig ist wie jedes Problem, dem Sie wahrscheinlich begegnen werden, und die meisten Informatiker denken, dass es im schlimmsten Fall exponentielle Zeit erfordern könnte.Wenn Sie solche "regulären" Ausdrücke (die im technischen Sinn nicht wirklich sind) in polynomieller Zeit abgleichen könnten, könnten Sie a million bucks gewinnen.

Quelle

2009-10-28 04:24:21

Regulärer Ausdruck Implementierungsdetails

Antwort

Verwandte Themen