Zpětné prohledávání v regulárních výrazech

Zpětné navracení nastane, když vzor regulárního výrazu obsahuje volitelné kvantifikátory nebo konstrukce alternace a modul regulárních výrazů se vrátí do předchozího uloženého stavu, aby pokračoval ve hledání shody. Backtracking je zásadní pro možnosti regulárních výrazů; díky němu jsou regulární výrazy mocné a flexibilní a dokážou odpovídat i velmi složitým vzorům. Tento výkon však zároveň něco stojí. Zpětné prohledávání je často zdaleka nejdůležitějším faktorem, který ovlivňuje výkon modulu regulárních výrazů. Vývojář má naštěstí kontrolu nad chováním modulu pro regulární výrazy a nad způsobem, jakým používá backtracking. Tento článek vysvětluje, jak funguje navracení a jak ho můžete řídit.

Upozornění

Neomezené použití System.Text.RegularExpressions s nedůvěryhodným vstupem může podléhat aplikacím útokům na dostupnost služby. Pokyny k bezpečnému použití .NET regulárních výrazů s nedůvěryhodným vstupem najdete v osvědčených postupech pro regulární výrazy v .NET.

Lineární porovnání bez zpětného navracení

Pokud vzor regulárního výrazu nemá žádné volitelné kvantifikátory nebo konstrukce alternace, bude modul regulárních výrazů spuštěn v lineárním čase. Což znamená, že jakmile se modul regulárních výrazů shoduje s prvním prvkem jazyka ve vzorci s textem ve vstupním řetězci, pokusí se vyhledat další prvek jazyka ve vzoru s dalším znakem nebo skupinou znaků ve vstupním řetězci. To pokračuje, dokud porovnání neskončí úspěchem nebo neúspěchem. V obou případech modul pro zpracování regulárních výrazů postupuje ve vstupním řetězci vždy o jeden znak.

V následujícím příkladu je uvedena ukázka. Regulární výraz e{2}\w\b hledá dva výskyty písmena "e" následované libovolným znakem slova následovaným hranicí slova.

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

I když tento regulární výraz obsahuje kvantifikátor {2}, je vyhodnocen lineárním způsobem. Modul regulárních výrazů se nevrátí zpět, protože {2} není volitelným kvantifikátorem. Určuje přesné číslo, nikoli proměnlivý počet, kolikrát se předchozí dílčí výraz musí shodovat. V důsledku toho se modul pro regulární výrazy pokusí porovnat vzor regulárního výrazu se vstupním řetězcem, jak ukazuje následující tabulka.

Operace Pozice ve vzoru Pozice v řetězci Výsledek
1 e potřebující rákosku Nenalezena žádná shoda.
2 e krmení rákosu Možná shoda.
3 e{2} „… rákos“ (index 2) Možná shoda.
4 \w „ťuknout do jazýčku“ (index 3) Možná shoda.
5 \b „… jazýček“ (index 4) Možná shoda selže.
6 e "eding a reed" (index 2) Možná shoda.
7 e{2} „ťuknout do jazýčku“ (index 3) Možná shoda selže.
8 e „ťuknout do jazýčku“ (index 3) Shoda selhala.
9 e „… jazýček“ (index 4) Nenalezena žádná shoda.
10 e "ng a reed" (index 5) Nenalezena žádná shoda.
11 e "g a reed" (index 6) Nenalezena žádná shoda.
12 e " a reed" (index 7) Nenalezena žádná shoda.
13 e rákos Nenalezena žádná shoda.
14 e " reed" (index 9) Nenalezena žádná shoda.
15 e "reed" (index 10) Žádná shoda
16 e "eed" (index 11) Možná shoda.
17 e{2} "ed" (index 12) Možná shoda.
18 \w "d" (index 13) Možná shoda.
19 \b "" (index 14) Shoda.

Pokud vzor regulárního výrazu neobsahuje žádné volitelné kvantifikátory nebo konstrukce alternace, musí maximální počet porovnání odpovídající vzoru regulárního výrazu se vstupním řetězcem být zhruba ekvivalentní počtu znaků ve vstupním řetězci. V tomto případě používá modul regulárních výrazů 19 porovnání k identifikaci možných shod v tomto řetězci o 13 znacích. Jinými slovy to znamená, že modul regulárních výrazů je spuštěn v téměř lineárním čase, pokud neobsahuje žádné volitelné kvantifikátory nebo konstrukce alternace.

