💬 NLP

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

Dit artikel vestigt de fijnkorrelige computationele complexiteit van het matchen van reguliere expressies met terugverwijzingen door conditionele ondergrenzen te bewijzen onder de aannames van SETH en driehoekdetectie, terwijl tegelijkertijd een verbeterd $O(n \log^2 n)$ -algoritme voor terugverwijzingen met één gebruik wordt gepresenteerd.

Oorspronkelijke auteurs: Soh Kumabe, Yuya Uezato

Gepubliceerd 2026-05-11

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Soh Kumabe, Yuya Uezato

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De "Regex" Verkeersopstopping

Stel je voor dat je een beveiligingsagent bent bij een club (het computersysteem). Je hebt een lijst met regels (een Regular Expression) voor wie er binnen mag.

Eenvoudige Regels: "Alleen mensen met een rood shirt." Dit is makkelijk te controleren. Je kijkt naar een shirt, zegt "Rood? Ja, kom binnen." Het kost evenveel tijd of de rij nu uit 10 mensen bestaat of uit 10.000.
Het Probleem (ReDoS): Soms maken hackers een specifieke rij mensen die de agent ertoe brengt een enorme hoeveelheid onnodig werk te doen. In plaats van één persoon te controleren en door te gaan, begint de agent met het controleren van Persoon A, dan Persoon B, dan weer Persoon A, dan Persoon C, dan weer Persoon A... totdat de agent van uitputting instort. Dit heet een Denial of Service (ReDoS) aanval.

In de echte wereld heeft dit ervoor gezorgd dat enorme websites zoals Stack Overflow en Cloudflare zijn gecrasht. Het paper merkt op dat zelfs "kwadratische" vertraging (waarbij het controleren van 100 mensen 10.000 stappen kost) genoeg is om een systeem te laten crashen.

De Schurk: "Backreferences"

Standaardregels zijn simpel. Maar moderne "Regex"-engines hebben een superkrachtige functie genaamd Backreferences.

De Analogie:
Stel je een regel voor die zegt: "Vind een woord, onthoud het, en zorg er vervolgens voor dat precies hetzelfde woord later weer voorkomt."

Voorbeeld: "Vind een woord, noem het 'X'. Vind vervolgens 'X' opnieuw."
Als de invoer appel ... appel is, werkt het.
Als de invoer appel ... banaan is, faalt het.

Deze functie is ongelooflijk nuttig voor programmeurs, maar het maakt de taak van de "agent" veel moeilijker. De agent moet onthouden wat hij eerder zag en dit voortdurend vergelijken met wat hij nu ziet. Het paper vraagt zich af: Kunnen we een agent bouwen die snel genoeg is om deze complexe regels te hanteren zonder uitgeput te raken?

De Bevindingen van het Paper: Het Goede, Het Slechte en Het Lelijke

De auteurs onderzochten precies hoe moeilijk het is om deze matchingsproblemen op te lossen. Ze splitsten het op in twee kanten: Moeilijkheid (Waarom het moeilijk is) en Algoritmen (Hoe het op te lossen).

1. Het Slechte Nieuws: Sommige Regels zijn Onmogelijk om te Versnellen

Het paper bewijst dat voor bepaalde soorten complexe regels er geen "wondermiddel" bestaat om ze snel te maken.

Het "Driehoek"-Probleem: Ze toonden aan dat als je een regel hebt die twee variabelen gebruikt (zoals het onthouden van twee verschillende woorden en het controleren ervan later), het oplossen ervan net zo moeilijk is als het vinden van een driehoek in een gigantisch sociaal netwerk-grafiek. Als je de regel snel kon oplossen, kon je het grafiekprobleem ook snel oplossen. Omdat grafiek-experts geloven dat het grafiekprobleem inherent traag is, moet het regelprobleem ook traag zijn.
Het "Orthogonale Vectoren"-Probleem: Voor regels met nog meer variabelen bewezen ze dat de benodigde tijd exponentieel groeit met het aantal variabelen. Het is alsof je probeert een specifieke combinatie van sleutels in een slot te vinden; hoe meer sleutels je hebt, hoe onmogelijker het wordt om dit snel via brute force op te lossen.

Conclusie: Als je regel te complex is (met veel "onthoud dit"-functies), kun je geen snelle engine voor bouwen. Je zult altijd tegen een muur aanlopen.

