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

Zpětné sledování nastane, když vzor regulárního výrazu obsahuje volitelné kvantifikátory nebo konstruktor alternace a modul regulárních výrazů se vrátí do předchozího uloženého stavu, aby pokračoval v hledání shody. Navracení má klíčový význam pro výkon regulárních výrazů, což umožňuje, aby výrazy byly výkonné a pružné a aby vyhovovaly velmi složitým vzorům. Tento výkon však zároveň něco stojí. Navracení je často jediným nejdůležitějším faktorem, který ovlivňuje výkon modulu regulárních výrazů. Vývojář má naštěstí vliv na chování modulu regulárních výrazů a způsob používání mechanismu navracení. V tomto tématu je vysvětleno fungování a ovládání mechanismu navracení.

Poznámka

Obecně platí, že nedeterministický stroj Finite Automaton (NFA), jako je modul regulárních výrazů .NET, zodpovídá za vytváření efektivních a rychlých regulárních výrazů pro vývojáře.

Lineární porovnání bez mechanismu 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. Tento postup se opakuje, dokud je shoda buď úspěšná, anebo neúspěšná. V obou případech se modul regulárních výrazů posune vždy o jeden znak ve vstupním řetězci.

V následujícím příkladu je uvedena ukázka. Regulární výraz e{2}\w\b vyhledá 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 Example
{
   public static void Main()
   {
      string input = "needing a reed";
      string pattern = @"e{2}\w\b";
      foreach (Match match in Regex.Matches(input, pattern))
         Console.WriteLine("{0} found at position {1}",
                           match.Value, match.Index);
   }
}
// The example displays the following output:
//       eed found at position 11
Imports System.Text.RegularExpressions

Module Example
    Public Sub Main()
        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ý kvantifikátor. 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 regulárních výrazů pokusí shodovat se vzorem regulárního výrazu se vstupním řetězcem, jak je znázorněno v následující tabulce.

Operace Pozice ve vzoru Pozice v řetězci Výsledek
1 e "needing a reed" (index 0) Žádná shoda.
2 e "eeding a reed" (index 1) Možná shoda.
3 E{2} "eding a reed" (index 2) Možná shoda.
4 \w "ding a reed" (index 3) Možná shoda.
5 \b "ing a reed" (index 4) Možná shoda se nezdaří.
6 e "eding a reed" (index 2) Možná shoda.
7 E{2} "ding a reed" (index 3) Možná shoda se nezdaří.
8 e "ding a reed" (index 3) Shoda se nezdaří.
9 e "ing a reed" (index 4) Žádná shoda.
10 e "ng a reed" (index 5) Žádná shoda.
11 e "g a reed" (index 6) Žádná shoda.
12 e " a reed" (index 7) Žádná shoda.
13 e "a reed" (index 8) Žádná shoda.
14 e " reed" (index 9) Žá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.

Navracení pomocí volitelných kvantifikátorů nebo konstrukcí alternace

Pokud regulární výraz zahrnuje volitelné kvantifikátory nebo alternace konstrukce, hodnocení vstupního řetězce již není lineární. Porovnání vzorů s modulem NFA řídí prvky jazyka v regulárním výrazu, nikoli znaky, které se musí shodovat 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 předchozímu stavu pro vyhledání shody se označuje jako navracení.

