Wie funktionieren reguläre Ausdrücke?

30

Angenommen, Sie haben ein Dokument mit einem Aufsatz geschrieben. Sie möchten diesen Aufsatz analysieren, um nur bestimmte Wörter auszuwählen. Cool.

Ist die Verwendung eines regulären Ausdrucks schneller als das zeilenweise und wortweise Analysieren der Datei, um nach einer Übereinstimmung zu suchen? Wenn ja, wie funktioniert das? Wie kannst du schneller gehen, als auf jedes Wort zu schauen?

Laser
quelle
5
Sie gehen davon aus, dass ein regulärer Ausdruck schneller ist (ohne Beweise), wissen aber nicht, warum? Vielleicht sollten Sie dann Ihre Annahme überdenken.
pdr
3
also die annahme. Wenn ich Beweise hätte, wäre es keiner, oder?
lazeR
4
Das ist nicht der Punkt. Der Punkt ist, was Sie zu dieser Annahme geführt hat ... Sie brauchen keine Beweise für Ihre Fragen, aber Sie brauchen Gründe für Ihre Annahmen.
Yannis
1
äh, ist nicht jedes Zeichen der Eingabezeichenfolge nur eine Zustandsmaschine in den nächsten Zustand zu versetzen. Ich verstehe nicht, wie jemand diese Operation verlangsamen könnte ...
tp1
2
Ich bin mir nicht sicher, ob es schneller gehen soll, aber mein Hauptgrund für die Verwendung regulärer Ausdrücke liegt in der Eleganz komplexer Übereinstimmungsmuster. Sie werden einfach keinen besseren Weg finden, sie in einer Codierungsumgebung zu artikulieren.
Mantorok

Antworten:

47

Wie funktioniert es?

Werfen Sie einen Blick auf die Automatentheorie

Kurz gesagt, jeder reguläre Ausdruck hat einen äquivalenten endlichen Automaten und kann zu einem endlichen Automaten kompiliert und optimiert werden. Die beteiligten Algorithmen finden Sie in vielen Compiler-Büchern. Diese Algorithmen werden von Unix-Programmen wie awk und grep verwendet.

