Navracení 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. 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í.
Upozorňující
Při zpracování System.Text.RegularExpressions nedůvěryhodného vstupu předejte vypršení časového limitu. Uživatel se zlými úmysly může poskytnout vstup RegularExpressions, což způsobí útok na dostupnost služby. ASP.NET rozhraní API architektury Core, která používají RegularExpressions vypršení časového limitu.
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. 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 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("{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 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 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 |
|---|---|---|---|
| 0 | 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 | "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 konstruktorů 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ů s nedeterministickým modulem finite Automaton (NFA) je řízen elementy jazyka v regulárním výrazu, a ne znaky, které se mají spárovat 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é 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("'{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 expressions 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 expressions 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.
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. 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 operace shody trvá.
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 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ích pěti znaků 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 svých shod "a" (které zavoláme 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ří. 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ří. Pak se vrátí ke shodě 3 a pokusí se spárovat dva další znaky "a" ve dvou dalších zachycených skupinách. 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. 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 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 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. Rozhraní .NET navíc podporuje tři prvky jazyka regulárních výrazů, které omezují nebo potlačí navracení a podporují složité 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ů.
Modul regulárních výrazů bez navracení
Pokud nepotřebujete používat žádné konstrukce, které vyžadují navracení (například lookarounds, backreference nebo atomické skupiny), zvažte použití RegexOptions.NonBacktracking režimu. 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 jsou všechny rozumné textové vstupy ve vašem scénáři známé jako pod určitou délkou, zvažte odmítnutí delších vstupů před použitím regulárního výrazu na ně.
Zadání intervalu časového limitu
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ž tento 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. 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 to být jakákoli 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é TimeSpan vyjádření hodnoty 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 časový limit nastavený na Regex.InfiniteMatchTimeout hodnotu a modul regulárních výrazů nevysadí časový limit.
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é navracení, ale je také možné, že interval časového limitu byl nastaven příliš nízký vzhledem k zatížení systému v době, kdy byla výjimka vyvolán. 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 objektu Regex s hodnotou časového limitu 1 sekundy. Vzor (a+)+$regulárního výrazu, 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 3 sekundy. 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 subexpression) je atomické seskupení. Zabraňuje zpětnému navracení do dílčího výrazu. Jakmile se tento prvek jazyka úspěšně spáruje, nevzdá žádnou část shody s následným navracením. Například v vzoru (?>\w*\d*)1, pokud 1 nelze spárovat, \d* nebude se vzdát žádné z jeho shody, i když to znamená, že by to umožnilo 1 úspěšné shody. 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 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: {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.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 prvky jazyka jsou kontrolní výrazy nulové šířky; to znamená, že určují, zda se znak nebo znaky, které bezprostředně před aktuálním znakem, mohou shodovat dílčím výrazem bez postupu nebo zpětného navracení.
(?<=subexpression) je pozitivní výraz lookbehind; to znamená, že znak nebo znaky před aktuální pozicí musí odpovídat dílčímu výrazu. (?<!subexpression) 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ší, pokud je podvý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 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: {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 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] |
Porovná alfanumerický znak. Toto porovnání nerozlišuje malá a velká písmena, protože Regex.IsMatch metoda je volána 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 se znakem at (@). |
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] |
Porovná alfanumerický znak. Toto porovnání nerozlišuje malá a velká písmena, protože Regex.IsMatch metoda je volána 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 se znakem at (@). |
Kontrolní výrazy lookahead
.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 prvky jazyka jsou kontrolní výrazy nulové šířky; to znamená, že určují, zda se znak nebo znaky, které bezprostředně následují za aktuálním znakem, mohou shodovat dílčím výrazem, bez postupu nebo zpětného navracení.
(?=dílčí výraz) je kontrolní výraz pozitivního vzhledu. To znamená, že znak nebo znaky za aktuální pozicí musí odpovídat dílčímu výrazu. (?!subexpression) je záporný kontrolní výraz pro vyhledávání; 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ší, pokud je podvýraz podmnožinou 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 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("{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.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*)+\. |
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í nerozlišuje malá a velká písmena, protože Regex.IsMatch metoda je volána 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í kontrolní výraz lookahead. 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 Regex.IsMatch metoda je volána 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. |
Obecné aspekty výkonu
Následující návrhy nejsou výslovně určené k tomu, aby se zabránilo nadměrnému navracení, ale může pomoct zvýšit výkon regulárního výrazu:
Předkompilní silně 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.
Do mezipaměti se silně používaly objekty Regex. 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.
Začněte porovnávat od posunu. Pokud víte, že shody budou vždy začínat nad rámec určitého posunu do vzoru, předat posun při použití přetížení, jako je Regex.Match(String, Int32). Tím se sníží množství textu, který modul potřebuje zvážit.
Shromážděte jenom potřebné informace. Pokud potřebujete vědět, zda se shoda vyskytuje, ale ne tam, kde se shoda vyskytuje, preferujte 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 hranice shody, ale ne nic o zachycení shody, raději použijte Regex.EnumerateMatches. Tím méně informací, které modul potřebuje poskytnout, tím lépe.
Vyhněte se zbytečným zachycením. Závorky ve vašem vzoru ve výchozím nastavení tvoří zachytávání skupiny. Pokud nepotřebujete zachytávání, zadejte RegexOptions.ExplicitCapture nebo použijte skupiny, které se nezachytí. Tím se motor zachová v přehledu o těchto zachyceních.
Viz také
Váš názor
Připravujeme: V průběhu roku 2024 budeme postupně vyřazovat problémy z GitHub coby mechanismus zpětné vazby pro obsah a nahrazovat ho novým systémem zpětné vazby. Další informace naleznete v tématu: https://aka.ms/ContentUserFeedback.
Odeslat a zobrazit názory pro