💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

Dieser Artikel etabliert die fein abgestufte rechnerische Komplexität des Matchings von regulären Ausdrücken mit Rückwärtsreferenzen, indem er bedingte untere Schranken unter den Annahmen von SETH und der Dreieckserkennung beweist und gleichzeitig einen verbesserten $O(n \log^2 n)$ -Algorithmus für einmal verwendete Rückwärtsreferenzen vorstellt.

Ursprüngliche Autoren: Soh Kumabe, Yuya Uezato

Veröffentlicht 2026-05-11

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Soh Kumabe, Yuya Uezato

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Der „Regex"-Stau

Stellen Sie sich vor, Sie sind ein Sicherheitsbeamter an einem Club (dem Computersystem). Sie haben eine Liste von Regeln (einen Regulären Ausdruck), wer hereinkommen darf.

Einfache Regeln: „Nur Personen mit roten Hemden." Das ist leicht zu prüfen. Sie schauen auf ein Hemd, sagen „Rot? Ja, rein." Es dauert gleich viel Zeit, egal ob die Schlange 10 oder 10.000 Personen lang ist.
Das Problem (ReDoS): Manchmal basteln Hacker eine spezifische Schlange von Personen, die den Beamten dazu bringt, eine massive Menge unnötiger Arbeit zu verrichten. Statt eine Person zu prüfen und weiterzumachen, prüft der Beamte Person A, dann Person B, dann wieder Person A, dann Person C, dann wieder Person A ... bis der Beamte vor Erschöpfung zusammenbricht. Dies wird als Denial-of-Service-Angriff (ReDoS) bezeichnet.

In der realen Welt hat dies massive Websites wie Stack Overflow und Cloudflare zum Absturz gebracht. Das Paper stellt fest, dass selbst eine „quadratische" Verlangsamung (wo das Prüfen von 100 Personen 10.000 Schritte erfordert) ausreicht, um ein System zum Absturz zu bringen.

Der Bösewicht: „Backreferences" (Rückbezüge)

Standardregeln sind einfach. Aber moderne „Regex"-Engines verfügen über eine supermächtige Funktion namens Backreferences.

Die Analogie:
Stellen Sie sich eine Regel vor, die sagt: „Finde ein Wort, merke es dir, und stelle dann sicher, dass exakt dasselbe Wort später wieder erscheint."

Beispiel: „Finde ein Wort, nenne es 'X'. Finde dann 'X' erneut."
Wenn die Eingabe apple ... apple lautet, funktioniert es.
Wenn die Eingabe apple ... banana lautet, schlägt es fehl.

Diese Funktion ist für Programmierer unglaublich nützlich, macht aber die Arbeit des „Beamten" viel schwieriger. Der Beamte muss sich merken, was er früher gesehen hat, und ständig damit vergleichen, was er gerade sieht. Das Paper fragt: Können wir einen Beamten bauen, der schnell genug ist, um diese komplexen Regeln zu bewältigen, ohne müde zu werden?

Die Erkenntnisse des Papers: Das Gute, das Schlechte und das Hässliche

Die Autoren untersuchten genau, wie schwer es ist, diese Matching-Probleme zu lösen. Sie unterteilten es in zwei Seiten: Schwierigkeit (Warum es schwierig ist) und Algorithmen (Wie man es löst).

1. Die schlechte Nachricht: Manche Regeln lassen sich nicht beschleunigen

Das Paper beweist, dass es für bestimmte Arten komplexer Regeln keine „Wunderwaffe" gibt, um sie schnell zu machen.

Das „Dreieck"-Problem: Sie zeigten, dass wenn Sie eine Regel haben, die zwei Variablen verwendet (wie das Merken von zwei verschiedenen Wörtern und das spätere Prüfen davon), das Lösen so schwer ist wie das Finden eines Dreiecks in einem riesigen sozialen Netzwerk-Graphen. Wenn Sie die Regel schnell lösen könnten, könnten Sie das Graphenproblem schnell lösen. Da Graphen-Experten glauben, dass das Graphenproblem inhärent langsam ist, muss das Regelproblem auch langsam sein.
Das „Orthogonale Vektoren"-Problem: Für Regeln mit noch mehr Variablen bewiesen sie, dass die benötigte Zeit exponentiell mit der Anzahl der Variablen wächst. Es ist wie der Versuch, eine spezifische Kombination von Schlüsseln in einem Schloss zu finden; je mehr Schlüssel Sie haben, desto unmöglicher wird es, dies durch Brute-Force schnell zu erledigen.