2. Het Goede Nieuws: Een "Bijna-Lineaire" Oplossing voor Eenvoudige Gevallen

Het paper vond echter een sweet spot. Ze richtten zich op een specifiek, veelvoorkomend type regel:

Het "ABCBD"-Patroon: "Vind een woord (A), dan een woord (B), dan een woord (C), dan precies hetzelfde woord B opnieuw, dan een woord (D)."
- Voorbeeld uit de echte wereld: "Vind een gebruikersnaam, dan een wachtwoord, dan een bericht, dan dezelfde gebruikersnaam opnieuw, dan een handtekening."

De auteurs ontdekten dat hoewel dit er lastig uitziet, het zeer efficiënt opgelost kan worden.

De Oude Manier: Vorige methoden waren als het controleren van elke mogelijke combinatie in een bibliotheek, wat $O(n^2)$ tijd kostte (kwadratisch). Als het boek 1.000 pagina's had, kostte het 1.000.000 stappen.
De Nieuwe Manier: De auteurs bouwden een nieuw algoritme dat ongeveer $O(n \log^2 n)$ $O (n lo g^{2} n)$ tijd kost.
- De Analogie: Stel je voor dat de bibliotheek is georganiseerd met een magisch indexsysteem (met behulp van Suffix Trees en Factorization Forests). In plaats van elke pagina te lezen, kan de agent direct naar de relevante secties springen. Als het boek 1.000 pagina's heeft, kost de nieuwe methode ongeveer 10.000 stappen (of zelfs minder), wat een enorme verbetering is.

Hoe het Nieuwe Algoritme Werkt (De "Magische Trucs")

Om deze snelheid te bereiken, gebruikten de auteurs verschillende slimme technieken, die ze in het paper beschrijven:

De Suffix Tree (De Kaart): Ze bouwden een gigantische kaart van de invoerstring. Deze kaart toont elke mogelijke eindiging van de string. Het helpt de agent om direct te zien: "Oh, dit woord 'B' komt hier voor, en het komt daar ook voor."
Heavy-Light Decomposition (De Sorteerhoed): Ze splitsten de kaart op in "zware" paden (zeer veelvoorkomende paden) en "lichte" paden (zeldzame paden). Ze doen alleen het zware werk op de zeldzame paden, waardoor tijd wordt bespaard.
Periodiciteit (Het Ritme): Ze merkten op dat wanneer een woord zich herhaalt (zoals "B...B"), de string vaak een ritme of patroon heeft. Ze gebruikten wiskunde om deze patronen te voorspellen in plaats van elke enkele letter te controleren.
Factorization Forests (De Index): Dit is een datastructuur die fungeert als een supersnelle index, waardoor de agent kan controleren of een stuk tekst overeenkomt met een regel in constante tijd, ongeacht hoe lang de tekst is.

Samenvatting van de Conclusie

Kunnen we alle ReDoS-aanvallen stoppen? Nee. Als een regel te complex is (te veel "onthoud dit"-variabelen), is het wiskundig bewezen dat het traag is.
Kunnen we de meest voorkomende complexe regels oplossen? Ja! Voor het specifieke geval waarin een regel één woord onthoudt en het later één keer controleert (het "ABCBD"-patroon), hebben de auteurs een nieuwe engine gemaakt die bijna net zo snel is als de eenvoudige regels.
Waarom is dit belangrijk? Het vertelt software-engineers: "Gebruik niet te veel backreferences, anders word je traag. Maar als je ze op deze specifieke, veelvoorkomende manier gebruikt, kun je nu onze nieuwe methode gebruiken om je systeem veilig en snel te houden."

Het paper trekt in feite een lijn in het zand: Hier is waar het snelheidslimiet onbreekbaar is, en hier hebben we een manier gevonden om sneller te rijden.

Technische Samenvatting: Over de Complexiteit van het Matching-probleem van Reguliere Expressies met Achterwaartse Referenties

1. Probleemdefinitie en Motivatie

