Bakåtspårning i reguljära uttryck

Bakåtspårning sker när ett mönster för reguljära uttryck innehåller valfria kvantifierare eller växlingskonstruktioner, och motorn för reguljära uttryck återgår till ett tidigare sparat tillstånd för att fortsätta sökningen efter en matchning. Backtracking är avgörande för styrkan hos reguljära uttryck; det gör dem kraftfulla och flexibla och gör det möjligt att matcha mycket komplexa mönster. Samtidigt kommer den här kraften till en kostnad. Backtracking är ofta den enskilt viktigaste faktorn som påverkar prestanda för den reguljära uttrycksmotorn. Lyckligtvis har utvecklaren kontroll över beteendet för motorn för reguljära uttryck och hur den använder backtracking. Den här artikeln förklarar hur backtracking fungerar och hur du kan kontrollera det.

Linjär jämförelse utan bakåtspårning

Om ett reguljärt uttrycksmönster inte har några valfria kvantifierare eller alternationskonstruktioner körs motorn för reguljära uttryck linjärt. Efter att motorn för reguljära uttryck matchar det första språkelementet i mönstret med text i indatasträngen försöker den matcha nästa språkelement i mönstret med nästa tecken eller grupp med tecken i indatasträngen. Detta fortsätter tills matchningen lyckas eller misslyckas. I båda fallen avancerar motorn för reguljära uttryck med ett tecken i taget i indatasträngen.

I följande exempel visas en bild. Det reguljära uttrycket e{2}\w\b söker efter två förekomster av bokstaven "e" följt av ordtecken följt av en ordgräns.

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

Även om det här reguljära uttrycket innehåller kvantifieraren {2}utvärderas det linjärt. Motorn för reguljära uttryck backar inte eftersom {2} den inte är en valfri kvantifierare. Den anger ett exakt tal och inte ett variabelt antal gånger som föregående underuttryck måste matcha. Det innebär att motorn för reguljära uttryck försöker matcha mönstret för reguljära uttryck med indatasträngen enligt följande tabell.

Om ett mönster för reguljära uttryck inte innehåller några valfria kvantifierare eller växlingskonstruktioner motsvarar det maximala antalet jämförelser som krävs för att matcha mönstret för reguljära uttryck med indatasträngen ungefär lika med antalet tecken i indatasträngen. I det här fallet använder motorn för reguljära uttryck 19 jämförelser för att identifiera möjliga matchningar i den här strängen med 13 tecken. Med andra ord körs motorn för reguljära uttryck nästan linjärt om den inte innehåller några valfria kvantifierare eller alternationskonstruktioner.

Bakåtspårning med valfria kvantifierare eller växlingskonstruktioner

När ett reguljärt uttryck innehåller valfria kvantifierare eller alternationskonstruktioner är utvärderingen av indatasträngen inte längre linjär. Mönstermatchning med en nondeterministisk Finite Automaton-motor (NFA) drivs av språkelementen i det reguljära uttrycket och inte av de tecken som ska matchas i indatasträngen. Därför försöker motorn för reguljära uttryck att helt matcha valfria eller alternativa underuttryck. När den går vidare till nästa språkelement i underuttrycket och matchningen misslyckas kan motorn för reguljära uttryck överge en del av sin lyckade matchning och återgå till ett tidigare sparat tillstånd för att matcha det reguljära uttrycket som helhet med indatasträngen. Den här processen att återgå till ett tidigare sparat tillstånd för att hitta en matchning kallas bakåtspårning.

Tänk till exempel på det reguljära uttrycksmönstret .*(es), som matchar tecknen "es" och alla tecken som föregår det. Som följande exempel visar, om indatasträngen är "Essential services are provided by regular expressions.", matchar mönstret hela strängen fram till och med "es" i "expressions".

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

För att göra detta använder motorn för reguljära uttryck bakåtspårning på följande sätt:

• Den matchar .* (som matchar noll, en eller flera förekomster av något tecken) med hela indatasträngen.

• Den försöker matcha "e" i mönstret för reguljära uttryck. Indatasträngen har dock inga återstående tecken att matcha.

• Den backar till sin senaste lyckade matchning, "Viktiga tjänster tillhandahålls av reguljära uttryck" och försöker matcha "e" med perioden i slutet av meningen. Matchningen misslyckas.

• Det fortsätter att backa till en tidigare lyckad matchning ett tecken i taget tills den preliminärt matchade delsträngen är "Essential services are provided by regular expr". Den jämför sedan "e" i mönstret med det andra "e" i "uttryck" och hittar en matchning.

• Den jämför "s" i mönstret med det "s" som följer det matchade "e"-tecknet (det första "s" i "expressions"). Matchningen lyckas.