Fazit: Wenn Ihre Regel zu komplex ist (zu viele „merke dir das"-Funktionen verwendet), können Sie keine schnelle Engine dafür bauen. Sie werden immer an eine Wand stoßen.

2. Die gute Nachricht: Eine „nahezu lineare" Lösung für einfache Fälle

Das Paper fand jedoch eine goldene Mitte. Sie konzentrierten sich auf einen spezifischen, häufigen Regeltyp:

Das „ABCBD"-Muster: „Finde ein Wort (A), dann ein Wort (B), dann ein Wort (C), dann exakt dasselbe Wort B erneut, dann ein Wort (D)."
- Beispiel aus der Praxis: „Finde einen Benutzernamen, dann ein Passwort, dann eine Nachricht, dann denselben Benutzernamen erneut, dann eine Signatur."

Die Autoren entdeckten, dass dies zwar tricky aussieht, aber sehr effizient gelöst werden kann.

Der alte Weg: Frühere Methoden waren wie das Prüfen jeder möglichen Kombination in einer Bibliothek, was $O(n^2)$ Zeit (quadratisch) benötigte. Wenn das Buch 1.000 Seiten hatte, dauerte es 1.000.000 Schritte.
Der neue Weg: Die Autoren bauten einen neuen Algorithmus, der ungefähr $O(n \log^2 n)$ $O (n lo g^{2} n)$ Zeit benötigt.
- Die Analogie: Stellen Sie sich vor, die Bibliothek ist mit einem magischen Indexsystem organisiert (unter Verwendung von Suffix-Bäumen und Faktorisierungs-Wäldern). Statt jede Seite zu lesen, kann der Beamte direkt zu den relevanten Abschnitten springen. Wenn das Buch 1.000 Seiten hat, benötigt die neue Methode ungefähr 10.000 Schritte (oder sogar weniger), was eine massive Verbesserung darstellt.

Wie der neue Algorithmus funktioniert (Die „Magischen Tricks")

Um diese Geschwindigkeit zu erreichen, verwendeten die Autoren mehrere clevere Techniken, die sie im Paper beschreiben:

Der Suffix-Baum (Die Karte): Sie bauten eine riesige Karte der Eingabezeichenkette. Diese Karte zeigt jedes mögliche Ende der Zeichenkette. Sie hilft dem Beamten, sofort zu sehen: „Ach, dieses Wort 'B' erscheint hier, und es erscheint auch dort."
Heavy-Light-Decomposition (Der Sortierhut): Sie teilten die Karte in „schwere" Pfade (sehr häufige Pfade) und „leichte" Pfade (seltene Pfade) auf. Sie leisten nur bei den seltenen Pfaden die schwere Arbeit, was Zeit spart.
Periodizität (Der Rhythmus): Sie stellten fest, dass wenn sich ein Wort wiederholt (wie „B...B"), die Zeichenkette oft einen Rhythmus oder ein Muster hat. Sie verwendeten Mathematik, um diese Muster vorherzusagen, anstatt jeden einzelnen Buchstaben zu prüfen.
Faktorisierungs-Wälder (Der Index): Dies ist eine Datenstruktur, die wie ein superschneller Index funktioniert und dem Beamten erlaubt, zu prüfen, ob ein Textabschnitt eine Regel erfüllt, in konstanter Zeit, egal wie lang der Text ist.

Zusammenfassung der Schlussfolgerung

Können wir alle ReDoS-Angriffe stoppen? Nein. Wenn eine Regel zu komplex ist (zu viele „merke dir das"-Variablen), ist mathematisch bewiesen, dass sie langsam ist.
Können wir die häufigsten komplexen Regeln beheben? Ja! Für den spezifischen Fall, bei dem eine Regel ein Wort merkt und es später einmal prüft (das „ABCBD"-Muster), schufen die Autoren eine neue Engine, die fast so schnell ist wie einfache Regeln.
Warum ist das wichtig? Es sagt Software-Ingenieuren: „Verwenden Sie nicht zu viele Backreferences, sonst werden Sie langsam. Aber wenn Sie sie auf diese spezifische, gängige Weise verwenden, können Sie jetzt unsere neue Methode nutzen, um Ihr System sicher und schnell zu halten."

Das Paper zieht im Wesentlichen eine Linie im Sand: Hier ist das Geschwindigkeitslimit unbrechbar, und hier haben wir einen Weg gefunden, schneller zu fahren.

Technische Zusammenfassung: Zur Komplexität des Matching-Problems regulärer Ausdrücke mit Rückverweisen

1. Problemdefinition und Motivation

Die Arbeit untersucht die feingranulare rechnerische Komplexität des Matching-Problems regulärer Ausdrücke mit Rückverweisen (REWB). Während klassische reguläre Ausdrücke (Regex) unter Verwendung von Thompsons Konstruktion in linearer Zeit relativ zur Länge des Eingabestings $|w|$ gematcht werden können, unterstützen praktische Engines Rückverweise (z. B. (E)x zum Erfassen eines Teilstrings und \x zum Wiederverwenden). Dieses Merkmal erweitert die Ausdruckskraft von Regex strikt (indem es die Erkennung nicht-regulärer Sprachen wie $\{ww \mid w \in \Sigma^*\}$ ermöglicht), führt jedoch zu erheblichen algorithmischen Risiken.

Die Motivation ergibt sich aus Regular Expression Denial of Service (ReDoS)-Angriffen, bei denen Gegner Eingaben so gestalten, dass sie das Worst-Case-Verhalten in Matching-Engines auslösen. Bemerkenswerte Vorfälle bei Stack Overflow (2016) und Cloudflare (2019) zeigten, dass selbst quadratisches Zeitverhalten ( $O(|w|^2)$ ) in auf Backtracking basierenden Engines katastrophale Dienstausfälle verursachen kann. Die Autoren stellen die fundamentale Frage: Ist es möglich, ReDoS-sichere Engines für REWB zu konstruieren, die in linearer oder nahezu linearer Zeit laufen?

Der Fokus der Arbeit liegt auf $r$ -use $k$ -REWBs, definiert als Ausdrücke mit $k$ verschiedenen Variablen, wobei die Gesamtzahl der Rückverweis-Ausführungen in jeder Berechnung durch $r$ beschränkt ist.

2. Methodik und technischer Ansatz

Die Arbeit verfolgt einen dualen Ansatz: die Etablierung bedingter unterer Schranken (Härte) und das Design effizienter Algorithmen für spezifische Unterklassen.

2.1 Härteergebnisse

Die Autoren stärken frühere Komplexitätsresultate, indem sie bekannte harte Probleme auf REWB-Matching reduzieren:

W[2]-Härte: Durch Reduktion des $k$ -Dominating-Set-Problems beweisen sie, dass REWB-Matching W[2]-hart ist, wenn es nach der Ausdrucksgröße $|E|$ parametrisiert wird. Dies stärkt das bekannte W[1]-Härteergebnis.
Bedingte untere Schranken (Dreieckserkennung): Unter Annahme der „No-Almost-Linear-Time-Hypothese" für die Dreieckserkennung zeigen sie, dass selbst das hochgradig eingeschränkte 2-use 2-REWB-Problem nicht in $O(|w|^{1+\delta})$ Zeit für jedes $\delta > 0$ gelöst werden kann.
Bedingte untere Schranken (k-OV): Unter der $k$ -Orthogonal-Vectors (k-OV)-Hypothese (schwächer als SETH) beweisen sie, dass $k$ -REWB-Matching nicht in $O(|w|^{2k-\epsilon})$ Zeit gelöst werden kann. Dies impliziert, dass für allgemeines $k$ eine nahezu lineare Zeit unwahrscheinlich ist.

2.2 Algorithmische Ergebnisse

Der primäre algorithmische Beitrag konzentriert sich auf 1-use REWBs (Ausdrücke mit einer Variable, die genau einmal referenziert wird).

Transformation in kanonische Form: Die Autoren beweisen, dass jeder 1-use REWB in eine kanonische Form transformiert werden kann, die eine Summe von Termen wie $A (B)_x C \backslash x D$ beinhaltet, wobei $A, B, C, D$ klassische Regex sind. Dies wird als ABCBD-Problem bezeichnet.
Zerlegungsstrategie: Das ABCBD-Problem wird in zwei Teilprobleme zerlegt:
1. XYYZ-Problem: Der Fall, in dem die beiden Vorkommen von $B$ benachbart sind ( $w = w_A w_B w_B w_D$ ). Dies wird unter Verwendung der maximalen lokalen Potenzenumeration nach Crochemore und Eigenschaften ultimativ periodischer Mengen, die aus Transformationsmonoiden abgeleitet werden, gelöst.
2. Verzweigtes ABCBD-Problem: Der Fall, in dem die beiden Vorkommen von $B$ durch ein nicht-leeres $C$ getrennt sind und die Zeichen, die unmittelbar auf die beiden $B$ -Vorkommen folgen, unterschiedlich sind.
Suffix-Baum und Heavy-Light-Zerlegung: Für den verzweigten Fall nutzt der Algorithmus den Suffix-Baum des Eingabestings $w$ . Er verwendet eine Heavy-Light-Zerlegung, um den Suchraum zu partitionieren.
Datenstrukturen:
- Faktorisierungswälder: Werden verwendet, um Regex-Mitgliedschaft in Teilstrings nach linearer Vorverarbeitung in konstanter Zeit zu bewerten.
- Transformationsmonoid: Werden genutzt, um den Zustand der Regex $A, B, C, D$ effizient zu verfolgen.
- Benutzerdefinierte Enumeratoren: Die Autoren entwerfen spezialisierte Datenstrukturen (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) zur Handhabung der Transitionsenumeration. Diese Strukturen verwenden lazy Updates und Disjoint-Set-Union (DSU)-Strategien, um Einschränkungen zu verwalten, die von der Länge des Teilstrings $w_B$ abhängen.

3. Schlüsselergebnisse

Härte

Satz 3: REWB-Matching ist W[2]-hart, parametrisiert nach der Ausdrucksgröße.
Satz 4: Unter der Dreieckserkennungs-Hypothese erfordert 2-use 2-REWB-Matching superlineare Zeit (speziell nicht $O(|w|^{1+\delta})$ ).
Satz 5: Unter der $k$ -OV-Hypothese erfordert $k$ -REWB-Matching $\Omega(|w|^{2k-\epsilon})$ Zeit.

Algorithmen

Satz 7 (Hauptergebnis): Das ABCBD-Problem erlaubt einen $O(|w| \log^2 |w|)$ -Zeit-Algorithmus. Die versteckte Konstante hängt exponentiell von den Größen der Regex $A, B, C, D$ ab ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Satz 8: Folglich erlaubt das 1-use REWB-Matching-Problem einen $O(|w| \log^2 |w|)$ -Zeit-Algorithmus.
Satz 9: Das XY $\alpha$ Z-Problem (Verallgemeinerung von XYYZ auf $\alpha$ Wiederholungen) erlaubt einen $O(|w| \log |w|)$ -Zeit-Algorithmus.

Diese Ergebnisse stellen eine signifikante Verbesserung gegenüber dem bisher besten bekannten $O(|w|^2)$ -Algorithmus für das ABCBD-Problem von Nogami und Terauchi (MFCS 2025) dar.

4. Bedeutung und Behauptungen

Die Arbeit behauptet, ein fundamentales Verständnis der Komplexitätslandschaft für REWB-Matching zu liefern:

ReDoS-Sicherheit: Sie etabliert, dass zwar allgemeines REWB-Matching für nahezu lineare Zeit wahrscheinlich unlösbar ist, eine praktisch relevante Unterklasse (1-use REWB) jedoch in nahezu linearer Zeit gematcht werden kann. Dies legt nahe, dass Engines, die 1-use-Rückverweise unterstützen, theoretisch ReDoS-sicher gemacht werden könnten.
Feingranulare Komplexität: Die Arbeit grenzt die Grenze zwischen lösbaren und unlösbaren Fällen ab. Sie zeigt, dass die Erhöhung der Anzahl der Rückverweisverwendungen von 1 auf 2 (selbst bei nur 2 Variablen) das Problem wahrscheinlich aus dem Bereich der nahezu linearen Zeit herausdrückt.
Algorithmische Innovation: Die Arbeit stellt einen komplexen, aber höchst nicht-trivialen algorithmischen Rahmen vor, der Suffix-Bäume, Faktorisierungswälder und Transformationsmonoid kombiniert, um ein Problem zu lösen, von dem zuvor angenommen wurde, dass es quadratische Zeit erfordert.

Die Autoren stellen explizit fest, dass ihr Algorithmus uniform ist, was bedeutet, dass er den Ausdruck und den Eingabestring zusammen verarbeitet, ohne nicht-uniforme Ratschläge zu benötigen, die vom festen Ausdruck abhängen. Sie räumen ein, dass die exponentielle Abhängigkeit von der Ausdrucksgröße $|E|$ eine Einschränkung für sehr große Ausdrücke bleibt, und lassen die Frage offen, ob ein wahrer linearer Zeitalgorithmus ( $O(|w|)$ ) existiert oder ob die logarithmischen Faktoren entfernt werden können.

5. Einschränkungen und offene Probleme

Die Arbeit identifiziert mehrere offene Richtungen:

Komplexität von $r$ -use 1-REWB: Die Komplexität für $r$ -use 1-REWBs, wobei $r \ge 2$ , bleibt offen.
Lineare Zeit: Ob die $O(|w| \log^2 |w|)$ -Schranke auf $O(|w|)$ verbessert werden kann.
Ausdruckabhängigkeit: Die Reduzierung der exponentiellen Abhängigkeit von $|E|$ auf polynomiell bei gleichzeitiger Beibehaltung einer nahezu linearen Abhängigkeit von $|w|$ .
Breitere Merkmale: Die Erweiterung dieser Ergebnisse auf andere praktische Regex-Merkmale wie Lookarounds, atomare Gruppierung und greedy/lazy-Sterne.