RE#: Hochleistungs-Derivatbasierte Regex-Abgleich mit Schnittmenge, Komplement und eingeschränkten Lookarounds

Wir präsentieren ein Werkzeug und die Theorie RE # für den Abgleich regulärer Ausdrücke, das auf symbolischen Derivaten basiert, kein Backtracking verwendet und zusätzlich zu den klassischen Operatoren auch Komplement, Schnittmenge und eingeschränkte Lookarounds unterstützt. Wir entwickeln die Theorie formal und zeigen, dass der Hauptabgleichsalgorithmus sowohl theoretisch als auch experimentell eine eingabelineare Komplexität aufweist. Wir führen eine gründliche Bewertung an beliebten Benchmarks durch, die zeigen, dass RE # mehr als 71 % schneller ist als die nächstschnellste Regex-Engine in Rust im Baseline-Test und alle fortschrittlichen Engines bei Erweiterungen der Benchmarks oft um mehrere Größenordnungen übertrifft.