Backtracking in reguliere expressies

Backtracking treedt op wanneer een normaal expressiepatroon optionele kwantificatoren of alternation-constructies bevat en de engine voor reguliere expressies terugkeert naar een eerdere opgeslagen status om door te gaan met het zoeken naar een overeenkomst. Backtracking ligt aan de basis van de kracht van reguliere expressies; het maakt het mogelijk dat expressies krachtig en flexibel zijn en met zeer complexe patronen overeenkomen. Tegelijkertijd kost dit vermogen een prijs. Backtracking is vaak de belangrijkste factor die van invloed is op de prestaties van de engine voor reguliere expressies. Gelukkig heeft de ontwikkelaar controle over het gedrag van de reguliere expressie-engine en hoe backtracking wordt gebruikt. In dit artikel wordt uitgelegd hoe backtracking werkt en hoe u deze kunt beheren.

Lineair vergelijken zonder backtracking

Als een patroon voor reguliere expressies geen optionele kwantificatoren of alternatieconstructies heeft, wordt de engine voor reguliere expressies in lineaire tijd uitgevoerd. Dat wil zeggen, nadat de reguliere-expressie-engine het eerste taalelement in het patroon heeft gekoppeld aan tekst in de invoertekenreeks, probeert deze het volgende taalelement in het patroon te koppelen aan het volgende teken of de volgende groep tekens in de invoertekenreeks. Dit gaat door totdat de match slaagt of mislukt. In beide gevallen gaat de engine voor de reguliere expressie met één teken tegelijk in de invoertekenreeks verder.

In het volgende voorbeeld ziet u een afbeelding. De reguliere expressie e{2}\w\b zoekt naar twee voorkomens van de letter "e", gevolgd door een willekeurig woordteken en vervolgens door een woordgrens.

using System;
using System.Text.RegularExpressions;

public class Example1
{
    public static void Run()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        foreach (Match match in Regex.Matches(input, pattern))
            Console.WriteLine($"{match.Value} found at position {match.Index}");
    }
}
// The example displays the following output:
//       eed found at position 11

Imports System.Text.RegularExpressions

Module Example1
    Public Sub Run()
        Dim input As String = "needing a reed"
        Dim pattern As String = "e{2}\w\b"
        For Each match As Match In Regex.Matches(input, pattern)
            Console.WriteLine("{0} found at position {1}",
                              match.Value, match.Index)
        Next
    End Sub
End Module
' The example displays the following output:
'       eed found at position 11

Hoewel deze reguliere expressie de kwantificeerder {2}bevat, wordt deze op een lineaire manier geëvalueerd. De engine voor reguliere expressies voert geen backtracking uit, omdat {2} geen optionele kwantificator is; deze specificeert een exact aantal en geen variabel aantal keren dat de vorige subexpressie moet overeenkomen. Als gevolg hiervan probeert de reguliere-expressie-engine het patroon van de reguliere expressie te vergelijken met de invoertekenreeks, zoals in de volgende tabel wordt weergegeven.

Als een patroon voor reguliere expressies geen optionele kwantificatoren of alternatieconstructies bevat, is het maximum aantal vergelijkingen dat nodig is om het reguliere expressiepatroon te vergelijken met de invoertekenreeks ongeveer gelijk aan het aantal tekens in de invoertekenreeks. In dit geval gebruikt de engine voor reguliere expressies 19 vergelijkingen om mogelijke overeenkomsten in deze tekenreeks van 13 tekens te identificeren. Met andere woorden, de engine voor reguliere expressies werkt in bijna lineaire tijd als die geen optionele kwantificaties of alternatieconstructies bevat.

Backtracking met optionele kwantificatoren of alternatieven

Wanneer een reguliere expressie optionele kwantificatoren of alternation-constructies bevat, is de evaluatie van de invoertekenreeks niet langer lineair. Het patroon dat overeenkomt met een NFA-engine (Nondeterministic Finite Automaton) wordt aangestuurd door de taalelementen in de reguliere expressie en niet door de tekens die moeten worden vergeleken in de invoertekenreeks. Daarom probeert de engine voor reguliere expressies volledig overeen te komen met optionele of alternatieve subexpressies. Wanneer het naar het volgende taalelement in de subexpressie gaat en de overeenkomst mislukt, kan de engine voor reguliere expressies een deel van de geslaagde overeenkomst afbreken en terugkeren naar een eerder opgeslagen status om de reguliere expressie als geheel te vergelijken met de invoertekenreeks. Dit proces om terug te keren naar een eerdere opgeslagen status om een overeenkomst te vinden, wordt backtracking genoemd.