Zpětné prohledávání s volitelnými kvantifikátory nebo konstrukcemi alternace

Pokud regulární výraz zahrnuje volitelné kvantifikátory nebo alternace konstrukce, hodnocení vstupního řetězce již není lineární. Porovnávání vzorů pomocí modulu nedeterministického konečného automatu (NFA) se řídí jazykovými prvky v regulárním výrazu, nikoli znaky, které mají být porovnávány ve vstupním řetězci. Proto se modul regulárních výrazů pokouší o úplnou shodu volitelných nebo alternativních dílčích výrazů. Jakmile přejde na další prvek jazyka v dílčím výrazu a shoda není úspěšná, může modul regulárních výrazů opustit část úspěšné shody a vrátit se ke dříve uloženému stavu v zájmu shody celého regulárního výrazu ve vstupním řetězci. Tento proces návratu k dříve uloženému stavu za účelem nalezení shody se označuje jako zpětné prohledávání.

Představte si například vzor .*(es)regulárního výrazu, který odpovídá znakům "es" a všem znakům, které před ním předchází. Jak znázorňuje následující příklad, pokud je vstupní řetězec zadán jako „Essential services are provided by regular expressions.“, shoduje se vzor s celým řetězcem a obsahuje výraz „es“ ve slově „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

K tomu modul pro regulární výrazy používá zpětné prohledávání takto:

  • Odpovídá výrazu .* (který odpovídá nulovému, jednomu nebo více výskytům libovolného znaku) v celém vstupním řetězci.

  • Pokusí se najít shodu se znakem „e“ ve vzoru regulárního výrazu. Vstupní řetězec však již neobsahuje žádné zbývající znaky, které by bylo možné porovnat.

  • Navrátí se k poslední úspěšné shodě „Essential services are provided by regular expressions“ a pokusí se najít shodu pro písmeno „e“ s tečkou na konci věty. Tato shoda se nezdaří.

  • Bude pokračovat v navracení k předchozí úspěšné shodě vždy po jednom znaku, dokud nebude vyhledán nezávazně se shodující podřetězec „Essential services are provided by regular expr“. Poté porovná písmeno „e“ ve vzoru s druhým písmenem „e“ ve výrazu „expressions“ a najde shodu.

  • Porovná písmeno „s“ ve vzoru s písmenem „s“, které následuje za shodujícím se znakem „e“ (první výskyt písmene „s“ ve výrazu „expressions“). Shoda byla úspěšná.

Když použijete zpětné prohledávání, porovnání vzoru regulárního výrazu se vstupním řetězcem o délce 55 znaků vyžaduje 67 porovnávacích operací. Obecně platí, že pokud vzor regulárních výrazů má jedinou konstrukci alternace nebo jediný volitelný kvantifikátor, je počet operací porovnání vyžadovaný pro shodu vzoru více než dvakrát větší než počet znaků ve vstupním řetězci.

Zpětné prohledávání s vnořenými volitelnými kvantifikátory

Počet operací porovnání vyžadovaný pro shodu vzoru regulárního výrazu lze zvýšit exponenciálně, pokud vzor obsahuje velký počet konstrukcí alternace, pokud obsahuje vnořené konstrukce alternace, nebo pokud obsahuje vnořené volitelné kvantifikátory, což je nejčastější případ. Vzor regulárního výrazu ^(a+)+$ je například navržený tak, aby odpovídal úplnému řetězci, který obsahuje jeden nebo více znaků "a". Příklad obsahuje dva vstupní řetězce stejné délky, ale pouze první řetězec odpovídá vzoru. Třída System.Diagnostics.Stopwatch slouží k určení, jak dlouho trvá operace porovnání.

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