När du använder backtracking krävs 67 jämförelseåtgärder för att matcha det reguljära uttrycksmönstret med indatasträngen, som är 55 tecken lång. Om ett reguljärt uttrycksmönster har en enda alternationskonstruktion eller en enda valfri kvantifierare är antalet jämförelseåtgärder som krävs för att matcha mönstret mer än dubbelt så många tecken i indatasträngen.

Backtracking med kapslade valfria kvantifierare

Antalet jämförelseåtgärder som krävs för att matcha ett mönster för reguljära uttryck kan öka exponentiellt om mönstret innehåller ett stort antal alternationskonstruktioner, om det innehåller kapslade alternationskonstruktioner, eller oftast om det innehåller kapslade valfria kvantifierare. Mönstret ^(a+)+$ för reguljära uttryck är till exempel utformat för att matcha en fullständig sträng som innehåller ett eller flera "a"-tecken. Exemplet innehåller två indatasträngar med identisk längd, men endast den första strängen matchar mönstret. Klassen System.Diagnostics.Stopwatch används för att avgöra hur lång tid matchningsåtgärden tar.

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

Som utdata från exemplet visar tog det betydligt längre tid för motorn för reguljära uttryck att upptäcka att en indatasträng inte matchade mönstret som den gjorde för att identifiera en matchande sträng. Det beror på att en misslyckad matchning alltid representerar ett värsta scenario. Motorn för reguljära uttryck måste använda reguljära uttryck för att följa alla möjliga sökvägar genom data innan den kan dra slutsatsen att matchningen misslyckas och de kapslade parenteserna skapar många ytterligare sökvägar genom data. Motorn för reguljära uttryck drar slutsatsen att den andra strängen inte matchade mönstret genom att göra följande:

• Den kontrollerar att den var i början av strängen och matchar sedan de första fem tecknen i strängen med mönstret a+. Den avgör sedan att det inte finns några ytterligare grupper med "a"-tecken i strängen. Slutligen kontrollerar den om det är slutet av strängen. Eftersom ytterligare ett tecken finns kvar i strängen misslyckas matchningen. Denna misslyckade matchning kräver 9 jämförelser. Motorn för reguljära uttryck sparar även tillståndsinformation om sina matchningar av "a" (som vi kallar matchning 1), "aa" (matchning 2), "aaa" (matchning 3) och "aaaa" (matchning 4).

• Den återgår till den tidigare sparade matchningen 4. Den fastställer att det finns ytterligare ett "a"-tecken som ska tilldelas en ytterligare fångad grupp. Slutligen kontrollerar den om strängen är slut. Eftersom ytterligare ett tecken finns kvar i strängen misslyckas matchningen. Den här misslyckade matchningen kräver 4 jämförelser. Hittills har totalt 13 jämförelser utförts.

• Den återgår till den tidigare sparade matchningen 3. Den fastställer att det finns två ytterligare "a"-tecken att tilldela en ytterligare fångstgrupp. Dock misslyckas testet för strängslut. Sedan går den tillbaka till den tredje matchningen och försöker matcha de två ytterligare "a"-tecknen i ytterligare två fångstgrupper. Testet i slutet av strängen misslyckas fortfarande. Dessa misslyckade matchningar kräver 12 jämförelser. Hittills har totalt 25 jämförelser utförts.

Jämförelsen av indatasträngen med det reguljära uttrycket fortsätter på det här sättet tills motorn för reguljära uttryck har provat alla möjliga kombinationer av matchningar och sedan drar slutsatsen att det inte finns någon matchning. På grund av de kapslade kvantifierarna är den här jämförelsen en O(2ⁿ) eller en exponentiell åtgärd, där n är antalet tecken i indatasträngen. Det innebär att i värsta fall kräver en indatasträng på 30 tecken cirka 1 073 741 824 jämförelser och en indatasträng på 40 tecken kräver cirka 1 099 511 627 776 jämförelser. Om du använder strängar av dessa eller ännu större längder kan reguljära uttrycksmetoder ta mycket lång tid att slutföra när de bearbetar indata som inte matchar det reguljära uttrycksmönstret.

Styr bakåtspårning

Med bakåtspårning kan du skapa kraftfulla, flexibla reguljära uttryck. Men som föregående avsnitt visade kan dessa fördelar kombineras med oacceptabelt dåliga prestanda. För att förhindra överdriven backtracking bör du definiera ett tidsgränsintervall när du instansierar ett Regex objekt eller anropar en matchningsmetod för statiska reguljära uttryck. Detta beskrivs i nästa avsnitt. Dessutom har .NET stöd för tre reguljära uttrycksspråkelement som begränsar eller undertrycker backtracking och som stöder komplexa reguljära uttryck med liten eller ingen prestandaförsämring: atomiska grupper, lookbehind-försäkran och lookahead-försäkran. Mer information om varje språkelement finns i Grupperingskonstruktioner.