Denk bijvoorbeeld aan het reguliere expressiepatroon .*(es), dat overeenkomt met de tekens 'es' en alle tekens die eraan voorafgaan. Zoals in het volgende voorbeeld wordt getoond, komt het patroon overeen met de hele tekenreeks tot en met de 'es' in 'expressies' als de invoertekenreeks 'Essentiële services worden geleverd door reguliere expressies.' is.

using System;
using System.Text.RegularExpressions;

public class Example2
{
    public static void Run()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
        if (m.Success)
        {
            Console.WriteLine($"'{m.Value}' found at position {m.Index}");
            Console.WriteLine($"'es' found at position {m.Groups[1].Index}");
        }
    }
}
//    'Essential services are provided by regular expres' found at position 0
//    'es' found at position 47

Imports System.Text.RegularExpressions

Module Example2
    Public Sub Run()
        Dim input As String = "Essential services are provided by regular expressions."
        Dim pattern As String = ".*(es)"
        Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
        If m.Success Then
            Console.WriteLine("'{0}' found at position {1}",
                              m.Value, m.Index)
            Console.WriteLine("'es' found at position {0}",
                              m.Groups(1).Index)
        End If
    End Sub
End Module
'    'Essential services are provided by regular expres' found at position 0
'    'es' found at position 47

Hiervoor gebruikt de engine voor reguliere expressies backtracking als volgt:

• Deze komt overeen met de .* (die overeenkomt met nul, één of meer voorkomens van een willekeurig teken) en de volledige invoertekenreeks.

• Er wordt geprobeerd om 'e' overeen te laten komen met het patroon van de reguliere expressie. De invoertekenreeks bevat echter geen resterende tekens die overeenkomen.

• Het gaat terug naar de laatste succesvolle overeenkomst, "Essentiële diensten worden geleverd door reguliere expressies", en probeert de 'e' te laten overeenkomen met de punt aan het einde van de zin. De overeenkomst mislukt.

• Het blijft telkens één teken teruggaan naar een eerdere succesvolle overeenkomst totdat de voorlopig gematchte subtekenreeks "Essential services are provided by regular expr" is. Vervolgens wordt de 'e' in het patroon vergeleken met de tweede 'e' in 'expressies' en wordt een overeenkomst gevonden.

• Het vergelijkt 's' in het patroon met de 's' die het overeenkomende 'e'-teken volgt (de eerste 's' in 'expressies'). De match is gelukt.

Wanneer u backtracking gebruikt, moet u 67 vergelijkingsbewerkingen uitvoeren om het reguliere expressiepatroon te vergelijken met de invoertekenreeks, die 55 tekens lang is. Over het algemeen geldt dat als een patroon voor een reguliere expressie één alternationconstructie of één optionele kwantificator heeft, het aantal vergelijkingsbewerkingen dat nodig is om aan het patroon te voldoen, meer dan twee keer het aantal tekens in de invoertekenreeks is.

Backtracking met geneste optionele kwantificatoren

Het aantal vergelijkingsbewerkingen dat nodig is om overeen te komen met een normaal expressiepatroon kan exponentieel toenemen als het patroon een groot aantal alternatieconstructies bevat, als het geneste alternatieconstructies bevat, of, meestal, als het geneste optionele kwantificatoren bevat. Het reguliere expressiepatroon ^(a+)+$ is bijvoorbeeld ontworpen om overeen te komen met een volledige tekenreeks die een of meer a-tekens bevat. Het voorbeeld bevat twee invoertekenreeksen met een identieke lengte, maar alleen de eerste tekenreeks komt overeen met het patroon. De System.Diagnostics.Stopwatch klasse wordt gebruikt om te bepalen hoe lang de zoekbewerking duurt.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example3
{
    public static void Run()
    {
        string pattern = "^(a+)+$";
        string[] inputs = { "aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!" };
        Regex rgx = new Regex(pattern);
        Stopwatch sw;

        foreach (string input in inputs)
        {
            sw = Stopwatch.StartNew();
            Match match = rgx.Match(input);
            sw.Stop();
            if (match.Success)
                Console.WriteLine($"Matched {match.Value} in {sw.Elapsed}");
            else
                Console.WriteLine($"No match found in {sw.Elapsed}");
        }
    }
}
//    Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
//    No match found in 00:00:05.1882144