Die meisten modernen Programmiersprachen (Perl, Python, Ruby, Java (und JVM-basierte Sprachen), C #) verwenden diesen Ansatz jedoch nicht. Sie verwenden einen rekursiven Backtracking-Ansatz, bei dem ein regulärer Ausdruck in einen Baum oder eine Folge von Konstrukten kompiliert wird, die verschiedene Unterabschnitte des regulären Ausdrucks darstellen. Die meisten modernen Syntaxen für "reguläre Ausdrücke" bieten Rückverweise, die außerhalb der Gruppe regulärer Sprachen liegen (sie haben keine Darstellung in endlichen Automaten) und die in einem rekursiven Rückverfolgungsansatz trivial implementiert werden können.

Die Optimierung ergibt normalerweise eine effizientere Zustandsmaschine. Beispiel: Wenn Sie aaaab | aaaac | aaaad betrachten, kann ein normaler Programmierer die einfache, aber weniger effiziente Suchimplementierung (drei Zeichenfolgen separat vergleichen) in zehn Minuten durchführen. Wenn man jedoch erkennt, dass es gleichbedeutend mit aaaa [bcd] ist, kann eine bessere Suche durchgeführt werden, indem zuerst vier 'a' gesucht werden und dann das fünfte Zeichen gegen [b, c, d] getestet wird. Der Optimierungsprozess gehörte vor vielen Jahren zu meinen Aufgaben als Compiler. Daher gehe ich davon aus, dass er auch in den meisten modernen regulären Ausdrucksmodulen verwendet wird.

Auf der anderen Seite haben Zustandsautomaten einen gewissen Vorteil, wenn sie Zeichenfolgen akzeptieren, da sie im Vergleich zu einer "trivialen Implementierung" mehr Platz beanspruchen. Stellen Sie sich ein Programm vor, mit dem die Anführungszeichen für SQL-Zeichenfolgen aufgehoben werden: 1) Beginnt und endet mit einfachen Anführungszeichen. 2) Einfache Anführungszeichen werden durch zwei aufeinanderfolgende einfache Anführungszeichen maskiert. Also: Eingabe ['a' ''] sollte Ausgabe [a '] ergeben. Bei einer Zustandsmaschine werden die aufeinanderfolgenden einfachen Anführungszeichen von zwei Zuständen behandelt. Diese beiden Zustände dienen dazu, den Eingabeverlauf so zu speichern, dass jedes Eingabezeichen genau nur einmal verarbeitet wird, wie im Folgenden dargestellt:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Meiner Meinung nach kann der reguläre Ausdruck in einigen trivialen Fällen langsamer sein, aber in der Regel schneller als ein manuell erstellter Suchalgorithmus, da die Optimierung vom Menschen nicht zuverlässig durchgeführt werden kann.

(Selbst in trivialen Fällen wie dem Durchsuchen eines Strings kann eine intelligente Engine den einzelnen Pfad in der Statusübersicht erkennen und diesen Teil auf einen einfachen Stringvergleich reduzieren und das Verwalten von Status vermeiden.)

Eine bestimmte Engine aus einem Framework / einer Bibliothek kann langsam sein, da die Engine eine Reihe anderer Dinge erledigt, die ein Programmierer normalerweise nicht benötigt. Beispiel: Die Regex-Klasse in .NET erstellt eine Reihe von Objekten, einschließlich Match, Groups und Captures.

Kodismus
quelle
2
Ich hätte es nicht besser sagen können. Das einzige , was ich möchte hinzufügen: Reguläre Ausdrücke können auch bilden für faule Programmierer. In dem genannten Beispiel Sie aaaab|aaaac|aaaadvs. aaaa[bcd]. Es muss ausdrücklich darauf hingewiesen werden, dass die beiden mathematisch äquivalent sind und denselben DFA erzeugen, wodurch Programmierer mehr Freiheit haben, einen regulären Ausdruck auf sinnvolle Weise darzustellen (nicht, dass dies üblich ist, aber ... weißt du). ..
riwalk
Danke, das
ergab
Ist dies ein Beispiel für ein triviales Problem, bei dem Regex übertrieben ist ?: stackoverflow.com/questions/18955099/…
Menelaos Bakopoulos
17

Reguläre Ausdrücke sehen einfach schnell aus, weil Sie schnelle Computer haben.

In den 1980er Jahren, als 1 MIPS ein schneller Computer war, waren reguläre Ausdrücke ein ziemlich großer Bereich der Sorge, Sorge und Forschung, da sie langsam und hässlich und rechenintensiv waren. Es folgte eine clevere Algorithmusentwicklung, die half - aber heutzutage sieht man praktisch gesehen das Wunder schneller Maschinen, die über die Risse tapezieren.

schnell_nun
quelle
2
Wenn Sie nur nach einem einzigen Wort suchen, sind beide Methoden gleich (oder der Ausdruck ist etwas langsamer). Bei einem komplexen Ausdruck (und einem relativ großen Text) ist der reguläre Ausdruck wahrscheinlich schneller als eine einfache Suche (vorausgesetzt, Sie schreiben die einfache Suche einfach (Sie können immer eine komplexe Suche schreiben, die so schnell ist)). Jetzt ist das Wetter, bei dem es wichtig ist, eine zu allgemeine Frage, und Sie müssen sie von Fall zu Fall prüfen.
Martin York
3
-1. Die Theorie des regulären Ausdrucks stammt aus den 50er Jahren und war maßgeblich an der Erstellung von lexikalischen Analysatoren (und damit auch Compilern) beteiligt. Sie erzeugen sehr effiziente Zustandsautomaten, die (nachweislich) die geringstmögliche Anzahl von Zuständen verwenden. Die resultierenden Zustandsautomaten können komplexe Muster viel schneller zuordnen als alles, was Sie von Hand schreiben könnten. Sie sehen schnell aus, weil sie schnell sind.
riwalk
Könnte meinen Standpunkt etwas verfehlt haben. Sie mögen "schnell" sein, aber das ist alles relativ - es gibt noch eine Menge Arbeit zu erledigen. Einige der anderen Antworten hier sind ebenfalls lesenswert.
quick_now
Ist diese Antwort für die Frage relevant? und wie 13 upvotes?
Sadanand,
7

Warum sind sie Ihrer Meinung nach schneller als das Durchsuchen des Dokuments?

Sie können einige Tricks ausführen, z. Wenn Sie nach einem 10-Buchstaben-Wort suchen, das mit A beginnt und mit B endet, und wenn Sie ein A finden und das Zeichen 9 Stellen weiter nicht B ist, können Sie einiges überspringen. siehe Knuth-Morris-Pratt-Algorithmus

Martin Beckett
quelle
5

Was macht einen regulären Ausdruck schnell?

Eigentlich sind sie nicht. Nicht sehr viel. Es ist nur so, dass sie für die meisten von uns nicht langsam genug sind, um es zu bemerken. Zurück in den alten langsamen Tagen war es viel auffälliger.

Sie sind auch nicht für jeden Job das richtige Werkzeug - der Hammer .

Turm
quelle
+1 Danke, dass du mich an dieses besondere Kunstwerk erinnert hast ...
yannis
5

RegExs sind vergleichsweise schneller als der Code, den Sie möglicherweise schreiben, da die meisten Bibliotheken das Ergebnis vieler Entwickler sind, die viele Jahre damit verbracht haben, sie zu optimieren, um alle nur möglichen Performanceeinbußen zu erzielen. Es ist schwierig für eine einzelne Person, dies in ihrem eigenen Suchcode zu duplizieren.

GroßmeisterB
quelle
4
s / quietschen / quetschen /?
Péter Török,
4

Ihre Grundannahme ist falsch.

Reguläre Ausdrücke sind nicht immer schneller als eine einfache Suche. Es hängt alles vom Kontext ab. Dies hängt von der Komplexität des Ausdrucks, der Länge des durchsuchten Dokuments und einer Vielzahl von Faktoren ab.

Was passiert ist, dass der reguläre Ausdruck in einen einfachen Parser kompiliert wird (was Zeit kostet). Wenn das Dokument klein ist, überwiegt diese zusätzliche Zeit jeden Vorteil. Wenn der Ausdruck einfach ist, bietet der reguläre Ausdruck keinen Vorteil.

Wenn der Ausdruck komplex und das Dokument groß genug ist, können Sie einen gewissen Nutzen daraus ziehen. Ob dies wichtig genug ist, um zu berücksichtigen, dass reguläre Ausdrücke schneller sind, hängt stark davon ab, wie viel Aufwand Sie in die Suche investieren möchten.

Ich versuche zu sagen, dass es keine verallgemeinerte, pauschale Antwort gibt. Wenn Sie einen bestimmten Ausdruck (und eine bekannte Dokumentgröße) haben, können Sie sagen, dass Sie eine Ja / Nein-Antwort darauf erhalten, ob der Ausdruck schneller ist als eine einfache Suche (und warum).

Der eigentliche Vorteil von regulären Ausdrücken besteht darin, dass Sie, sobald Sie wissen, wie sie geschrieben werden, eine komplexe Suche präzise ausdrücken können. Da es sich um ein verallgemeinertes Formular handelt, können Sie dann Tools erstellen, die Suchen auf eine Weise ermöglichen, die im allgemeinen Fall nützlich ist. Dies ist in der Regel mindestens so schnell wie eine einfache Suche (bei Dokumenten mit minimaler Größe; bei kleineren Dokumenten spielt dies keine Rolle, da diese auch dann noch schnell genug sind, wenn sie langsamer sind).

Martin York
quelle
1

Es ist plausibel, dass in einigen Hochsprachen (möglicherweise Javascript) die Verwendung einer in einer Niedrigsprache (möglicherweise C) implementierten Regex-Bibliothek schneller ist als das Schreiben von Parser-Logik in der Hochsprache.

Plausibel - Ich habe keine Ahnung, ob dies jemals tatsächlich der Fall ist.

Steve Bennett
quelle
Schön! Auch das habe ich mir überlegt. Aber mit den heutigen Prozessoren, die viel schneller sind als ihre Vorgänger, kann ich mit Sicherheit sagen, dass Sie, wenn Sie Code effizient schreiben, den Unterschied selten erkennen können. Ich bin eigentlich im Großen und Ganzen nicht wirklich über die gesamte reguläre Hypothese eines schnelleren Ausdrucks gaga! ;-)
user3833732