Motor för reguljära uttryck utan bakåtspårning

Om du inte behöver använda några konstruktioner som kräver backtracking (till exempel lookaround-uttryck, bakåtreferenser eller atomiska grupper), bör du överväga att använda RegexOptions.NonBacktracking-läget. Det här läget är utformat för att köras i tid som är proportionellt mot längden på indata. Mer information finns i NonBacktracking-läge. Du kan också ange ett timeout-värde.

Begränsa storleken på indata

Vissa reguljära uttryck har godtagbara prestanda om inte indata är exceptionellt stora. Om alla rimliga textindata i ditt scenario är kända för att vara under en viss längd bör du överväga att avvisa längre indata innan du tillämpar det reguljära uttrycket på dem.

Ange ett tidsgränsintervall

Du kan ange ett timeout-värde som representerar det längsta intervallet som motorn för reguljära uttryck söker efter en enda matchning innan den överger försöket och genererar ett RegexMatchTimeoutException undantag. Du anger tidsgränsintervallet genom att ange ett TimeSpan värde till Regex(String, RegexOptions, TimeSpan) konstruktorn för reguljära instansuttryck. Dessutom har varje statisk mönstermatchningsmetod en överlagring med en TimeSpan parameter som gör att du kan ange ett timeout-värde.

Om du inte uttryckligen anger ett timeout-värde bestäms standardvärdet för timeout enligt följande:

• Med hjälp av tidsgränsvärdet för hela programmet, om det finns ett sådant. Detta kan vara ett timeout-värde som gäller för programdomänen Regex där objektet instansieras eller det statiska metodanropet görs. Du kan ange timeout-värdet för hela programmet genom att anropa AppDomain.SetData metoden för att tilldela strängrepresentationen av ett TimeSpan värde till REGEX_DEFAULT_MATCH_TIMEOUT egenskapen.
• Genom att använda värdet InfiniteMatchTimeout, om inget timeout-värde för hela programmet har angetts.

Som standard är timeout-intervallet inställt på Regex.InfiniteMatchTimeout och ingen timeout inträffar för motorn för reguljära uttryck.

Ett RegexMatchTimeoutException undantag anger att motorn för reguljära uttryck inte kunde hitta en matchning inom det angivna tidsgränsintervallet, men anger inte varför undantaget utlöstes. Orsaken kan vara överdriven backtracking, men det är också möjligt att tidsgränsintervallet angavs för lågt med tanke på systembelastningen när undantaget utlöstes. När du hanterar undantaget kan du välja att avbryta ytterligare matchningar med indatasträngen eller öka tidsgränsintervallet och försöka matcha åtgärden igen.

Följande kod anropar Regex(String, RegexOptions, TimeSpan) till exempel konstruktorn för att instansiera ett Regex objekt med ett timeout-värde på 1 sekund. Det reguljära uttrycksmönstret (a+)+$, som matchar en eller flera sekvenser med ett eller flera "a"-tecken i slutet av en rad, är föremål för överdriven bakåtspårning. Om en RegexMatchTimeoutException utlöses ökar exemplet tidsgränsvärdet till högst 3 sekunder. Därefter avbryts försöket att matcha mönstret.

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.

Atomiska grupper

Underuttrycksspråkelementet (?>)är en atomisk gruppering. Det förhindrar bakåtspårning in i underuttrycket. När detta språkelement väl har matchats kommer det inte att släppa ifrån sig någon del av matchningen vid efterföljande backtracking. Till exempel, i mönstret (?>\w*\d*)1, om 1 inte kan matchas, kommer \d* inte att ge upp någon del av det den har matchat, även om det skulle göra det möjligt för 1 att matchas. Atomgrupper kan hjälpa till att förhindra prestandaproblem som är associerade med misslyckade matchningar.

I följande exempel visas hur om du undertrycker backtracking förbättras prestandan när du använder kapslade kvantifierare. Den mäter den tid som krävs för motorn för reguljära uttryck för att fastställa att en indatasträng inte matchar två reguljära uttryck. Det första reguljära uttrycket använder backtracking för att försöka matcha en sträng som innehåller en eller flera förekomster av en eller flera hexadecimala siffror, följt av ett kolon följt av en eller flera hexadecimala siffror, följt av två kolon. Det andra reguljära uttrycket är identiskt med det första, förutom att det inaktiverar bakåtspårning. Som utdata från exemplet visar är prestandaförbättringen från att inaktivera backtracking betydande.

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

Bakåtblickande assertioner

