Das Innenleben einer Regex-Engine als Bibliothek

• Es gibt den Autor des regex-Crates für Rust, der die Regex-Bibliothek von Rust verbessert und optimiert hat.
• Ein neues Crate namens regex-automata wurde geschaffen, das das Innenleben des regex-Crates über eine separate API zugänglich macht.
• Damit handelt es sich um die erste Regex-Bibliothek, die ihr Innenleben in diesem Umfang als separate versionierte Bibliothek offenlegt.
• Dieser Artikel bietet eine Anleitung zum Umschreibungsprozess für Verbesserungen, zu den Methoden der Problemlösung und zur API von regex-automata.
• Die Zielgruppe sind Rust-Programmierer und alle, die sich für die Implementierung von Regex-Engines auf Basis endlicher Automaten interessieren.
• Der Artikel gibt einen kurzen Überblick über die Geschichte des regex-Crates und seiner Entwicklung.
• Zu den Problemen, mit denen das regex-Crate konfrontiert war, gehörten Konfiguration, Tests, bestimmte API-Anfragen und der Bedarf an vollständig kompilierten DFAs.
• Die Neufassung löst diese Probleme und bietet eine flexiblere und besser optimierte Lösung.
• Durch die Veröffentlichung von regex-automata als separates Crate wird das Experimentieren mit zusätzlichen APIs und deren Weiterentwicklung möglich, ohne das Haupt-regex-Crate unübersichtlich zu machen.
• Der Artikel hebt die Vorteile der Nutzung von regex-automata und das Potenzial für weitere Verbesserungen im Bereich der Regex-Engines hervor.
• Der Artikel beschreibt das Programm regex-cli, das Kommandozeilenzugriff auf die API des regex-Crates bietet.
• Das Programm enthält Hilfswerkzeuge wie die Serialisierung kompilierter DFAs in Dateien und die Erzeugung von Rust-Code.
• Der Artikel zeigt Beispiele dafür, wie sich Unicode auf Regex-Muster auswirkt.
• Das Programm regex-cli kann verschiedene Datentypen im Ökosystem des regex-Crates debuggen und ausgeben.
• Es gibt den Befehl regex-cli find, mit dem sich Mehrfachmustersuchen unter Verwendung von Capture Groups ausführen lassen.
• Der Artikel erklärt den Datenfluss durch eine Regex-Engine, vom Parsen der Muster bis zum Aufbau der NFA.
• Die Literal-Extraktion ist eine wichtige Optimierungstechnik, die im regex-Crate verwendet wird.
• Literal-Extraktion bedeutet, Literale aus Regex-Mustern zu extrahieren, um potenzielle Treffer im Suchtext schnell zu identifizieren.
• Die Auswahl der zu suchenden Literale ist wichtig, um False Positives zu minimieren und die Latenz zu senken.
• Literal-Extraktion ist ein heuristischer Prozess zur Minimierung von False Positives und Latenzeffekten.
• Eine Richtlinie für die Literal-Extraktion ist, längere Literale zu bevorzugen und extrem kurze oder sehr häufige Literale zu vermeiden.
• Der Artikel beschreibt die Optimierung von Literal-Sequenzen in regulären Ausdrücken.
• Literal-Sequenzen sind Folgen von Zeichenketten, die als exakt übereinstimmende Strings behandelt werden.
• Im Optimierungsprozess werden Sequenzen identifiziert, die zur Leistungssteigerung unendlich gemacht werden können.
• Der Artikel erklärt den Prozess, durch den unterschiedliche Regexe unterschiedliche Literal-Sequenzen erzeugen können.
• Der Artikel behandelt auch den Prozess der Suche nach Literalen im Suchtext.
• Für die Suche nach einzelnen Teilstrings und mehreren Teilstrings werden unterschiedliche Algorithmen verwendet.
• Der Artikel führt in das Konzept von NFAs (nichtdeterministische endliche Automaten) und ihre Rolle in Regex-Engines ein.
• NFAs können in andere Typen umgewandelt werden und zum Beispiel zur Implementierung von DFAs (deterministische endliche Automaten) verwendet werden.
• Der Artikel liefert und erläutert detaillierte Beispiele zu den Bestandteilen einer NFA.
• Der Artikel erwähnt Optimierungen im neuen NFA-Compiler, die den Einsatz von Epsilon-Übergängen reduzieren.
• Der neue NFA-Compiler optimiert die Darstellung von NFAs durch die Verwendung sparsamer Zustände, die mehrere Byte-Bereiche enthalten.
• Diese Optimierung reduziert Overhead und beseitigt die Notwendigkeit von Epsilon-Übergängen.
• Die im früheren Compiler verwendete byteorientierte NFA war langsam und erforderte eine separate Kompilierung für Unicode- und byteorientierte NFAs.
• Der neue NFA-Compiler verarbeitet Unicode-Klassen, indem er UTF-8-Automaten in die byteorientierte NFA integriert.
• Der neue Compiler verwendet den Algorithmus von Daciuk, um minimale DFAs aus sortierten, nicht überlappenden Elementsequenzen zu berechnen.
• Rückwärtsübergänge werden mithilfe einer speziellen Datenstruktur namens Range Trie verarbeitet.
• Im Vergleich zum früheren Compiler erzeugt der neue NFA-Compiler NFAs mit weniger Zuständen und ohne Epsilon-Übergänge.
• Mit der Optimierung durch umgekehrte Reduktion kann die Größe der NFA weiter verringert werden, allerdings auf Kosten längerer Build-Zeiten.
• Insgesamt verbessert der neue NFA-Compiler die Leistung und vereinfacht die Verarbeitung von Unicode-Klassen in regulären Ausdrücken.
• Der Artikel diskutiert technische Probleme im Zusammenhang mit Zeichenkodierungen.
• Das Problem betrifft seltene Zeichen und ihre Darstellung in verschiedenen Kodierungsformaten.
• Der Artikel erwähnt bestimmte Zeichen und deren Häufigkeit in ihren jeweiligen Kodierungen.
• Der Artikel hebt die Komplexität und potenzielle Herausforderungen bei Zeichenkodierungen hervor.
• Der Artikel könnte für Softwareingenieure und Entwickler interessant sein, die mit Zeichenkodierungen arbeiten.
• Der Artikel behandelt NFA-Optimierungstechniken in Regex-Engines.
• Thompson-NFAs gelten wegen ihrer Epsilon-Übergänge als wenig skalierbar.
• Der Artikel stellt eine NFA-Optimierung vor, die Epsilon-Übergänge reduziert, indem die Alternation von Literalen eingeschränkt wird.
• Der neue NFA-Compiler erstellt ein Trie aus Literalen und wandelt es in eine NFA mit minimierten Epsilon-Übergängen um.
• Diese Optimierung erhält die Priorität von links nach rechts und verbessert die Suchleistung.
• Der Artikel erwähnt außerdem zukünftige Arbeiten an Glushkov-NFAs und an der Speicherung von NFAs in einer einzelnen zusammenhängenden Allokation.
• Das regex-Crate für Rust verwendet mehrere Regex-Engines, um Funktionsumfang und Suchleistung auszubalancieren.
• PikeVM ist die leistungsfähigste Regex-Engine im Crate und unterstützt alle Regex-Funktionen.
• PikeVM simuliert die NFA

[GN⁺]

Hacker-News-Kommentare

• Das Rust-regex-Crate ist legendär und ein wertvolles Werkzeug für die Community.
• Dieser Artikel geht tief auf die Änderungen und Verbesserungen im regex-Crate ein.
• Reguläre Ausdrücke sind ein leistungsstarkes Werkzeug, mit dem sich komplexe Aufgaben schnell erledigen lassen.
• In diesem Artikel wurde ein Buch empfohlen, um reguläre Ausdrücke zu meistern.
• Im Jahr 2001 verfügte der Editor Komodo über einen hochmodernen Debugger für reguläre Ausdrücke.
• Ripgrep ist ein Werkzeug, das der Suche in Code- und Textdateien Leben einhaucht.
• Ein Kommentator schlug vor, die Funktionalität regulärer Ausdrücke so zu erweitern, dass sie statt nur mit Strings auch mit Listen verwendet werden kann.
• Das regex-automata-Crate ist mit allen Textdatenstrukturen kompatibel.
• Ein Kommentator lobte die Arbeit von BurntSushi und brachte seinen Dank zum Ausdruck.
• Automa.jl ist eine reine Julia-Engine für reguläre Ausdrücke, die das Einfügen beliebigen Julia-Codes erlaubt.