Jak ukazuje výstup z příkladu, modul regulárních výrazů trvalo výrazně déle, než zjistil, že vstupní řetězec neodpovídá vzoru, jako tomu bylo při identifikaci odpovídajícího řetězce. Je to proto, že neúspěšná shoda vždy představuje nejhorší případ. Modul pro zpracování regulárních výrazů musí použít regulární výraz a projít všechny možné cesty daty, než může dojít k závěru, že se nepodařilo najít shodu, a vnořené závorky vytvářejí mnoho dalších možných cest daty. Modul pro regulární výrazy dospěje k závěru, že druhý řetězec neodpovídal vzoru, a to takto:

  • Ověří, že je na začátku řetězce, a poté porovná prvních pět znaků řetězce se vzorem a+. Poté určí, zda řetězec neobsahuje žádné další skupiny znaků „a“. Nakonec ověří konec řetězce. Vzhledem k tomu, že v řetězci zůstává jeden další znak, shoda se nezdaří. Tato nezdařená shoda vyžaduje 9 porovnání. Modul pro zpracování regulárních výrazů také ukládá informace o stavu svých shod „a“ (kterou budeme označovat jako shodu 1), „aa“ (shoda 2), „aaa“ (shoda 3) a „aaaa“ (shoda 4).

  • Vrátí se k předchozí uložené shodě 4. Určí, že existuje další znak „a“, který lze přiřadit dodatečné zachycené skupině. Nakonec ověří konec řetězce. Vzhledem k tomu, že v řetězci zůstává jeden další znak, shoda se nezdaří. Toto neúspěšné porovnání vyžaduje 4 porovnání. Zatím bylo provedeno celkem 13 porovnání.

  • Vrátí se k dříve uloženému výskytu 3. Určí, že existují další dva znaky „a“, které lze přiřadit dodatečné zachycené skupině. Test konce řetězce se však nezdaří. Pak se vrátí ke 3. shodě a pokusí se porovnat dva další znaky „a“ ve dvou dalších zachycovacích skupinách. Test konce řetězce stále selhává. Tyto neúspěšné shody vyžadují 12 porovnání. Zatím bylo provedeno celkem 25 porovnání.

Porovnání vstupního řetězce s regulárním výrazem pokračuje tímto způsobem, dokud se modul regulárních výrazů nepokusí vyhledat všechny možné kombinace shody, a poté dojde k závěru, že neexistuje žádná shoda. Z důvodu vnořených kvantifikátorů je toto porovnání O(2n) nebo exponenciální operace, kde n je počet znaků ve vstupním řetězci. To znamená, že v nejhorším případě vyžaduje vstupní znak o délce 30 znaků přibližně 1 073 741 824 porovnání a vstupní znak o délce 40 znaků vyžaduje přibližně 1 099 511 627 776 porovnání. Pokud používáte řetězce o této nebo větší délce, může dokončení metod regulárních výrazů trvat extrémně dlouhou dobu, pokud zpracovávají obsah, který se neshoduje se vzorem regulárního výrazu.

Řízení zpětného prohledávání

Mechanismus navracení umožňuje vytvářet výkonné a pružné regulární výrazy. Jak již však bylo znázorněno v předchozích částech, mohou tyto výhody být vázány na nepřijatelně nízký výkon. Pokud chcete zabránit nadměrnému navracení, měli byste definovat interval časového limitu při vytvoření instance objektu Regex nebo volání metody porovnávání statických regulárních výrazů. Tento postup je popsán v následujícím oddíle. .NET navíc podporuje tři prvky jazyka regulárních výrazů, které omezují nebo potlačují zpětné prohledávání a podporují složité regulární výrazy s minimálním nebo žádným dopadem na výkon: atomické skupiny, zpětné predikáty a dopředné predikáty. Další informace o jednotlivých elementech jazyka naleznete v tématu Seskupování konstruktorů.

Modul regulárních výrazů bez zpětného prohledávání

Pokud nepotřebujete používat žádné konstrukce, které vyžadují zpětné prohledávání (například lookaroundy, zpětné odkazy nebo atomické skupiny), zvažte použití režimu RegexOptions.NonBacktracking. Tento režim je navržený tak, aby byl proveden v čase úměrný délce vstupu. Další informace naleznete v tématu režim NonBacktracking. Můžete také nastavit hodnotu časového limitu.

Omezení velikosti vstupů

Některé regulární výrazy mají přijatelný výkon, pokud vstup není mimořádně velký. Pokud u všech rozumných textových vstupů ve vašem scénáři víte, že nepřesahují určitou délku, zvažte odmítání delších vstupů předtím, než na ně použijete regulární výraz.