.NET innehåller två språkelement, (?<=underuttryck) och (?<!underuttryck), som matchar föregående tecken eller tecken i indatasträngen. Båda språkelementen är nollbreddskontroller. De avgör alltså om tecknet eller tecknen som omedelbart föregår det aktuella tecknet kan matchas av underuttryck, utan att avancera eller bakåtspåra.

(?<= subexpression) är ett positivt lookbehind-villkor, det vill säga att tecknet eller tecknen före den aktuella positionen måste matcha subexpression. (?<! subexpression) är ett negativt lookbehind-assertion, det vill säga att tecknet eller tecknen som föregår den aktuella positionen inte får matcha subexpression. Både positiva och negativa lookbehind-kontroller är som mest användbara när underuttryck är en delmängd av det föregående underuttrycket.

I följande exempel används två motsvarande mönster för reguljära uttryck som validerar användarnamnet i en e-postadress. Det första mönstret är föremål för dåliga prestanda på grund av överdriven backtracking. Det andra mönstret ändrar det första reguljära uttrycket genom att ersätta en kapslad kvantifierare med en positiv lookbehind-försäkran. Utdata från exemplet visar körningstiden för Regex.IsMatch metoden.

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

Det första reguljära uttrycksmönstret, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, definieras enligt följande tabell.

Det andra reguljära uttrycksmönstret, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, använder en positiv lookbehind-assertion. Den definieras enligt följande tabell.

Lookahead-påstående

.NET innehåller två språkelement, (?=underuttryck) och (?!underuttryck), som matchar nästa tecken eller tecken i indatasträngen. Båda språkelementen är nollbreddskontroller. De avgör alltså om tecknet eller tecknen som omedelbart följer det aktuella tecknet kan matchas av underuttryck, utan att avancera eller backa.

(?= subexpression) är ett positivt lookahead-villkor, det vill säga att tecknet eller tecknen efter den aktuella positionen måste matcha subexpression. (?! subexpression) är ett negativt lookahead-villkor; det vill säga: tecknet eller tecknena efter den aktuella positionen får inte matcha subexpression. Både positiva och negativa lookahead-villkor är mest användbara när underuttryck utgör en delmängd av nästa underuttryck.

I följande exempel används två motsvarande mönster för reguljära uttryck som verifierar ett fullständigt kvalificerat typnamn. Det första mönstret ger dålig prestanda på grund av omfattande bakåtspårning. Det andra ändrar det första reguljära uttrycket genom att ersätta en kapslad kvantifierare med en positiv lookahead-försäkran. Resultatet i exemplet visar körningstiden för metoden Regex.IsMatch.

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

Det första reguljära uttrycksmönstret, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, definieras enligt följande tabell.

Det andra reguljära uttrycksmönstret, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, använder en positiv lookahead-försäkran. Den definieras enligt följande tabell.

Allmänna prestandaöverväganden

Följande förslag är inte specifikt avsedda att förhindra överdriven backtracking, men kan bidra till att förbättra prestandan hos ditt reguljära uttryck:

1. Förkompilera starkt använda mönster. Det bästa sättet att göra detta är att använda källgeneratorn för reguljära uttryck för att förkompilera den. Om källgeneratorn inte är tillgänglig för din app, till exempel om du inte riktar in dig på .NET 7 eller senare, eller om du inte känner till mönstret vid kompileringstillfället, använder du RegexOptions.Compiled alternativet .

2. Cachelagrade regex-objekt som används mycket. Detta inträffar implicit när du använder källgeneratorn. Annars skapar du ett Regex-objekt och lagrar det för återanvändning i stället för att använda statiska Regex-metoder eller skapa och kasta bort ett Regex-objekt.

3. Börja matchningen från ett offset. Om du vet att matchningar alltid börjar bortom en viss förskjutning i mönstret skickar du in förskjutningen med hjälp av en överlagring som Regex.Match(String, Int32). Detta minskar mängden text som motorn behöver tänka på.

4. Samla bara in den information du behöver. Om du bara behöver veta om en matchning inträffar men inte var matchningen sker, föredrar du Regex.IsMatch. Om du bara behöver veta hur många gånger något matchar föredrar du att använda Regex.Count. Om du bara behöver veta var en matchning börjar och slutar, men inte något om en matchnings fångster, bör du använda Regex.EnumerateMatches. Desto mindre information behöver motorn ge, desto bättre.

5. Undvik onödiga avbildningar. Parenteser i ditt mönster bildar som standard en fångstgrupp. Om du inte behöver fångstgrupper anger du antingen RegexOptions.ExplicitCapture eller använder icke-fångande grupper i stället. Detta gör att motorn slipper hålla reda på dessa fångster.

Se även

• Reguljära .NET-uttryck
• Språk för reguljärt uttryck – snabbreferens
• Kvantifierare
• Alternationskonstruktioner
• Grupperingskonstruktioner