Imports System.Text.RegularExpressions

Module Example3
    Public Sub Run()
        Dim pattern As String = "^(a+)+$"
        Dim inputs() As String = {"aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!"}
        Dim rgx As New Regex(pattern)
        Dim sw As Stopwatch

        For Each input As String In inputs
            sw = Stopwatch.StartNew()
            Dim match As Match = rgx.Match(input)
            sw.Stop()
            If match.Success Then
                Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
            Else
                Console.WriteLine("No match found in {0}", sw.Elapsed)
            End If
        Next
    End Sub
End Module
'    Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
'    No match found in 00:00:05.1882144

Zoals de uitvoer uit het voorbeeld laat zien, duurde het aanzienlijk langer om te ontdekken dat een invoertekenreeks niet overeenkomt met het patroon, net als bij het identificeren van een overeenkomende tekenreeks. Dit komt doordat een mislukte match altijd een worstcasescenario is. De engine voor reguliere expressies moet de reguliere expressie gebruiken om alle mogelijke paden door de gegevens te volgen voordat deze kan concluderen dat er geen overeenkomst is, en de geneste haakjes creëren veel extra paden door de gegevens. De engine voor reguliere expressies concludeert dat de tweede tekenreeks niet overeenkomt met het patroon door het volgende te doen:

• Er wordt gecontroleerd of deze zich aan het begin van de tekenreeks bevond en vervolgens overeenkomt met de eerste vijf tekens in de tekenreeks met het patroon a+. Vervolgens wordt vastgesteld dat er geen verdere groepen van 'a'-tekens in de tekenreeks voorkomen. Ten slotte wordt gecontroleerd of het einde van de tekenreeks is bereikt. Omdat er nog één extra teken in de tekenreeks blijft, mislukt de overeenkomst. Deze niet-geslaagde match vereist 9 vergelijkingen. De engine voor reguliere expressies slaat ook statusgegevens op uit de overeenkomsten van 'a' (die we match 1 noemen), 'aa' (overeenkomst 2), 'aaa' (overeenkomst 3) en 'aaaa' (overeenkomst 4).

• Het gaat terug naar de eerder opgeslagen match 4. Het bepaalt dat er één extra "a"-teken is om toe te wijzen aan een extra vastgelegde groep. Tot slot controleert het of het einde van de tekenreeks is bereikt. Omdat er nog één extra teken in de tekenreeks staat, mislukt de overeenstemming. Voor deze mislukte match zijn vier vergelijkingen nodig. Tot nu toe zijn er in totaal 13 vergelijkingen uitgevoerd.

• Keert terug naar de eerder opgeslagen match 3. Er wordt bepaald dat er twee extra 'a'-tekens zijn die moeten worden toegewezen aan een extra vastgelegde groep. De end-of-string-test mislukt echter. Vervolgens keert het terug naar match 3 en probeert het de twee extra 'a'-tekens te matchen in twee extra vastgelegde groepen. De end-of-string-test mislukt nog steeds. Voor deze mislukte overeenkomsten zijn 12 vergelijkingen vereist. Tot nu toe zijn er in totaal 25 vergelijkingen uitgevoerd.

De vergelijking van de invoertekenreeks met de reguliere expressie wordt op deze manier voortgezet totdat de engine voor reguliere expressies alle mogelijke combinaties van overeenkomsten heeft geprobeerd en vervolgens besluit dat er geen overeenkomst is. Vanwege de geneste kwantificatoren is deze vergelijking een O(2ⁿ) of een exponentiële bewerking, waarbij n het aantal tekens in de invoertekenreeks is. Dit betekent dat in het ergste geval een invoertekenreeks van 30 tekens ongeveer 1.073.741.824 vergelijkingen vereist en een invoertekenreeks van 40 tekens ongeveer 1.099.511.627.776 vergelijkingen vereist. Als u tekenreeksen van deze of nog grotere lengten gebruikt, kan het zeer lang duren voordat reguliere expressiemethoden zijn voltooid wanneer ze invoer verwerken die niet overeenkomt met het reguliere expressiepatroon.

Backtracking beheren