Zadejte interval časového limitu

Můžete nastavit hodnotu časového limitu, která určuje nejdelší interval, po který bude modul regulárních výrazů hledat jednu shodu, než od pokusu upustí a vyvolá výjimku RegexMatchTimeoutException. Interval časového limitu určíte předáním hodnoty TimeSpan konstruktoru Regex(String, RegexOptions, TimeSpan) pro instance regulárních výrazů. Kromě toho každá statická metoda porovnávání vzorů má přetížení s TimeSpan parametrem, který umožňuje zadat hodnotu časového limitu.

Pokud hodnotu časového limitu nenastavíte explicitně, výchozí hodnota časového limitu se určí takto:

  • Pokud existuje, použijte hodnotu časového limitu pro celou aplikaci. Může jít o jakoukoli hodnotu časového limitu, která se vztahuje k doméně aplikace, v níž je vytvořena instance objektu Regex nebo je provedeno volání statické metody. Hodnotu časového limitu pro celou aplikaci můžete nastavit voláním metody AppDomain.SetData, která přiřadí řetězcovou reprezentaci hodnoty TimeSpan vlastnosti REGEX_DEFAULT_MATCH_TIMEOUT.
  • Pokud nebyla nastavena žádná hodnota časového limitu pro celou aplikaci, použije se tato hodnota InfiniteMatchTimeout.

Ve výchozím nastavení je interval časového limitu nastaven na hodnotu Regex.InfiniteMatchTimeout a u modulu pro regulární výrazy nedojde k vypršení časového limitu.

Důležité

Pokud nepoužíváte RegexOptions.NonBacktracking, doporučujeme vždy nastavit interval časového limitu, pokud regulární výraz spoléhá na navracení nebo pracuje s nedůvěryhodnými vstupy.

Výjimka RegexMatchTimeoutException značí, že modul regulárních výrazů nemohl najít shodu v zadaném intervalu časového limitu, ale nezjistí důvod, proč došlo k výjimce. Důvodem může být nadměrný backtracking, ale je také možné, že časový limit byl nastaven příliš nízko vzhledem k zatížení systému v době, kdy byla výjimka vyvolána. Když tuto výjimku zpracováváte, můžete ukončit další hledání shod ve vstupním řetězci nebo prodloužit časový limit a operaci hledání shody zopakovat.

Například následující kód volá Regex(String, RegexOptions, TimeSpan) konstruktor pro vytvoření instance objektu Regex s hodnotou časového limitu 1 sekundy. Vzor regulárního výrazu (a+)+$, který odpovídá jedné nebo více sekvencím jednoho nebo více znaků „a“ na konci řádku, vykazuje nadměrné zpětné prohledávání. Pokud je vyvolána výjimka RegexMatchTimeoutException, příklad zvýší hodnotu časového limitu až na maximum 3 sekund. Poté upustí od pokusu o shodu se vzorem.

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.

Atomické skupiny

Jazykový prvek (?>podvýraz) je atomické seskupení. Zabraňuje zpětnému navracení do dílčího výrazu. Jakmile je tento jazykový prvek úspěšně nalezen, neuvolní žádnou část své shody pro následné zpětné prohledávání. Například ve vzoru (?>\w*\d*)1 platí, že pokud pro 1 nelze najít shodu, \d* se nevzdá žádné části své shody, i kdyby to znamenalo, že by se pak 1 mohl úspěšně porovnat. Atomické skupiny můžou pomoct zabránit problémům s výkonem přidruženým k neúspěšným shodám.

Následující příklad znázorňuje, jakým způsobem potlačení mechanismu navracení zlepšuje výkon při použití vnořených kvantifikátorů. Měří čas, který modul regulárních výrazů potřebuje k určení toho, zda se vstupní řetězec neshoduje s dvěma regulárními výrazy. První regulární výraz používá zpětné prohledávání, aby se pokusil najít shodu s řetězcem, který obsahuje jeden nebo více výskytů jedné či více šestnáctkových číslic, za nimiž následuje dvojtečka, poté jedna či více šestnáctkových číslic a nakonec dvě dvojtečky. Druhý regulární výraz je stejný jako první, jen s tím rozdílem, že vypíná zpětné prohledávání. Výstup z příkladu ukazuje, že zlepšení výkonu plynoucí ze zakázání mechanismu navracení je značné.

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

