Wycofywanie w wyrażeniach regularnych
Wycofywanie występuje, gdy wzorzec wyrażenia regularnego zawiera opcjonalne kwantyfikatory lub konstrukcje zmiany, a aparat wyrażeń regularnych powraca do poprzedniego zapisanego stanu, aby kontynuować wyszukiwanie dopasowania. Wycofywanie stanowi podstawę dużych możliwości wyrażeń regularnych, ponieważ dzięki niemu wyrażenia oferują duże możliwości i są elastyczne, a także umożliwiają dopasowywanie bardzo złożonych wzorców. Jednocześnie te możliwości są obciążone kosztami. Wycofywanie często jest najważniejszym czynnikiem wpływającym na wydajność aparatu wyrażeń regularnych. Na szczęście deweloper ma kontrolę nad zachowaniem aparatu wyrażeń regularnych i sposobem użycia wycofywania. W tym artykule wyjaśniono, jak działa wycofywanie i jak można go kontrolować.
Ostrzeżenie
W przypadku używania System.Text.RegularExpressions metody do przetwarzania niezaufanych danych wejściowych należy przekazać limit czasu. Złośliwy użytkownik może przekazać dane wejściowe , RegularExpressionspowodując atak typu "odmowa usługi". ASP.NET podstawowe interfejsy API platformy, które używają RegularExpressions przekroczenia limitu czasu.
Porównanie liniowe bez wycofywania
Jeśli wzorzec wyrażenia regularnego nie ma opcjonalnych kwantyfikatorów ani konstrukcji zmiany, aparat wyrażeń regularnych wykonuje go liniowo. Oznacza to, że gdy aparat wyrażeń regularnych znajdzie pierwszy element języka ze wzorca w tekście w ciągu wejściowym, próbuje dopasować następny element języka ze wzorca do następnego znaku lub grupy znaków w ciągu wejściowym. Ten proces jest kontynuowany do czasu, aż dopasowywanie zakończy się pomyślnie lub niepomyślnie. W każdym przypadku aparat wyrażeń regularnych przesuwa się w danej chwili o jeden znak do przodu w ciągu wejściowym.
Poniższy przykład stanowi ilustrację. Wyrażenie e{2}\w\b regularne wyszukuje dwa wystąpienia litery "e", po którym następuje dowolny znak słowa, po którym następuje granica słowa.
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
Mimo że to wyrażenie regularne zawiera kwantyfikator {2}, jest obliczane liniowo. Aparat wyrażeń regularnych nie jest wycofywaniem, ponieważ {2} nie jest opcjonalnym kwantyfikatorem; określa dokładną liczbę, a nie zmienną liczbę razy, w których poprzednie wyrażenie podrzędne musi być zgodne. W wyniku tego aparat wyrażeń regularnych próbuje dopasować wzorzec wyrażenia regularnego do ciągu wejściowego, tak jak pokazano w poniższej tabeli.
| Operacja | Pozycja we wzorcu | Pozycja w ciągu | Wynik |
|---|---|---|---|
| 1 | e | „needing a reed” (indeks 0) | Brak dopasowania. |
| 2 | e | „eeding a reed” (indeks 1) | Możliwe dopasowanie. |
| 3 | e{2} | „eding a reed” (indeks 2) | Możliwe dopasowanie. |
| 100 | \w | „ding a reed” (indeks 3) | Możliwe dopasowanie. |
| 5 | \b | „ing a reed” (indeks 4) | Możliwe dopasowanie nie powiodło się. |
| 6 | e | „eding a reed” (indeks 2) | Możliwe dopasowanie. |
| 7 | e{2} | „ding a reed” (indeks 3) | Możliwe dopasowanie nie powiodło się. |
| 8 | e | „ding a reed” (indeks 3) | Dopasowanie nie powiodło się. |
| 9 | e | „ing a reed” (indeks 4) | Brak dopasowania. |
| 10 | e | „ng a reed” (indeks 5) | Brak dopasowania. |
| 11 | e | „g a reed” (indeks 6) | Brak dopasowania. |
| 12 | e | " reed" (indeks 7) | Brak dopasowania. |
| 13 | e | "reed" (indeks 8) | Brak dopasowania. |
| 14 | e | "reed" (indeks 9) | Brak dopasowania. |
| 15 | e | "reed" (indeks 10) | Brak dopasowania. |
| 16 | e | „eed” (indeks 11) | Możliwe dopasowanie. |
| 17 | e{2} | „ed” (indeks 12) | Możliwe dopasowanie. |
| 18 | \w | „d” (indeks 13) | Możliwe dopasowanie. |
| 19 | \b | „” (indeks 14) | Dopasowanie. |
Jeśli wzorzec wyrażenia regularnego nie zawiera opcjonalnych kwantyfikatorów ani konstrukcji zmiany, maksymalna liczba porównań niezbędna do wykonania dopasowania wzorca wyrażenia regularnego do ciągu wejściowego jest w przybliżeniu równa liczbie znaków w ciągu wejściowym. W tym przypadku aparat wyrażeń regularnych wykonuje 19 porównań w celu zidentyfikowania możliwych dopasowań w 13-znakowy ciągu. Innymi słowy, aparat wyrażeń regularnych działa prawie liniowo, jeśli nie zawiera opcjonalnych kwantyfikatorów ani konstrukcji zmiany.
Wycofywanie z opcjonalnymi kwantyfikatory lub konstrukcjami zmiany
Gdy wyrażenie regularne zawiera opcjonalne kwantyfikatory lub konstrukcje zmiany, obliczenia wykonywane na ciągu wejściowym nie są już liniowe. Dopasowanie wzorca z aparatem Finite Automaton (NFA) nondeterministic jest sterowane przez elementy języka w wyrażeniu regularnym, a nie przez znaki, które mają być dopasowane w ciągu wejściowym. Dlatego aparat wyrażeń regularnych próbuje w pełni dopasować opcjonalne lub alternatywne podwyrażenia. Kiedy aparat wyrażeń regularnych przechodzi do następnego elementu języka w podwyrażeniu i wykonanie dopasowania nie jest możliwe, może porzucić część pomyślnie wykonanego dopasowania i powrócić do wcześniejszego zapisanego stanu dopasowywania wyrażenia regularnego jako całości w ciągu wejściowym. Ten proces wracania do poprzednio zapisanego stanu w celu znalezienia dopasowania jest nazywany wycofywaniem.
Rozważmy na przykład wzorzec .*(es)wyrażenia regularnego, który odpowiada znakom "es" i wszystkim znakom poprzedzającym go. W poniższym przykładzie pokazano, że jeśli ciągiem wejściowym jest ciąg „Essential services are provided by regular expressions.”, wzorzec dopasowuje cały ciąg aż do znaków „es” w wyrazie „expressions” włącznie.
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
W tym celu aparat wyrażeń regularnych używa wycofywania, tak jak opisano poniżej:
Pasuje do wartości
.*(która pasuje do zera, jednego lub większej liczby wystąpień dowolnego znaku) z całym ciągiem wejściowym.Podejmuje próbę dopasowania znaku „e” we wzorcu wyrażenia regularnego. Jednak ciąg wejściowy nie zawiera już znaków, z którymi można by wykonać porównanie.
Aparat wycofuje się więc do ostatniego pomyślnego dopasowania (Essential services are provided by regular expressions) i podejmuje próbę dopasowania litery „e” do kropki na końcu zdania. Nie można utworzyć takiego dopasowania.
Aparat kontynuuje wycofywanie do poprzedniego pomyślnego dopasowania po jednym znaku, aż wykryje, że pasującym podciągiem jest „Essential services are provided by regular expr”. Następnie porównuje znak „e” we wzorcu z drugą literą „e” w wyrazie „expressions” i znajduje dopasowanie.
Porównuje znak „s” we wzorcu z literą „s” występującą po dopasowanym znaku „e” (pierwsza litera „s” w wyrazie „expressions”). Dopasowanie jest wykonywane pomyślnie.
Gdy jest używane wycofywanie, wykonanie dopasowania wzorca wyrażenia regularnego do ciągu wejściowego składającego się z 55 znaków wymaga wykonania 67 operacji porównania. Ogólnie, jeśli wzorzec wyrażenia regularnego zawiera jedną konstrukcję zmiany lub jeden opcjonalny kwantyfikator, liczba operacji porównania wymaganych do wykonania dopasowania wzorca jest ponad dwa razy większa niż liczba znaków w ciągu wejściowym.
Wycofywanie z zagnieżdżonych opcjonalnych kwantyfikatorów
Liczba operacji porównania wymaganych do wykonania dopasowania wzorca wyrażenia regularnego rośnie wykładniczo, gdy wzorzec zawiera dużą liczbę konstrukcji zmiany, jeśli zawiera zagnieżdżone konstrukcje zmiany lub, co występuje najczęściej, zawiera zagnieżdżone kwantyfikatory opcjonalne. Na przykład wzorzec ^(a+)+$ wyrażenia regularnego jest przeznaczony do dopasowania kompletnego ciągu zawierającego co najmniej jeden znak "a". W przykładzie podano dwa ciągi wejściowe o identycznej długości, ale tylko pierwszy ciąg pasuje do wzorca. Klasa System.Diagnostics.Stopwatch służy do określania, jak długo trwa operacja dopasowania.
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 pokazano w danych wyjściowych z przykładu, aparat wyrażeń regularnych trwał znacznie dłużej, aby stwierdzić, że ciąg wejściowy nie jest zgodny ze wzorcem, tak jak w przypadku identyfikowania pasującego ciągu. Jest to spowodowane tym, że niepowodzenie tworzenia dopasowania zawsze jest scenariuszem najgorszego przypadku. Aparat wyrażeń regularnych musi użyć wyrażenia regularnego, aby sprawdzić wszystkie możliwe ścieżki w danych, zanim będzie mógł uznać, że nie można wykonać dopasowania, a zagnieżdżone nawiasy powodują powstanie wielu dodatkowych ścieżek w danych. Aparat wyrażeń regularnych dochodzi do wniosku, że drugi ciąg nie pasuje do wzorca, wykonując następujące czynności:
Sprawdza, czy był na początku ciągu, a następnie pasuje do pierwszych pięciu znaków w ciągu ze wzorcem
a+. Następnie ustala, że w ciągu nie znajdują się dodatkowe grupy liter „a”. Na końcu sprawdza, czy znajduje się na końcu ciągu. W ciągu pozostał jeden dodatkowy znak, więc wykonywanie dopasowania kończy się niepowodzeniem. To nieudane dopasowanie wymaga wykonania 9 porównań. Aparat wyrażeń regularnych zapisuje również informacje o stanie z dopasowań "a" (które wywołamy dopasowanie 1), "aa" (dopasowanie 2), "aaa" (dopasowanie 3) i "aaaa" (dopasowanie 4).Aparat powraca do uprzednio zapisanego dopasowania 4. Ustala, że istnieje jeden dodatkowy znak „a”, który można przypisać do dodatkowej przechwyconej grupy. Na końcu sprawdza, czy znajduje się na końcu ciągu. W ciągu pozostał jeden dodatkowy znak, więc wykonywanie dopasowania kończy się niepowodzeniem. To dopasowanie nie powiodło się wymaga 4 porównań. Do tego momentu zostało wykonanych 13 porównań.
Powróci do wcześniej zapisanego dopasowania 3. Ustala, że istnieją dwa dodatkowe znaki „a”, które można przypisać do dodatkowej przechwyconej grupy. Jednak test końca ciągu kończy się niepowodzeniem. Następnie powraca do dopasowania 3 i próbuje dopasować dwa dodatkowe znaki "a" w dwóch dodatkowych przechwyconych grupach. Test końca ciągu nadal kończy się niepowodzeniem. Te nieudane dopasowania wymagały wykonania 12 porównań. Do tej pory wykonano łącznie 25 porównań.
Porównywanie ciągu wejściowego z wyrażeniem regularnym w ten sposób będzie kontynuowane, dopóki aparat wyrażeń regularnych nie wypróbuje wszystkich możliwych kombinacji dopasowań, a następnie uzna, że nie istnieje dopasowanie. Ze względu na zagnieżdżone kwantyfikatory, to porównanie jest operacją O(2n) lub operacją wykładniczą, gdzie n jest liczbą znaków w ciągu wejściowym. Oznacza to, że w najgorszym przypadku ciąg wejściowy o długości 30 znaków będzie wymagał wykonania ok. 1 073 741 824 porównań, a ciąg wejściowy o długości 40 znaków będzie wymagał wykonania ok. 1 099 511 627 776 porównań. Gdy są używane ciągi o takiej lub większej długości, wykonanie metod opartych na wyrażeniach regularnych może trwać niezwykle długo, jeśli w przetwarzanych ciągach nie będą znajdować się dopasowania do wzorca wyrażenia regularnego.
Kontrolowanie wycofywania
Wycofywanie umożliwia tworzenie zaawansowanych, elastycznych wyrażeń regularnych. Jednak, tak jak pokazano w poprzedniej sekcji, ich zalety może przesłonić nieakceptowalnie niska wydajność. Aby zapobiec nadmiernemu wycofywaniu, należy zdefiniować interwał limitu czasu podczas tworzenia wystąpienia Regex obiektu lub wywoływania statycznej metody dopasowywania wyrażeń regularnych. Ta czynność została omówiona w następnej sekcji. Ponadto platforma .NET obsługuje trzy elementy języka wyrażeń regularnych, które ograniczają lub pomijają wycofywanie i obsługują złożone wyrażenia regularne z małą karą dla wydajności lub bez kar za wydajność: grupy atomowe, asercje lookbehind i asercje lookahead. Aby uzyskać więcej informacji na temat każdego elementu języka, zobacz Konstrukcje grupowania.
Aparat wyrażeń regularnych bez wycofywania
Jeśli nie musisz używać żadnych konstrukcji, które wymagają wycofywania (na przykład lookarounds, backreferences lub grup niepodzielnych), rozważ użycie RegexOptions.NonBacktracking trybu . Ten tryb jest przeznaczony do wykonywania w czasie proporcjonalnym do długości danych wejściowych. Aby uzyskać więcej informacji, zobacz Tryb nonBacktracking. Można również ustawić wartość limitu czasu.
Ograniczanie rozmiaru danych wejściowych
Niektóre wyrażenia regularne mają akceptowalną wydajność, chyba że dane wejściowe są wyjątkowo duże. Jeśli wszystkie rozsądne dane wejściowe tekstu w scenariuszu są znane jako o określonej długości, rozważ odrzucenie dłuższych danych wejściowych przed zastosowaniem wyrażenia regularnego.
Określanie interwału limitu czasu
Możesz ustawić wartość limitu czasu reprezentującą najdłuższy interwał wyszukiwarki wyrażeń regularnych, zanim porzuci próbę i zgłosi RegexMatchTimeoutException wyjątek. Interwał limitu czasu określa się, podając TimeSpan wartość konstruktorowi Regex(String, RegexOptions, TimeSpan) dla wystąpień wyrażeń regularnych. Ponadto każda metoda dopasowania wzorca statycznego ma przeciążenie z parametrem TimeSpan , który umożliwia określenie wartości limitu czasu.
Jeśli jawnie nie ustawisz wartości limitu czasu, domyślna wartość limitu czasu zostanie określona w następujący sposób:
- Używając wartości limitu czasu dla całej aplikacji, jeśli istnieje. Może to być dowolna wartość limitu czasu, która ma zastosowanie do domeny aplikacji, w której Regex jest tworzone wystąpienie obiektu lub jest wykonywane wywołanie metody statycznej. Możesz ustawić wartość limitu czasu dla całej aplikacji, wywołując AppDomain.SetData metodę w celu przypisania reprezentacji TimeSpan ciągu wartości do
REGEX_DEFAULT_MATCH_TIMEOUTwłaściwości. - Używając wartości InfiniteMatchTimeout, jeśli nie ustawiono wartości limitu czasu dla całej aplikacji.
Domyślnie interwał limitu czasu jest ustawiony na Regex.InfiniteMatchTimeout wartość , a aparat wyrażeń regularnych nie przekracza limitu czasu.
Ważne
Jeśli nie używasz RegexOptions.NonBacktrackingmetody , zalecamy, aby zawsze ustawiać interwał limitu czasu, jeśli wyrażenie regularne opiera się na wycofywaniu lub działa na niezaufanych danych wejściowych.
Wyjątek RegexMatchTimeoutException wskazuje, że aparat wyrażeń regularnych nie może odnaleźć dopasowania w określonym interwale limitu czasu, ale nie wskazuje, dlaczego wyjątek został zgłoszony. Przyczyną może być nadmierne wycofywanie, ale jest również możliwe, że interwał przekroczenia limitu czasu został ustawiony zbyt nisko, biorąc pod uwagę obciążenie systemu w momencie zgłoszenia wyjątku. Podczas obsługi tego wyjątku można określić, że nie mają być wykonywane kolejne porównania z ciągiem wejściowym, albo zwiększyć interwał limitu czasu i ponowić próbę wykonania operacji dopasowywania.
Na przykład poniższy kod wywołuje konstruktor, Regex(String, RegexOptions, TimeSpan) aby utworzyć Regex wystąpienie obiektu z wartością limitu czasu 1 sekundy. Wzorzec (a+)+$wyrażenia regularnego, który pasuje do co najmniej jednej sekwencji co najmniej jednego znaku "a" na końcu wiersza, podlega nadmiernemu wycofywaniu. Jeśli element RegexMatchTimeoutException zostanie zgłoszony, przykład zwiększy wartość limitu czasu do maksymalnego interwału wynoszącego 3 sekundy. Po upływie tego czasu nie będą już podejmowane próby dopasowania wzorca.
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.
Grupy niepodzielne
Element (?>języka podwyrażenia) to grupowanie niepodzielne. Zapobiega to wycofywaniu wycofywania w podrażeniu. Po pomyślnym dopasowaniu tego elementu języka nie podda się żadnej części dopasowania do kolejnych wycofywania. Na przykład w wzorcu (?>\w*\d*)1, jeśli 1 nie można dopasować elementu , element nie podda żadnego dopasowania, \d* nawet jeśli oznacza to, że pozwoli to na 1 pomyślne dopasowanie. Grupy niepodzielne mogą pomóc w zapobieganiu problemom z wydajnością skojarzonymi z nieudanymi dopasowaniami.
W poniższym przykładzie pokazano, w jaki sposób pomijanie wycofywania zwiększa wydajność w sytuacji, gdy są używane kwantyfikatory zagnieżdżone. Mierzony jest czas potrzebny aparatowi wyrażeń regularnych na ustalenie, że ciąg wejściowy nie pasuje do dwóch wyrażeń regularnych. W pierwszym wyrażeniu regularnym jest używane wycofywanie w celu podjęcia próby dopasowania ciągu zawierającego co najmniej jedno wystąpienie co najmniej jednej cyfry szesnastkowej, po której następuje dwukropek, po którym następuje co najmniej jedna cyfra szesnastkowa, po której następują dwa dwukropki. Drugie wyrażenie regularne jest takie samo jak pierwsze, aby wyłączono w nim wycofywanie. Jak widać w wynikach przykładu, wyłączenie wycofywania przynosi znaczącą poprawę wydajności.
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
Asercji lookbehind
Platforma .NET zawiera dwa elementy języka, (?<=podwyrażenie) i (?<!podwyrażenie), które pasują do poprzedniego znaku lub znaków w ciągu wejściowym. Oba elementy języka są asercją o zerowej szerokości; oznacza to, że określają, czy znak lub znaki, które bezpośrednio poprzedzają bieżący znak, można dopasować przez podwyrażenie, bez przechodzenia lub wycofywania.
(?<=podwyrażenie) jest pozytywną asercją lookbehind. Oznacza to, że znak lub znaki przed bieżącą pozycją muszą być zgodne z podwyrażeniem podrzędnym. (?<!podwyrażenie) jest negatywną asercją lookbehind; oznacza to, że znak lub znaki przed bieżącym położeniem nie mogą być zgodne z podwyrażeniem. Zarówno pozytywne, jak i negatywne asercji lookbehind są najbardziej przydatne, gdy podwyrażenie jest podzbiorem poprzedniego podwyrażenia .
W poniższym przykładzie użyto dwóch równoważnych wzorców wyrażeń regularnych, które weryfikują nazwę użytkownika na adresie e-mail. Pierwszy wzorzec działa z niską wydajnością z powodu nadmiernego wycofywania. Drugi wzorzec modyfikuje pierwsze wyrażenie regularne, zastępując zagnieżdżony kwantyfikator pozytywną asercją wsteczną. Dane wyjściowe z przykładu wyświetlają czas Regex.IsMatch wykonywania 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
Pierwszy wzorzec wyrażenia regularnego , ^[0-9A-Z]([-.\w]*[0-9A-Z])*@jest zdefiniowany, jak pokazano w poniższej tabeli.
| Wzorzec | opis |
|---|---|
^ |
Rozpoczyna dopasowywanie na początku ciągu. |
[0-9A-Z] |
Dopasowuje znak alfanumeryczny. To porównanie nie uwzględnia wielkości liter, ponieważ Regex.IsMatch metoda jest wywoływana z opcją RegexOptions.IgnoreCase . |
[-.\w]* |
Dopasowuje zero, jedno lub większą liczbę wystąpień łącznika, kropki lub znaku słowa. |
[0-9A-Z] |
Dopasowuje znak alfanumeryczny. |
([-.\w]*[0-9A-Z])* |
Dopasowuje zero lub większą liczbę wystąpień kombinacji składających się z zera lub większej liczby łączników, kropek lub znaków słowa, po których występuje znak alfanumeryczny. Jest to pierwsza grupa przechwytywania. |
@ |
Dopasuj znak ("@"). |
Drugi wzorzec ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@wyrażenia regularnego , używa pozytywnej asercji lookbehind. Definicję tego wyrażenia pokazano w poniższej tabeli.
| Wzorzec | opis |
|---|---|
^ |
Rozpoczyna dopasowywanie na początku ciągu. |
[0-9A-Z] |
Dopasowuje znak alfanumeryczny. To porównanie nie uwzględnia wielkości liter, ponieważ Regex.IsMatch metoda jest wywoływana z opcją RegexOptions.IgnoreCase . |
[-.\w]* |
Dopasowuje zero lub większą liczbę wystąpień łącznika, kropki lub znaku słowa. |
(?<=[0-9A-Z]) |
Sprawdza ostatni dopasowany znak i kontynuuje dopasowywanie, jeśli jest to znak alfanumeryczny. Należy zauważyć, że znaki alfanumeryczne stanowią podzestaw zestawu składającego się z kropek, łączników i wszystkich znaków słowa. |
@ |
Dopasuj znak ("@"). |
Asercji lookahead
Platforma .NET zawiera dwa elementy języka, (?=podwyrażenie) i (?!podwyrażenie), które pasują do następnego znaku lub znaków w ciągu wejściowym. Oba elementy języka są asercją o zerowej szerokości; oznacza to, że określają, czy znak lub znaki, które natychmiast podążają za bieżącym znakiem, mogą być dopasowywane przez podwyrażenie, bez przechodzenia lub wycofywania.
(?=podwyrażenie) jest pozytywną asercją lookahead; oznacza to, że znak lub znaki po bieżącej pozycji muszą być zgodne z podwyrażeniem. (?!podwyrażenie) jest negatywną asercją wyprzedzającą; oznacza to, że znak lub znaki po bieżącym położeniu nie mogą być zgodne z podwyrażeniem. Zarówno dodatnie, jak i negatywne asercji lookahead są najbardziej przydatne, gdy podwyrażenie jest podzbiorem następnego podwyrażenia .
W poniższym przykładzie są używane dwa równoważne wzorce wyrażenia regularnego sprawdzające w pełni kwalifikowaną nazwę typu. Pierwszy wzorzec działa z niską wydajnością z powodu nadmiernego wycofywania. Drugi wzorzec modyfikuje pierwsze wyrażenie regularne, zastępując zagnieżdżony kwantyfikator pozytywną asercją wyprzedzającą. Dane wyjściowe z przykładu wyświetlają czas Regex.IsMatch wykonywania 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
Pierwszy wzorzec wyrażenia regularnego , ^(([A-Z]\w*)+\.)*[A-Z]\w*$jest zdefiniowany, jak pokazano w poniższej tabeli.
| Wzorzec | opis |
|---|---|
^ |
Rozpoczyna dopasowywanie na początku ciągu. |
([A-Z]\w*)+\. |
Dopasowuje znak alfanumeryczny (A–Z), po którym co najmniej raz występuje zero lub większa liczba znaków słowa, po których następuje kropka. To porównanie nie uwzględnia wielkości liter, ponieważ Regex.IsMatch metoda jest wywoływana z opcją RegexOptions.IgnoreCase . |
(([A-Z]\w*)+\.)* |
Dopasowuje poprzedni wzorzec zero lub większą liczbę razy. |
[A-Z]\w* |
Dopasowuje znak alfabetyczny, po którym występuje zero lub większa liczba znaków słowa. |
$ |
Dopasowywanie kończy się na końcu ciągu wejściowego. |
Drugi wzorzec ^((?=[A-Z])\w+\.)*[A-Z]\w*$wyrażenia regularnego , używa pozytywnej asercji lookahead. Definicję tego wyrażenia pokazano w poniższej tabeli.
| Wzorzec | opis |
|---|---|
^ |
Rozpoczyna dopasowywanie na początku ciągu. |
(?=[A-Z]) |
Sprawdza pierwszy następny znak i kontynuuje dopasowywanie, jeśli jest to znak alfabetyczny (A–Z). To porównanie nie uwzględnia wielkości liter, ponieważ Regex.IsMatch metoda jest wywoływana z opcją RegexOptions.IgnoreCase . |
\w+\. |
Dopasowuje co najmniej jeden znak słowa, po którym następuje kropka. |
((?=[A-Z])\w+\.)* |
Dopasowuje wzorzec składający się z co najmniej jednego znaku słowa, po którym zero lub większą liczbę razy występuje kropka. Początkowy znak słowa musi być znakiem alfabetycznym. |
[A-Z]\w* |
Dopasowuje znak alfabetyczny, po którym występuje zero lub większa liczba znaków słowa. |
$ |
Dopasowywanie kończy się na końcu ciągu wejściowego. |
Ogólne zagadnienia dotyczące wydajności
Poniższe sugestie nie mają specjalnie na celu zapobiegania nadmiernemu wycofywaniu, ale mogą pomóc zwiększyć wydajność wyrażenia regularnego:
Wstępnie kompiluj mocno używane wzorce. Najlepszym sposobem, aby to zrobić, jest użycie generatora źródła wyrażeń regularnych, aby wstępnie go skompilować. Jeśli generator źródła nie jest dostępny dla aplikacji, na przykład nie jest przeznaczony dla platformy .NET 7 lub nowszej lub nie znasz wzorca w czasie kompilacji, użyj RegexOptions.Compiled opcji .
Pamięć podręczna intensywnie używanych obiektów wyrażeń regularnych. Dzieje się tak niejawnie, gdy używasz generatora źródłowego. W przeciwnym razie utwórz obiekt regex i zapisz go do ponownego użycia, zamiast używać statycznych metod wyrażeń regularnych lub tworzenia i wyrzucania obiektu Regex.
Rozpocznij dopasowywanie od przesunięcia. Jeśli wiesz, że dopasowania zawsze zaczynają się od określonego przesunięcia do wzorca, przekaż przesunięcie przy użyciu przeciążenia, takiego jak Regex.Match(String, Int32). Spowoduje to zmniejszenie ilości tekstu, który aparat musi wziąć pod uwagę.
Zbierz tylko potrzebne informacje. Jeśli musisz tylko wiedzieć, czy występuje dopasowanie, ale nie tam, gdzie występuje dopasowanie, preferuj wartość Regex.IsMatch. Jeśli musisz tylko wiedzieć, ile razy coś pasuje, preferuj użycie polecenia Regex.Count. Jeśli musisz tylko znać granice dopasowania, ale nie cokolwiek w przypadku przechwytywania dopasowania, preferuj użycie polecenia Regex.EnumerateMatches. Tym mniej informacji aparat musi zapewnić, tym lepiej.
Unikaj niepotrzebnych przechwytywania. Nawiasy w wzorcu tworzą domyślnie grupę przechwytywania. Jeśli nie potrzebujesz przechwytywania, określ RegexOptions.ExplicitCapture lub użyj grup , które nie są przechwytywane. Dzięki temu aparat może śledzić te przechwytywane dane.