Met Backtracking kunt u krachtige, flexibele reguliere expressies maken. Zoals in de vorige sectie is gebleken, kunnen deze voordelen echter worden gekoppeld aan onaanvaardbaar slechte prestaties. Als u overmatige backtracking wilt voorkomen, moet u een time-outinterval definiëren wanneer u een Regex object instantiëren of een statische reguliere expressiekoppelingsmethode aanroept. Dit wordt besproken in de volgende sectie. Daarnaast ondersteunt .NET drie reguliere expressietaalelementen die backtracking beperken of onderdrukken en die complexe reguliere expressies ondersteunen met weinig of geen prestatiestraf: atomische groepen, lookbehind-asserties en lookahead-asserties. Zie Groeperingsconstructies voor meer informatie over elk taalelement.

Engine voor niet-backtracking van reguliere expressies

Als u geen constructies hoeft te gebruiken waarvoor backtracking is vereist (bijvoorbeeld lookarounds, backreferences of atomische groepen), kunt u overwegen de RegexOptions.NonBacktracking modus te gebruiken. Deze modus is ontworpen om in de tijd evenredig te worden uitgevoerd met de lengte van de invoer. Zie de modus NonBacktracking voor meer informatie. U kunt ook een time-outwaarde instellen.

De grootte van invoer beperken

Sommige reguliere expressies hebben acceptabele prestaties, tenzij de invoer uitzonderlijk groot is. Als alle redelijke tekstinvoer in uw scenario onder een bepaalde lengte staat, kunt u overwegen langere invoer te weigeren voordat u de reguliere expressie erop toepast.

Een time-outinterval opgeven

U kunt een time-outwaarde instellen die de maximale tijdsduur aangeeft dat de engine voor reguliere expressies naar één overeenkomst zoekt voordat de poging wordt afgebroken en er een RegexMatchTimeoutException-uitzondering wordt gegenereerd. U geeft het time-outinterval op door een TimeSpan waarde op te geven aan de Regex(String, RegexOptions, TimeSpan) constructor voor bijvoorbeeld reguliere expressies. Bovendien heeft elke methode voor het vergelijken van statische patronen een overbelasting met een TimeSpan parameter waarmee u een time-outwaarde kunt opgeven.

Als u geen time-outwaarde expliciet instelt, wordt de standaardtime-outwaarde als volgt bepaald:

• Als deze bestaat, gebruikt u de time-outwaarde voor de hele toepassing. Dit kan elke time-outwaarde zijn die van toepassing is op het toepassingsdomein waarin het Regex object wordt geïnstantieerd of de aanroep van de statische methode wordt uitgevoerd. U kunt de time-outwaarde voor de hele toepassing instellen door de AppDomain.SetData methode aan te roepen om de tekenreeksweergave van een TimeSpan waarde toe te wijzen aan de REGEX_DEFAULT_MATCH_TIMEOUT eigenschap.
• Door de waarde InfiniteMatchTimeout te gebruiken als er geen toepassingsbrede time-outwaarde is ingesteld.

Standaard is het time-outinterval ingesteld op Regex.InfiniteMatchTimeout en treedt er geen time-out op voor de engine voor reguliere expressies.

Een RegexMatchTimeoutException uitzondering geeft aan dat de engine voor reguliere expressies geen overeenkomst kon vinden binnen het opgegeven time-outinterval, maar niet aangeeft waarom de uitzondering is gegenereerd. De reden kan overmatige backtracking zijn, maar het is ook mogelijk dat het time-outinterval te laag is ingesteld, gezien de systeembelasting op het moment dat de uitzondering werd gegenereerd. Wanneer u de uitzondering afhandelt, kunt u ervoor kiezen om verdere overeenkomsten met de invoertekenreeks te verlaten of het time-outinterval te verhogen en de overeenkomende bewerking opnieuw uit te voeren.

Met de volgende code wordt de Regex(String, RegexOptions, TimeSpan) constructor bijvoorbeeld aangeroepen om een Regex object te instantiëren met een time-outwaarde van 1 seconde. Het reguliere expressiepatroon (a+)+$, dat overeenkomt met een of meer reeksen van een of meer a-tekens aan het einde van een regel, is onderhevig aan overmatige backtracking. Als er een RegexMatchTimeoutException optreedt, verhoogt het voorbeeld de time-outwaarde tot een maximuminterval van 3 seconden. Daarna staakt het de poging om het patroon te herkennen.

using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading;

public class Example
{
    const int MaxTimeoutInSeconds = 3;