Představte si například vzor .*(es)regulárního výrazu, který odpovídá znakům "es" a všem znakům, které mu 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 Example
{
   public static void Main()
   {
      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("'{0}' found at position {1}",
                           m.Value, m.Index);
         Console.WriteLine("'es' found at position {0}",
                           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 Example
    Public Sub Main()
        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

Chcete-li provést tuto akci, používá modul regulárních výrazů mechanismus navracení takto:

  • Odpovídá hodnotě .* (která odpovídá nule, jednomu nebo více výskytům libovolného znaku) s celým vstupním řetězcem.

  • Pokusí se najít shodu pro písmeno „e“ ve vzoru regulárního výrazu. Vstupní řetězec však nemá žádné odpovídající zbývající znaky.

  • 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“). Tato shoda je úspěšná.

Pokud použijete mechanismus navracení, vyžaduje shoda vzoru regulárního výrazu se vstupním řetězcem, který má 55 znaků, celkem 67 operací porovnání. 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.

Mechanismus navracení 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. Například vzor ^(a+)+$ regulárního výrazu je 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 se používá k určení doby trvání operace shody.

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

public class Example
{
   public static void Main()
   {
      string pattern = "^(a+)+$";
      string[] inputs = { "aaaaaa", "aaaaa!" };
      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 {0} in {1}", match.Value, sw.Elapsed);
         else
            Console.WriteLine("No match found in {0}", sw.Elapsed);
      }
   }
}
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
    Public Sub Main()
        Dim pattern As String = "^(a+)+$"
        Dim inputs() As String = {"aaaaaa", "aaaaa!"}
        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

Jak výstup v příkladu znázorňuje, trvalo modulu regulárních výrazů ve srovnání s délkou trvání identifikace odpovídajícího řetězce dvakrát tak dlouho, než vyhledal, že vstupní řetězec neodpovídá vzoru. Je to proto, že neúspěšná shoda vždy představuje nejhorší případ. Modul regulárních výrazů musí prohledat všechny možné cesty dat předtím, než dojde k závěru, že shoda je neúspěšná, a vnořené závorky vytvoří velký počet dodatečných cest napříč daty. Modul regulárních výrazů dojde k závěru, že druhý řetězec neodpovídá vzoru následujícím způsobem:

  • Zkontroluje, že byl na začátku řetězce, a pak odpovídá prvním pěti znakům v řetězci 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 regulárních výrazů také ukládá informace o stavu ze shody „a“ (který budeme nazývat shoda 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ří. Tato neúspěšná shoda vyžaduje 4 porovnání. Zatím bylo provedeno celkem 13 porovnání.

  • Vrátí se do dříve uložené shody 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ří. Poté se vrátí ke shodě 3 a pokusí se porovnat další dva znaky „a“ v dodatečné zachycené skupině. Test konce řetězce se však ani tentokrát nezdaří. Tyto nezdařené 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. Vzhledem k vnořeným kvantifikátorům 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.

Řídicí mechanismus navracení

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, kdy vytvoříte instanci objektu Regex nebo zavoláte metodu 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 elementy jazyka regulárních výrazů, které omezují nebo potlačují zpětné navracení a podporují komplexní regulární výrazy s minimálním nebo žádným trestem výkonu: atomické skupiny, kontrolní výrazy lookbehind a kontrolní výrazy lookahead. Další informace o jednotlivých elementech jazyka naleznete v tématu Seskupování konstruktorů.

Definování intervalu časového limitu

Počínaje rozhraním .NET Framework 4.5 můžete nastavit hodnotu časového limitu, která představuje nejdelší interval, který modul regulárních výrazů vyhledá jednu shodu předtím, než pokus opustí a vyvolá RegexMatchTimeoutException výjimku. Časový limit zadáte zadáním TimeSpan hodnoty konstruktoru Regex(String, RegexOptions, TimeSpan) pro regulární výrazy instance. Každá metoda porovnávání statických vzorů má navíc přetížení s parametrem TimeSpan , 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 hodnota časového limitu pro celou aplikaci, použijte ji. To může být libovolná hodnota časového limitu, která se vztahuje na doménu aplikace, ve které Regex je objekt instance, nebo se provede volání statické metody. Hodnotu časového limitu pro celou aplikaci můžete nastavit voláním AppDomain.SetData metody, která přiřadí řetězcové vyjádření TimeSpan hodnoty vlastnosti "REGEX_DEFAULT_MATCH_TIMEOUT".

  • Pokud nebyla nastavena žádná hodnota časového limitu InfiniteMatchTimeoutpro celou aplikaci, použijte ji.

Ve výchozím nastavení je časový limit nastavený na Regex.InfiniteMatchTimeout hodnotu a modul regulárních výrazů nevysadí časový limit.

Důležité

Pokud se regulární výraz spoléhá na mechanismus navracení, doporučujeme vždy nastavit interval časového limitu.

Výjimka RegexMatchTimeoutException značí, že modul regulárních výrazů nemohl najít shodu v zadaném intervalu časového limitu, ale nezjisťuje, proč došlo k výjimce. Důvodem může být nadměrné používání mechanismu navracení, je však také možné, že nastavený interval časového limitu byl příliš krátký vzhledem k zatížení systému v době vyvolání výjimky. Při zpracování výjimek můžete zrušit další shody se vstupním řetězcem nebo zvýšit interval časového limitu a opakovat operaci porovnání.

Například následující kód volá Regex(String, RegexOptions, TimeSpan) konstruktor pro vytvoření instance Regex objektu s hodnotou časového limitu jedné sekundy. Vzor regulárního výrazu (a+)+$, který odpovídá jedné nebo více sekvencí jednoho nebo více znaků "a" na konci řádku, podléhá nadměrnému navracení. RegexMatchTimeoutException Pokud je vyvolán, příklad zvýší hodnotu časového limitu až na maximální interval tří sekund. Poté zruší pokus 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 {0}", 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 {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;
                    }
                }
            } 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