Het artikel onderzoekt de fijnkorrelige computationele complexiteit van het Matching-probleem voor Reguliere Expressies met Achterwaartse Referenties (REWB). Hoewel klassieke reguliere expressies (Regex) in lineaire tijd ten opzichte van de lengte van de invoerstring $|w|$ kunnen worden gematcht met behulp van de constructie van Thompson, ondersteunen praktische engines achterwaartse referenties (bijvoorbeeld (E)x om een substring vast te leggen en \x om deze opnieuw te gebruiken). Deze functie breidt de expressieve kracht van Regex strikt uit (waardoor het herkennen van niet-reguliere talen mogelijk wordt, zoals $\{ww \mid w \in \Sigma^*\}$ ), maar introduceert aanzienlijke algoritmische risico's.

De motivatie vloeit voort uit Regular Expression Denial of Service (ReDoS)-aanvallen, waarbij tegenstanders invoer construeren om het worst-case-gedrag in matching-engines te activeren. Opmerkelijke incidenten bij Stack Overflow (2016) en Cloudflare (2019) hebben aangetoond dat zelfs kwadratisch-tijdsgedrag ( $O(|w|^2)$ ) in op backtracking gebaseerde engines tot catastrofale serviceonderbrekingen kan leiden. De auteurs stellen de fundamentele vraag: Is het mogelijk om ReDoS-veilige engines voor REWB te construeren die in lineaire of bijna-lineaire tijd draaien?

Het artikel richt zich op $r$ -gebruik $k$ -REWB's, gedefinieerd als expressies met $k$ verschillende variabelen waarbij het totale aantal uitvoeringen van achterwaartse referenties in elke berekening begrensd is door $r$ .

2. Methodologie en Technische Aanpak

Het artikel hanteert een tweeledige aanpak: het vaststellen van conditionele ondergrenzen (hardheid) en het ontwerpen van efficiënte algoritmen voor specifieke subklassen.

2.1 Hardheidsresultaten

De auteurs versterken eerdere complexiteitsresultaten door bekende moeilijke problemen te reduceren tot REWB-matching:

W[2]-hardheid: Door de $k$ -Dominating Set-probleem te reduceren, bewijzen ze dat REWB-matching W[2]-hard is wanneer geparametriseerd door de grootte van de expressie $|E|$ . Dit versterkt het bekende W[1]-hardheidsresultaat.
Conditionele Ondergrenzen (Driehoekdetectie): Aannemende de "No-Almost-Linear-Time Hypothesis" voor Driehoekdetectie, tonen ze aan dat zelfs het sterk beperkte 2-gebruik 2-REWB-probleem niet in $O(|w|^{1+\delta})$ tijd kan worden opgelost voor elke $\delta > 0$ .
Conditionele Ondergrenzen (k-OV): Onder de $k$ -Orthogonale Vectors (k-OV)-hypothese (zwakker dan SETH) bewijzen ze dat $k$ -REWB-matching niet in $O(|w|^{2k-\epsilon})$ tijd kan worden opgelost. Dit impliceert dat voor algemene $k$ bijna-lineaire tijd onwaarschijnlijk is.

2.2 Algoritmische Resultaten

De primaire algoritmische bijdrage richt zich op 1-gebruik REWB's (expressies met één variabele die precies één keer wordt gerefereerd).

Transformatie naar Canonieke Vorm: De auteurs bewijzen dat elke 1-gebruik REWB kan worden getransformeerd naar een canonieke vorm die een som van termen bevat zoals $A (B)_x C \backslash x D$ , waarbij $A, B, C, D$ klassieke Regexen zijn. Dit wordt het ABCBD-probleem genoemd.
Decompositiestrategie: Het ABCBD-probleem wordt opgesplitst in twee subproblemen:
1. XYYZ-probleem: Het geval waarin de twee voorkomens van $B$ naast elkaar staan ( $w = w_A w_B w_B w_D$ ). Dit wordt opgelost met behulp van Crochemore's enumeratie van maximale lokale machten en eigenschappen van uiteindelijk periodieke verzamelingen afgeleid van transitie-monoiden.
2. Branching ABCBD-probleem: Het geval waarin de twee voorkomens van $B$ gescheiden zijn door een niet-lege $C$ , en de karakters die direct na de twee $B$ -voorkomens volgen, verschillen.
Suffixboom en Heavy-Light Decompositie: Voor het Branching-geval maakt het algoritme gebruik van de suffixboom van de invoerstring $w$ . Het hanteert heavy-light decomposition om de zoekruimte te partitioneren.
Datastructuren:
- Factorisatiebossen: Gebruikt om Regex-lidmaatschap op substrings in constante tijd te evalueren na lineaire preprocessing.
- Transitie-monoiden: Ingezet om de staat van Regexen $A, B, C, D$ efficiënt bij te houden.
- Aangepaste Enumerators: De auteurs ontwerpen gespecialiseerde datastructuren (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) om transitieenumeratie te verwerken. Deze structuren maken gebruik van lazy updates en strategieën voor disjoint-set union (DSU) om beperkingen te beheren die variëren met de lengte van de substring $w_B$ .