    public static void Main()
    {
        string pattern = @"(a+)+$";    // DO NOT REUSE THIS PATTERN.
        Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));
        Stopwatch? sw = null;

        string[] inputs = { "aa", "aaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                         "aaaaaaaaaaaaaaaaaaaaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };

        foreach (var inputValue in inputs)
        {
            Console.WriteLine($"Processing {inputValue}");
            bool timedOut = false;
            do
            {
                try
                {
                    sw = Stopwatch.StartNew();
                    // Display the result.
                    if (rgx.IsMatch(inputValue))
                    {
                        sw.Stop();
                        Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                    else
                    {
                        sw.Stop();
                        Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                }
                catch (RegexMatchTimeoutException e)
                {
                    sw.Stop();
                    // Display the elapsed time until the exception.
                    Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed);
                    Thread.Sleep(1500);       // Pause for 1.5 seconds.

                    // Increase the timeout interval and retry.
                    TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
                    if (timeout.TotalSeconds > MaxTimeoutInSeconds)
                    {
                        Console.WriteLine($"Maximum timeout interval of {MaxTimeoutInSeconds} seconds exceeded.");
                        timedOut = false;
                    }
                    else
                    {
                        Console.WriteLine($"Changing the timeout interval to {timeout}");
                        rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
                        timedOut = true;
                    }
                }
            } while (timedOut);
            Console.WriteLine();
        }
    }
}
// The example displays output like the following :
//    Processing aa
//    Valid: 'aa' (00.0000779 seconds)
//
//    Processing aaaa>
//    'aaaa>' is not a valid string. (00.00005 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
//    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
//    Changing the timeout interval to 00:00:02
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
//    Changing the timeout interval to 00:00:03
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
//    Maximum timeout interval of 3 seconds exceeded.
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
//    Maximum timeout interval of 3 seconds exceeded.

Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading

Module Example
    Const MaxTimeoutInSeconds As Integer = 3

    Public Sub Main()
        Dim pattern As String = "(a+)+$"    ' DO NOT REUSE THIS PATTERN.
        Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))
        Dim sw As Stopwatch = Nothing

        Dim inputs() As String = {"aa", "aaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                                   "aaaaaaaaaaaaaaaaaaaaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>"}

        For Each inputValue In inputs
            Console.WriteLine("Processing {0}", inputValue)
            Dim timedOut As Boolean = False
            Do
                Try
                    sw = Stopwatch.StartNew()
                    ' Display the result.
                    If rgx.IsMatch(inputValue) Then
                        sw.Stop()
                        Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed)
                    Else
                        sw.Stop()
                        Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed)
                    End If
                Catch e As RegexMatchTimeoutException
                    sw.Stop()
                    ' Display the elapsed time until the exception.
                    Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed)
                    Thread.Sleep(1500)       ' Pause for 1.5 seconds.

                    ' Increase the timeout interval and retry.
                    Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
                    If timeout.TotalSeconds > MaxTimeoutInSeconds Then
                        Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                          MaxTimeoutInSeconds)
                        timedOut = False
                    Else
                        Console.WriteLine("Changing the timeout interval to {0}",
                                          timeout)
                        rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
                        timedOut = True
                    End If
                End Try
            Loop While timedOut
            Console.WriteLine()
        Next
    End Sub
End Module
' The example displays output like the following:
'    Processing aa
'    Valid: 'aa' (00.0000779 seconds)
'    
'    Processing aaaa>
'    'aaaa>' is not a valid string. (00.00005 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
'    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
'    Changing the timeout interval to 00:00:02
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
'    Changing the timeout interval to 00:00:03
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
'    Maximum timeout interval of 3 seconds exceeded.
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
'    Maximum timeout interval of 3 seconds exceeded.

Atomische groepen

Het (?>subexpressietaalelement) is een atomische groepering. Hiermee voorkomt u dat er backtracking wordt uitgevoerd naar de subexpressie. Zodra dit taalelement succesvol overeenkomt, staat het bij latere backtracking geen enkel deel van de gevonden overeenkomst af. Bijvoorbeeld: in het patroon (?>\w*\d*)1, als 1 niet kan worden gematcht, staat \d* niets van zijn match af, zelfs niet als dat zou betekenen dat 1 dan wel succesvol kan worden gematcht. Atomische groepen kunnen helpen de prestatieproblemen te voorkomen die zijn gekoppeld aan mislukte overeenkomsten.

