Unterzeichenfolge stimmt schneller mit regulärem Ausdruck überein?

Question

Nach dem Lesen von RE/NFA und DFA, scheint es, dass das Finden einer Teilzeichenkette innerhalb einer Zeichenkette tatsächlich asymptotisch schneller sein kann, indem man eine RE anstelle einer Brute-Force-O (mn) -Findung verwendet. Meine Schlussfolgerung ist, dass ein DFA tatsächlich den Status beibehalten und vermeiden würde, jeden Charakter im "Heuhaufen" mehr als einmal zu verarbeiten. Daher können Suchen in langen Strings viel schneller sein, wenn sie mit regulären Ausdrücken ausgeführt werden.

Dies gilt natürlich nur für RE-Matcher, die von NFA in DFA konvertieren.

Hat jemand im echten Leben eine bessere Saitenanpassungsleistung bei der Verwendung von RE erfahren als bei einem Brute-Force-Matcher?

Answer 1

Zunächst würde ich empfehlen, dass Sie den Artikel über Interna regulärer Ausdrücke in mehreren Sprachen lesen: Regular Expression Matching Can Be Simple And Fast.

Da Regexps in vielen Sprachen nicht nur zum Abgleich dienen, sondern auch die Möglichkeit zum Gruppen- und Rückverweisen bieten, verwenden fast alle Implementierungen das sogenannte "Backtracking", wenn NFA aus dem gegebenen Regexp erstellt wird. Und diese Implementierung hat eine exponentielle Zeitkomplexität (im schlimmsten Fall).

Es könnte RE-Implementierung über das DFA (mit Gruppenerfassung) sein, aber es hat einen Overhead (siehe Laurikaris Papier NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions).

Für die einfache Teilstringsuche können Sie den Knuth-Morris-Pratt Algorithmus verwenden, mit dem DFA Teilstrings suchen kann, und es hat optimale O (len (s)) Komplexität. Aber es hat auch Overhead, und wenn Sie naive Annäherung (O (nm)) gegen diesen optimalen Algorithmus auf realen Wörtern und Phrasen testen (die nicht so repetitiv sind), könnten Sie feststellen, dass der naive Ansatz im Durchschnitt besser ist.

Für die exakte Teilstringsuche können Sie auch Boyer–Moore algo ausprobieren, das eine Worst-Case-Komplexität von O (mn) aufweist, aber im Durchschnitt besser als KMP auf realen Daten arbeitet.

Answer 2

Wenn Sie sich die Dokumentation für die meisten Sprachen ansehen, wird es erwähnen, dass Sie die Nicht-Regex-Version aus Leistungsgründen verwenden sollten ... Beispiel: http://www.php.net/manual/en/function.preg-split.php besagt: "Wenn Sie nicht brauchen Mit der Kraft regulärer Ausdrücke können Sie Alternativen wie explode() oder str_split() schneller (wenn auch einfacher) wählen. "

Dies ist ein Kompromiss, der überall existiert. Je flexibler und funktionsreicher eine Lösung ist, desto schlechter ist ihre Leistung.

Answer 3

Die meisten in der Praxis verwendeten regulären Ausdrücke sind PCRE (Perl-Compatible Regular Expressions), die breiter als die normale Sprache sind und daher nicht mit einer regulären Grammatik ausgedrückt werden können. PCRE hat Dinge wie positive/negative Lookahead/Lookbehind-Assertionen und sogar Rekursion, so dass das Parsen einige Zeichen mehr als einmal verarbeiten muss. Sicher, es hängt alles von einer bestimmten RE-Implementierung ab: ob es optimiert ist, ob die Ausdrücke innerhalb der Grenzen der normalen Grammatik bleiben oder nicht.

Persönlich habe ich keine Art von Leistungsvergleich zwischen den beiden gemacht. Meiner Erfahrung nach hatte ich jedoch nie Leistungsprobleme mit Brute-Force-Suchen und Ersetzen, während ich mehrfach mit Leistungsengpässen in der RE-Umgebung zu kämpfen hatte.