Kontrolní výrazy Lookbehind

.NET obsahuje dva prvky jazyka, (?<=dílčí výraz) a (?<!dílčí výraz), které odpovídají předchozímu znaku nebo znakům ve vstupním řetězci. Oba jazykové prvky jsou tvrzení nulové šířky; to znamená, že určují, zda znak nebo znaky, které bezprostředně předcházejí aktuálnímu znaku, lze porovnat s dílčím výrazem, aniž by se posouvalo vpřed nebo zpět.

(?<= subexpression) je pozitivní aserce zpětného pohledu; to znamená, že znak nebo znaky před aktuální pozicí musí odpovídat subexpression. (?<! subexpression) je negativní aserce zpětného vyhledání; to znamená, že znak nebo znaky před aktuální pozicí nesmí odpovídat subexpression. Kladné i záporné aserce lookbehind jsou nejužitečnější, když podvýraz je podmnožinou předchozího podvýrazu.

Následující příklad používá dva ekvivalentní vzory regulárních výrazů, které ověřují uživatelské jméno v e-mailové adrese. První vzor má nízký výkon kvůli nadměrnému zpětnému prohledávání. Druhý vzor modifikuje první regulární výraz tak, že nahradí vnořený kvantifikátor pozitivní zpětnou kontrolou. Výstup z příkladu zobrazí čas Regex.IsMatch spuštění metody.

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

První vzor regulárního výrazu , ^[0-9A-Z]([-.\w]*[0-9A-Z])*@je definován, jak je znázorněno v následující tabulce.

Vzor Popis
^ Zahájí porovnávání na začátku řetězce.
[0-9A-Z] Odpovídat alfanumerickému znaku. Toto porovnání nerozlišuje malá a velká písmena, protože metoda Regex.IsMatch je volána s volbou RegexOptions.IgnoreCase.
[-.\w]* Odpovídá nule, jednomu nebo více výskytům spojovníku, tečky nebo alfanumerického znaku.
[0-9A-Z] Odpovídat alfanumerickému znaku.
([-.\w]*[0-9A-Z])* Odpovídá nule nebo více výskytům posloupnosti tvořené nulou nebo více spojovníky, tečkami nebo slovními znaky, po nichž následuje alfanumerický znak. Toto je první zachytávající skupina.
@ Odpovídá znaku zavináč (@).

Druhý vzor regulárního výrazu ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, používá pozitivní výraz lookbehind. Je definován tak, jak je uvedeno v následující tabulce.

Vzor Popis
^ Zahájí porovnávání na začátku řetězce.
[0-9A-Z] Odpovídat alfanumerickému znaku. Toto porovnání nerozlišuje malá a velká písmena, protože metoda Regex.IsMatch je volána s volbou RegexOptions.IgnoreCase.
[-.\w]* Odpovídá nule nebo více výskytům spojovníku, tečky nebo alfanumerického znaku.
(?<=[0-9A-Z]) Ověří poslední shodující se znak a pokračuje v porovnání, pokud se jedná o znak alfanumerický. Alfanumerické znaky jsou podmnožinou množiny, která sestává z teček, spojovníků a znaků slov.
@ Odpovídá znaku zavináč (@).

Tvrzení dopředného pohledu

.NET obsahuje dva prvky jazyka, (?=dílčí výraz) a (?!dílčí výraz), které odpovídají dalšímu znaku nebo znakům ve vstupním řetězci. Oba jazykové prvky jsou tvrzení nulové šířky; to znamená, že určují, zda lze znak nebo znaky, které bezprostředně následují za aktuálním znakem, porovnat s podvýrazem, aniž by se posouvala aktuální pozice nebo docházelo ke zpětnému prohledávání.

(?= dílčí výraz) je pozitivní prediktivní tvrzení; to znamená, že znak nebo znaky za aktuální pozicí musí odpovídat dílčímu výrazu. (?! dílčí výraz) je záporná predikce dopředu; to znamená, že znak nebo znaky následující za aktuální pozicí nesmí odpovídat dílčímu výrazu. Kladné i záporné aserce lookahead jsou nejužitečnější, když je podvýraz podmnožinou následujícího podvýrazu.