In het volgende voorbeeld ziet u hoe het onderdrukken van backtracking de prestaties verbetert bij het gebruik van geneste kwantificatoren. Het meet de tijd die nodig is voor de engine voor reguliere expressies om te bepalen dat een invoertekenreeks niet overeenkomt met twee reguliere expressies. De eerste reguliere expressie gebruikt backtracking om te proberen overeen te komen met een tekenreeks die een of meer voorkomens van een of meer hexadecimale cijfers bevat, gevolgd door een dubbele punt, gevolgd door een of meer hexadecimale cijfers, gevolgd door twee dubbele punten. De tweede reguliere expressie is identiek aan de eerste, behalve dat backtracking wordt uitgeschakeld. Zoals de uitvoer uit het voorbeeld laat zien, is de prestatieverbetering van het uitschakelen van backtracking aanzienlijk.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example4
{
    public static void Run()
    {
        string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
        bool matched;
        Stopwatch sw;

        Console.WriteLine("With backtracking:");
        string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, backPattern);
        sw.Stop();
        Console.WriteLine($"Match: {Regex.IsMatch(input, backPattern)} in {sw.Elapsed}");
        Console.WriteLine();

        Console.WriteLine("Without backtracking:");
        string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, noBackPattern);
        sw.Stop();
        Console.WriteLine($"Match: {Regex.IsMatch(input, noBackPattern)} in {sw.Elapsed}");
    }
}
// The example displays output like the following:
//       With backtracking:
//       Match: False in 00:00:27.4282019
//
//       Without backtracking:
//       Match: False in 00:00:00.0001391

Imports System.Text.RegularExpressions

Module Example4
    Public Sub Run()
        Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
        Dim matched As Boolean
        Dim sw As Stopwatch

        Console.WriteLine("With backtracking:")
        Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, backPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
        Console.WriteLine()

        Console.WriteLine("Without backtracking:")
        Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, noBackPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       With backtracking:
'       Match: False in 00:00:27.4282019
'       
'       Without backtracking:
'       Match: False in 00:00:00.0001391

lookbehind-beweringen

.NET bevat twee taalelementen, (?<=subexpressie) en (?<!subexpressie), die overeenkomen met het vorige teken of de vorige tekens in de invoertekenreeks. Beide taalelementen zijn asserties met nul breedte; dat wil gezegd, ze bepalen of het teken of de tekens die direct voorafgaan aan het huidige teken, kunnen worden vergeleken met subexpressie, zonder vooruit of terug te gaan.

(?<= subexpression) is een positieve lookbehind-assertie; dat wil zeggen: het teken of de tekens vóór de huidige positie moeten overeenkomen met subexpression. (?<! subexpressie) is een negatieve lookbehind-assertie; dat wil zeggen dat het teken of de tekens vóór de huidige positie niet mogen overeenkomen met subexpressie. Zowel positieve als negatieve lookbehind-asserties zijn het handigst wanneer subexpressie een subset van de vorige subexpressie is.

In het volgende voorbeeld worden twee equivalente reguliere expressiepatronen gebruikt waarmee de gebruikersnaam in een e-mailadres wordt gevalideerd. Het eerste patroon is onderhevig aan slechte prestaties vanwege overmatige backtracking. Het tweede patroon past de eerste reguliere expressie aan door een geneste kwantificator te vervangen door een positieve lookbehind-assertie. In de uitvoer van het voorbeeld wordt de uitvoeringstijd van de Regex.IsMatch methode weergegeven.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example5
{
    public static void Run()
    {
        Stopwatch sw;
        string input = "test@contoso.com";
        bool result;

        string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"Match: {result} in {sw.Elapsed}");

        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"Match with Lookbehind: {result} in {sw.Elapsed}");
    }
}
// The example displays output similar to the following:
//       Match: True in 00:00:00.0017549
//       Match with Lookbehind: True in 00:00:00.0000659

Module Example5
    Public Sub Run()
        Dim sw As Stopwatch
        Dim input As String = "test@contoso.com"
        Dim result As Boolean

        Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)

        Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays output similar to the following:
'       Match: True in 00:00:00.0017549
'       Match with Lookbehind: True in 00:00:00.0000659

Het eerste reguliere expressiepatroon, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.

Het tweede reguliere expressiepatroon, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@gebruikt een positieve lookbehind-assertie. Deze wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.

Lookahead-assertions