Element (?> jazyka dílčího) výrazu potlačuje zpětné navracení do dílčího výrazu. Jakmile se úspěšně spáruje, neudělí žádnou část své shody dalšímu navracení. Například v modelu (?>\w*\d*)1, pokud 1 nelze spárovat, \d* se žádná z jeho shody neudělí, i když to znamená, že by to umožnilo 1 úspěšné shodování. 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á mechanismus navracení k tomu, aby se pokusil porovnat řetězec, který obsahuje jeden výskyt nebo několik výskytů jedné nebo několika šestnáctkových číslic následovaných dvojtečkou, následovaných jednou nebo několika šestnáctkovými číslicemi, následovaných dvěma dvojtečkami. Druhý regulární výraz je shodný s prvním výrazem, s výjimkou toho, že zakáže mechanismus navracení. 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 Example
{
   public static void Main()
   {
      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: {0} in {1}", Regex.IsMatch(input, backPattern), 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: {0} in {1}", Regex.IsMatch(input, noBackPattern), 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.Diagnostics
Imports System.Text.RegularExpressions

Module Example
    Public Sub Main()
        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 zpětného vyhledávání

.NET obsahuje dva jazykové elementy, (?<=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 prvky jazyka jsou kontrolní výrazy nulové šířky; to znamená, že určují, zda znak nebo znaky, které bezprostředně předchází aktuálnímu znaku, mohou být spárovány dílčím výrazem, aniž by se postupovaly nebo vrátily zpět.

(?<=Podvýraz) je pozitivní výraz lookbehind; to znamená, že znak nebo znaky před aktuální pozicí musí odpovídat dílčímu výrazu. (?<!Podvýraz) je negativní výraz lookbehind; to znamená, že znak nebo znaky před aktuální pozicí nesmí odpovídat dílčímu výrazu. Pozitivní i negativní kontrolní výrazy lookbehind jsou nejužitečnější, když je dílčí výraz podmnožinou předchozího dílčího vý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 je ovlivněn nízkým výkonem z důvodu nadměrného používání mechanismu navracení. Druhý vzor upraví první regulární výraz nahrazením vnořeného kvantifikátoru kontrolním výrazem pozitivního zpětného vyhledávání. Výstup z příkladu zobrazuje čas Regex.IsMatch spuštění metody.

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

public class Example
{
   public static void Main()
   {
      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: {0} in {1}", result, 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: {0} in {1}", result, 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 Example
    Public Sub Main()
        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 Description
^ Zahájí porovnávání na začátku řetězce.
[0-9A-Z] Porovná alfanumerický znak. Toto porovnání je nerozlišující malá a velká písmena, protože Regex.IsMatch metoda se volá s RegexOptions.IgnoreCase možností.
[-.\w]* Porovná žádný či jeden výskyt nebo několik výskytů spojovníku, tečky nebo znaku slova.
[0-9A-Z] Porovná alfanumerický znak.
([-.\w]*[0-9A-Z])* Porovná žádný výskyt nebo několik výskytů kombinace nuly nebo několika spojovníků, teček či znaků slova, následovaných alfanumerickým znakem. Toto je první zachytávající skupina.
@ Shoda znaku at (@).

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

Vzor Description
^ Zahájí porovnávání na začátku řetězce.
[0-9A-Z] Porovná alfanumerický znak. Toto porovnání je nerozlišující malá a velká písmena, protože Regex.IsMatch metoda se volá s RegexOptions.IgnoreCase možností.
[-.\w]* Porovná žádný výskyt nebo několik výskytů spojovníku, tečky nebo znaku slova.
(?<=[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.
@ Shoda znaku at (@).

Kontrolní výrazy dopředného vyhledávání

.NET obsahuje dva jazykové elementy, (?=subexpression a (?!subexpression)), které odpovídají dalšímu znaku nebo znakům ve vstupním řetězci. Oba prvky jazyka jsou kontrolní výrazy nulové šířky; to znamená, že určují, jestli se znak nebo znaky, které bezprostředně následují po aktuálním znaku, dají spárovat dílčím výrazem, aniž by bylo možné pokračovat nebo vrátit zpět.

(?=Podvýraz) je pozitivní kontrolní výraz; to znamená, že znak nebo znaky za aktuální pozicí musí odpovídat dílčímu výrazu. (?!Podvýraz) je negativní kontrolní výraz; to znamená, že znak nebo znaky za aktuální pozicí nesmí odpovídat dílčímu výrazu. Pozitivní i negativní kontrolní výrazy lookahead jsou nejužitečnější, když podvýraz je podmnožina dalšího dílčího vý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 je ovlivněn nízkým výkonem z důvodu nadměrného používání mechanismu navracení. Druhý vzor upraví první regulární výraz nahrazením vnořeného kvantifikátoru kontrolním výrazem pozitivního dopředného vyhledávání. Výstup z příkladu zobrazuje čas Regex.IsMatch spuštění metody.

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

public class Example
{
   public static void Main()
   {
      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("{0} in {1}", result, sw.Elapsed);

      string aheadPattern = @"^((?=[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);
   }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
    Public Sub Main()
        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 Description
^ Zahájí porovnávání na začátku řetězce.
([A-Z]\w*)+\. Porovná abecední znak (A-Z) následovaný žádným nebo několika znaky slova jednou nebo vícekrát, následovaných tečkou. Toto porovnání je nerozlišující malá a velká písmena, protože Regex.IsMatch metoda se volá s RegexOptions.IgnoreCase možností.
(([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í výraz lookahead. Je definován tak, jak je uvedeno v následující tabulce.

Vzor Description
^ 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í je nerozlišující malá a velká písmena, protože Regex.IsMatch metoda se volá s RegexOptions.IgnoreCase možností.
\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* Porovná abecední znak následovaný žádným nebo několika znaky slova.
$ Ukončí porovnávání na konci vstupního řetězce.

Viz také