Následující příklad používá dva ekvivalentní vzory regulárních výrazů, které ověřují plně kvalifikovaný název typu. První vzor má nízký výkon kvůli nadměrnému zpětnému prohledávání. Druhý upravuje první regulární výraz tak, že nahradí vnořený kvantifikátor pozitivní dopřednou predikcí. Výstup z příkladu zobrazí čas Regex.IsMatch spuštění metody.

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

První vzor regulárního výrazu , ^(([A-Z]\w*)+\.)*[A-Z]\w*$je definován, jak je znázorněno v následující tabulce.

Vzor Popis
^ Zahájí porovnávání na začátku řetězce.
([A-Z]\w*)+\. Odpovídá písmenu (A-Z), za kterým následuje nula nebo více znaků slova, a to jednou nebo vícekrát, následované tečkou. Toto porovnání nerozlišuje malá a velká písmena, protože metoda Regex.IsMatch je volána s volbou RegexOptions.IgnoreCase.
(([A-Z]\w*)+\.)* Porovná předchozí vzor nulakrát nebo vícekrát.
[A-Z]\w* Porovná abecední znak následovaný žádným nebo několika znaky slova.
$ Ukončí porovnávání na konci vstupního řetězce.

Druhý vzor regulárního výrazu, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, používá pozitivní dopředné tvrzení. Je definován tak, jak je uvedeno v následující tabulce.

Vzor Popis
^ Zahájí porovnávání na začátku řetězce.
(?=[A-Z]) Ověří první znak a pokračuje v porovnávání, pokud se jedná o abecední znak (A-Z). Toto porovnání nerozlišuje malá a velká písmena, protože metoda Regex.IsMatch je volána s možností RegexOptions.IgnoreCase.
\w+\. Porovná jeden nebo více znaků slova následovaných tečkou.
((?=[A-Z])\w+\.)* Porovná vzor jednoho nebo několika znaků slova následovaných tečkou nulakrát nebo vícekrát. Prvním znakem slova musí být abecední znak.
[A-Z]\w* Odpovídá abecednímu znaku následovanému nulou nebo více znaky tvořícími slovo.
$ Ukončí porovnávání na konci vstupního řetězce.

Obecné aspekty výkonu

Následující návrhy nejsou specificky zaměřeny na zabránění nadměrnému zpětnému sledování, ale mohou pomoci zvýšit výkon regulárního výrazu:

  1. Předkompilujte často používané vzory. Nejlepším způsobem, jak to udělat, je použít generátor zdroje regulárních výrazů k předkompilování. Pokud zdrojový generátor není pro vaši aplikaci dostupný, například necílujete na .NET 7 nebo novější nebo neznáte vzor v době kompilace, použijte tuto RegexOptions.Compiled možnost.

  2. Ukládejte často používané objekty Regex do mezipaměti. K tomu implicitně dochází při použití zdrojového generátoru. V opačném případě vytvořte objekt Regex a uložte ho pro opakované použití namísto použití statických metod Regex nebo vytvoření a vyvolání objektu Regex.

  3. Začněte porovnávat od zadaného posunu. Pokud víte, že shody budou vždy začínat až za určitým offsetem ve vzoru, předejte tento offset pomocí přetížení, jako je Regex.Match(String, Int32). Tím se sníží množství textu, který modul potřebuje zvážit.

  4. Shromážděte jenom potřebné informace. Pokud potřebujete vědět pouze to, zda dojde ke shodě, ale nikoli kde k ní dojde, použijte raději Regex.IsMatch. Pokud potřebujete vědět, kolikrát se něco shoduje, raději použijte Regex.Count. Pokud potřebujete znát pouze meze shody, ale nepotřebujete žádné informace o zachycených skupinách shody, je lepší použít Regex.EnumerateMatches. Tím méně informací, které modul potřebuje poskytnout, tím lépe.

  5. Vyhněte se zbytečným záznamům. Závorky ve vašem vzoru ve výchozím nastavení představují zachytávací skupinu. Pokud zachytávání nepotřebujete, zadejte RegexOptions.ExplicitCapture nebo místo toho použijte nezachytávací skupiny. Tím odpadá nutnost, aby engine sledoval tyto zachycené skupiny.

Viz také

  • Last updated on