.NET bevat twee taalelementen, (?=subexpressie) en (?!subexpressie), die overeenkomen met het volgende teken of de volgende tekens in de invoertekenreeks. Beide taalelementen zijn asserties met nul breedte; dat wil gezegd, bepalen ze of het teken of de tekens die direct volgen op het huidige teken, kunnen worden vergeleken met subexpressie, zonder vooruit of terug te gaan.

(?= subexpressie) is een positieve lookahead-assertie; dat wil zeggen: het teken of de tekens na de huidige positie moeten overeenkomen met subexpressie. (?! subexpressie) is een negatieve vooruitkijkassertie; dat wil zeggen dat het teken of de tekens na de huidige positie niet mogen overeenkomen met subexpressie. Zowel positieve als negatieve lookahead-asserties zijn het nuttigst wanneer subexpressie een subset van de volgende subexpressie is.

In het volgende voorbeeld worden twee equivalente reguliere expressiepatronen gebruikt waarmee een volledig gekwalificeerde typenaam wordt gevalideerd. Het eerste patroon is onderhevig aan slechte prestaties vanwege overmatige backtracking. De tweede wijzigt de eerste reguliere expressie door een geneste kwantificator te vervangen door een positieve lookahead-assertie. In de uitvoer van het voorbeeld wordt de uitvoeringstijd van de Regex.IsMatch methode weergegeven.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example6
{
    public static void Run()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        bool result;
        Stopwatch sw;

        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"{result} in {sw.Elapsed}");

        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"{result} in {sw.Elapsed}");
    }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866

Imports System.Text.RegularExpressions

Module Example6
    Public Sub Run()
        Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
        Dim result As Boolean
        Dim sw As Stopwatch

        Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)

        Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       False in 00:00:03.8003793
'       False in 00:00:00.0000866

Het eerste reguliere expressiepatroon, ^(([A-Z]\w*)+\.)*[A-Z]\w*$wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.

Het tweede reguliere expressiepatroon, ^((?=[A-Z])\w+\.)*[A-Z]\w*$maakt gebruik van een positieve lookahead-assertie. Deze wordt gedefinieerd zoals wordt weergegeven in de volgende tabel.

Algemene prestatieoverwegingen

De volgende suggesties zijn niet specifiek bedoeld om overmatige backtracking te voorkomen, maar kunnen de prestaties van uw reguliere expressie verbeteren:

1. Precompileer veelgebruikte patronen. De beste manier om dit te doen, is door de brongenerator voor reguliere expressies te gebruiken om deze vooraf te compileren. Als de brongenerator niet beschikbaar is voor uw app, bijvoorbeeld als u zich niet richt op .NET 7 of hoger, of als u het patroon tijdens het compileren niet kent, gebruikt u de RegexOptions.Compiled optie.

2. Sla veelgebruikte Regex-objecten op in de cache. Dit gebeurt impliciet wanneer u de brongenerator gebruikt. Anders maakt u een Regex-object en slaat u het op voor hergebruik, in plaats van de statische Regex-methoden te gebruiken of een Regex-object te maken en weg te gooien.

3. Begin met vergelijken vanaf een offset. Als u weet dat overeenkomsten altijd pas na een bepaalde positie in het patroon beginnen, geeft u de offset door via een overload zoals Regex.Match(String, Int32). Dit vermindert de hoeveelheid tekst die de engine moet overwegen.

4. Verzamel alleen de informatie die u nodig hebt. Als u alleen wilt weten of een overeenkomst plaatsvindt, maar niet waar de overeenkomst plaatsvindt, geeft u de voorkeur Regex.IsMatch. Als u alleen hoeft te weten hoe vaak iets overeenkomt, gebruikt u liever Regex.Count. Als u alleen de grenzen van een match hoeft te kennen, maar niets over de vastgelegde groepen van een match, kunt u beter Regex.EnumerateMatches gebruiken. Hoe minder informatie de engine moet leveren, hoe beter.

5. Vermijd onnodige opnamen. Haakjes in uw patroon vormen standaard een vastleggende groep. Als u geen captures nodig hebt, geef dan RegexOptions.ExplicitCapture op of gebruik in plaats daarvan niet-vastleggende groepen. Hierdoor hoeft de engine die captures niet bij te houden.

Zie ook

• Reguliere .NET-expressies
• Reguliere expressietaal - Snelzoekgids
• Kwantoren
• Alternation Constructs
• Constructies voor groeperen