it-swarm-eu.dev

Wie funktionieren reguläre Ausdrücke tatsächlich?

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 Parsen der Datei und das wortweise Suchen nach einer Übereinstimmung? Wenn ja, wie funktioniert es? Wie können Sie schneller gehen, als jedes Wort zu betrachten?

30
lazeR

Wie funktioniert es?

Schauen Sie sich Automatentheorie an

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, der einen regulären Ausdruck kompiliert Die meisten modernen Syntaxen für "reguläre Ausdrücke" bieten Rückreferenzen, die außerhalb der Gruppe der regulären Sprachen liegen (sie haben keine Darstellung in endlichen Automaten) und in denen sie trivial implementiert werden können rekursiver Backtracking-Ansatz.

Die Optimierung ergibt normalerweise eine effizientere Zustandsmaschine. Beispiel: Betrachten Sie aaaab | aaaac | aaaad. Ein normaler Programmierer kann die einfache, aber weniger effiziente Suchimplementierung (drei Zeichenfolgen getrennt vergleichen) in zehn Minuten ausführen. Wenn Sie jedoch feststellen, dass es aaaa [bcd] entspricht, können Sie eine bessere Suche durchführen, indem Sie zuerst vier 'a' suchen und dann das 5. Zeichen gegen [b, c, d] testen. Der Optimierungsprozess war vor vielen Jahren einer meiner Compiler-Heimaufgaben, daher gehe ich davon aus, dass er auch in den meisten modernen Engines für reguläre Ausdrücke enthalten ist.

Auf der anderen Seite haben Zustandsautomaten einen gewissen Vorteil, wenn sie Zeichenfolgen akzeptieren, da sie im Vergleich zu einer "trivialen Implementierung" mehr Speicherplatz belegen. Stellen Sie sich ein Programm vor, um Anführungszeichen für SQL-Zeichenfolgen zu entfernen, dh: 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 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 normalerweise schneller als ein manuell gestalteter Suchalgorithmus, da die Optimierung vom Menschen nicht zuverlässig durchgeführt werden kann.

(Selbst in trivialen Fällen wie dem Durchsuchen einer Zeichenfolge kann eine Smart Engine den einzelnen Pfad in der Statuszuordnung erkennen und diesen Teil auf einen einfachen Zeichenfolgenvergleich 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 ausführt, die ein Programmierer normalerweise nicht benötigt. Beispiel: Die Regex-Klasse in .NET erstellt eine Reihe von Objekten, einschließlich Match, Groups und Captures.

47
Codism

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, Besorgnis und Forschung, da sie langsam und hässlich und rechenintensiv waren. Eine clevere Algorithmusentwicklung folgte und half - aber für alle praktischen Zwecke sehen Sie heutzutage das Wunder schneller Maschinen, die über die Risse tapezieren.

17
quickly_now

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

Es gibt einige Tricks, die Sie tun können, z. Wenn Sie nach einem 10-Buchstaben-Wort suchen, das mit A beginnt und mit B endet, können Sie einige überspringen, wenn Sie ein A finden und das 9-stellige Zeichen nicht B ist. siehe Knuth-Morris-Pratt-Algorithmus

7
Martin Beckett

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. In den alten, langsamen Tagen war es viel auffälliger.

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

5
Rook

RegEx's sind vergleichsweise schneller für 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 die letzte mögliche Leistung herauszuholen. Es ist schwierig für eine einzelne Person, dies in ihrem eigenen Suchcode zu duplizieren.

5
GrandmasterB

Ihre Grundvoraussetzung 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 braucht). Wenn das Dokument klein ist, überwiegt diese zusätzliche Zeit den Vorteil. Wenn der Ausdruck einfach ist, bietet Ihnen der reguläre Ausdruck keinen Vorteil.

Wenn der Ausdruck komplex und das Dokument groß genug ist, können Sie einige Vorteile erzielen. Ob dies wichtig genug ist, um reguläre Ausdrücke als schneller zu betrachten, hängt stark davon ab, wie viel Aufwand Sie in die Suche investieren möchten (auch reguläre Ausdrücke können einige Optimierungen aufweisen, die eine Bibliothek bereitstellen könnte, die Sie nicht an sich selbst gedacht hätten).

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

Der eigentliche Vorteil von regulären Ausdrücken besteht darin, dass Sie, sobald Sie verstanden haben, wie man sie schreibt, eine komplexe Suche präzise ausdrücken können. Da es sich um eine verallgemeinerte Form handelt, können Sie dann Tools erstellen, die die Suche auf eine Weise ermöglichen, die im allgemeinen Fall nützlich ist. Es ist normalerweise mindestens so schnell wie eine einfache Suche (bei Dokumenten mit minimaler Größe; bei Dokumenten, die kleiner als diese sind, spielt es keine Rolle, da es, selbst wenn es langsamer ist, immer noch schnell genug ist).

4
Martin York

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

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

1
Steve Bennett