3. Belangrijkste Resultaten

Hardheid

Stelling 3: REWB-matching is W[2]-hard geparametriseerd door de grootte van de expressie.
Stelling 4: Aannemende de Driehoekdetectie-hypothese, vereist 2-gebruik 2-REWB-matching super-lineaire tijd (specifiek, niet $O(|w|^{1+\delta})$ ).
Stelling 5: Onder de $k$ -OV-hypothese vereist $k$ -REWB-matching $\Omega(|w|^{2k-\epsilon})$ tijd.

Algoritmen

Stelling 7 (Hoofdresultaat): Het ABCBD-probleem staat een $O(|w| \log^2 |w|)$ tijd-algoritme toe. De verborgen constante hangt exponentieel af van de grootte van de Regexen $A, B, C, D$ ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Stelling 8: Bijgevolg staat het 1-gebruik REWB-matching-probleem een $O(|w| \log^2 |w|)$ tijd-algoritme toe.
Stelling 9: Het XY $\alpha$ Z-probleem (dat XYYZ generaliseert naar $\alpha$ herhalingen) staat een $O(|w| \log |w|)$ tijd-algoritme toe.

Deze resultaten vormen een aanzienlijke verbetering ten opzichte van het vorige beste bekende $O(|w|^2)$ algoritme voor het ABCBD-probleem van Nogami en Terauchi (MFCS 2025).

4. Betekenis en Claims

Het artikel claimt een fundamenteel inzicht te bieden in het complexiteitslandschap voor REWB-matching:

ReDoS-veiligheid: Het stelt vast dat hoewel algemene REWB-matching waarschijnlijk onhandelbaar is voor bijna-lineaire tijd, een praktisch relevante subklasse (1-gebruik REWB) wel in bijna-lineaire tijd kan worden gematcht. Dit suggereert dat engines die 1-gebruik achterwaartse referenties ondersteunen, theoretisch ReDoS-veilig kunnen worden gemaakt.
Fijnkorrelige Complexiteit: Het werk schetst de grens tussen hanteerbare en onhanteerbare gevallen. Het toont aan dat het verhogen van het aantal gebruik van achterwaartse referenties van 1 naar 2 (zelfs met slechts 2 variabelen) het probleem waarschijnlijk uit het bijna-lineaire regime duwt.
Algoritmische Innovatie: Het artikel introduceert een complex maar uiterst niet-triviaal algoritmisch raamwerk dat suffixbomen, factorisatiebossen en transitie-monoiden combineert om een probleem op te lossen waarvan eerder werd gedacht dat het kwadratische tijd vereiste.

De auteurs stellen expliciet dat hun algoritme uniform is, wat betekent dat het de expressie en invoerstring samen verwerkt zonder niet-uniform advies dat afhankelijk is van de vaste expressie. Zij erkennen dat de exponentiële afhankelijkheid van de grootte van de expressie $|E|$ een beperking blijft voor zeer grote expressies, en zij laten de vraag open of er een echt lineair-tijd-algoritme ( $O(|w|)$ ) bestaat of dat de logaritmische factoren kunnen worden verwijderd.

5. Beperkingen en Open Problemen

Het artikel identificeert verschillende open richtingen:

Complexiteit van $r$ -gebruik 1-REWB: De complexiteit voor $r$ -gebruik 1-REWB's waarbij $r \ge 2$ blijft open.
Lineaire Tijd: Of de $O(|w| \log^2 |w|)$ -grens kan worden verbeterd tot $O(|w|)$ .
Afhankelijkheid van Expressie: Het verminderen van de exponentiële afhankelijkheid van $|E|$ tot polynoom, terwijl de bijna-lineaire afhankelijkheid van $|w|$ behouden blijft.
Breder Functioneel: Het uitbreiden van deze resultaten naar andere praktische regex-functies zoals lookarounds, atomaire groepering en greedy/lazy sterren.