Поиск с возвратом в регулярных выражениях

Поиск с возвратом происходит, если шаблон регулярного выражения содержит переменные квантификаторы или конструкции изменения, и обработчик регулярных выражений возвращается в предыдущее сохраненное состояние, чтобы продолжить поиск совпадения. В поиске с возвратом заключена сила регулярных выражений. Благодаря ему выражения могут быть мощными и гибкими, а также совпадать со сложными шаблонами. С другой стороны, эти возможности дорого обходятся. Часто именно поиск с возвратом существенно снижает производительность обработчика регулярных выражений. К счастью, разработчик может управлять работой обработчика регулярных выражений и тем, как он использует поиск с возвратом. В этой статье объясняется, как работает обратная дорожка и как вы можете управлять им.

Линейное сравнение без поиска с возвратом

Если шаблон регулярного выражения не содержит переменных квантификаторов или конструкций изменения, обработчик регулярных выражений работает за линейное время. Это значит, что когда обработчик регулярных выражений находит совпадение с первым языковым элементом шаблона в тексте входной строки, он сопоставляет следующий языковой элемент шаблона со следующим символом или группой символов входной строки. Так продолжается, пока поиск совпадения не заканчивается успешно или неуспешно. В обоих случаях обработчик регулярных выражений продвигается вперед, обрабатывая по одному символу входной строки.

Это показывается в следующем примере. Регулярное выражение e{2}\w\b ищет следующую строку: два вхождения буквы «e», затем символ слова, затем граница слова.

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

Несмотря на то что это регулярное выражение содержит квантификатор {2}, оно обрабатывается линейным образом. Обработчик регулярных выражений не выполняет поиск с возвратом, поскольку квантификатор {2} не является переменным квантификатором; он указывает конкретное, а не переменное число вхождений предшествующей части выражения. В результате обработчик регулярных выражений ищет совпадение с шаблоном во входной строке, как показано в следующей таблице.

Если в шаблоне регулярного выражения нет переменных квантификаторов или конструкций изменения, максимальное число сравнений, необходимое для поиска во входной строке совпадения с шаблоном регулярного выражения, примерно равно числу символов во входной строке. В этом случае обработчик регулярных выражений использует 19 сравнений, чтобы определить возможные совпадения в этой 13-значной строке. Другими словами, обработчик регулярных выражений работает почти за линейное время, если отсутствуют переменные квантификаторы или конструкции изменения.

Поиск с возвратом с необязательными квантификаторами и конструкциями чередования

Если регулярное выражение содержит переменные квантификаторы или конструкции изменения, оценка входной строки уже не может быть линейной. Сопоставление шаблонов с подсистемой недетерминированного конечного автоматона (NFA) определяется элементами языка в регулярном выражении, а не символами, которые должны быть сопоставлены во входной строке. Поэтому обработчик регулярных выражений пытается найти полное совпадение для переменных подвыражений или подвыражений выбора. При переходе к следующему языковому элементу подвыражения и нарушении совпадения обработчик регулярных выражений отбрасывает совпавшую часть и возвращается к ранее сохраненному состоянию; ему снова требуется найти во входной строке совпадение с регулярным выражением целиком. Процесс возвращения к ранее сохраненному состоянию для поиска совпадения называется "поиск с возвратом".

Например, рассмотрим шаблон регулярного выражения .*(es), совпадающий с символами "es" и любыми предшествующими символам. Как показано в следующем примере, если взять входную строку "Essential services are provided by regular expressions.", совпадать с шаблоном будет вся строка до букв "es" в слове "expressions" включительно.

using System;
using System.Text.RegularExpressions;

public class Example2
{
    public static void Run()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
        if (m.Success)
        {
            Console.WriteLine($"'{m.Value}' found at position {m.Index}");
            Console.WriteLine($"'es' found at position {m.Groups[1].Index}");
        }
    }
}
//    'Essential services are provided by regular expres' found at position 0
//    'es' found at position 47

Imports System.Text.RegularExpressions

Module Example2
    Public Sub Run()
        Dim input As String = "Essential services are provided by regular expressions."
        Dim pattern As String = ".*(es)"
        Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
        If m.Success Then
            Console.WriteLine("'{0}' found at position {1}",
                              m.Value, m.Index)
            Console.WriteLine("'es' found at position {0}",
                              m.Groups(1).Index)
        End If
    End Sub
End Module
'    'Essential services are provided by regular expres' found at position 0
'    'es' found at position 47

В этом случае обработчик регулярных выражений использует поиск с возвратом следующим образом.

• Обработчик обнаруживает совпадение части выражения .* (что соответствует любому числу любых символов) со всей входной строкой.

• Затем обработчик ищет совпадение для символа "e" шаблона регулярного выражения. Однако во входной строке нет больше символов для поиска совпадения.

• Обработчик возвращается к месту последнего успешного совпадения, "Essential services are provided by regular expressions", и сравнивает символ "e" с точкой в конце предложения. Совпадение отсутствует.

• Обработчик продолжает возвращаться к предыдущим успешным совпадениям, отступая по одному символу, пока предположительно подходящей подстрокой не становится подстрока "Essential services are provided by regular expr". Затем обработчик сравнивает символ "e" шаблона со второй буквой "e" в слове "expressions" и обнаруживает совпадение.

• Затем он сравнивает символ "s" шаблона с символом "s" после символа "e" в строке (первая буква "s" в слове "expressions"). Совпадение успешно.

При использовании поиска с возвратом поиск совпадения шаблона регулярного выражения со входной строкой длиной 55 символов требует 67 операций сравнения. Как правило, если в шаблоне регулярного выражения есть один переменный квантификатор или одна конструкция изменения, число сравнений, необходимых для поиска во входной строке совпадения с шаблоном регулярного выражения, более чем вдвое превышает число символов во входной строке.

Поиск с возвратом со вложенными необязательными квантификаторами

Количество сравнений, необходимое для поиска во входной строке совпадения с шаблоном регулярного выражения, может увеличиваться экспоненциально, если шаблон включает большое количество конструкций изменения или вложенные конструкции изменения, или, что случается чаще, вложенные переменные квантификаторы. Например, шаблон регулярного выражения ^(a+)+$ должен совпадать со строкой, состоящей из одного и более символов "a". В примере показаны две входные строки одинаковой длины, только одна из которых совпадает с шаблоном. Класс System.Diagnostics.Stopwatch используется для определения времени выполнения операции поиска совпадения.

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

Как показано в выходных данных примера, подсистема регулярных выражений заняла значительно больше времени, чтобы найти, что входная строка не соответствовала шаблону, как это было для идентификации соответствующей строки. Неуспешное совпадение — худший сценарий. Обработчик регулярных выражений должен использовать регулярное выражение для проверки всех возможных путей в данных, чтобы заключить, что совпадения нет, а вложенные скобки сильно увеличивают количество таких путей. Чтобы установить, что вторая строка не совпадает с шаблоном, обработчику регулярных выражений нужно выполнить следующие действия:

• Он проверяет, что находится в начале строки, после чего проверяет первые пять символов строки на совпадение с шаблоном a+. Затем проверяет, что в строке нет других групп символов "a". Затем выполняется проверка до конца строки. Поскольку в строке содержится один дополнительный символ, проверка оказывается неудачной. Этот отрицательный результат требует 9 сравнений. Подсистема регулярных выражений также сохраняет сведения о состоянии из его совпадений "a" (который мы будем вызывать match 1), "aa" (match 2), "aaa" (match 3) и "aaaa" (match 4).

• Затем он возвращается к предварительно сохраненному совпадению 4. Далее устанавливается наличие дополнительного символа "a", который назначается дополнительной захваченной группе. Затем выполняется проверка до конца строки. Поскольку в строке содержится один дополнительный символ, проверка оказывается неудачной. Этот отрицательный результат требует 4 сравнений. Таким образом, всего выполнено 13 сравнений.

• Затем он возвращается к предварительно сохраненному совпадению 3. Он устанавливает наличие двух дополнительных символов "a", которые назначаются дополнительной захваченной группе. Однако проверка на наличие окончания строки не проходит. Затем он возвращается в соответствие 3 и пытается сопоставить два дополнительных символа a в двух дополнительных захваченных группах. Проверка на наличие окончания строки не проходит. Для получения этих неуспешных совпадений потребовалось 12 сравнений. Таким образом, всего выполнено 25 сравнений.

Сравнение входной строки с регулярным выражением продолжается таким же образом, пока обработчик регулярных выражений не переберет все возможные комбинации совпадений, заключив, что совпадений нет. Из-за наличия вложенных квантификаторов это сравнение представляет собой операцию экспоненциальной сложности O(2ⁿ), где n — количество символов входной строки. Это значит, что в худшем случае входная строка, состоящая из 30 символов, требует по примерным подсчетам 1 073 741 824 сравнений, а входная строка длиной 40 символов — 1 099 511 627 776 сравнений. При использовании строк такого или большего размера методы, выполняющие регулярные выражения, могут выполняться очень долго, прежде чем будет установлено, что входная строка не совпадает с шаблоном регулярного выражения.

Управление обратным отслеживанием

Поиск с возвратом позволяет создавать мощные и гибкие регулярные выражения. Однако, как было показано в предыдущем разделе, эти преимущества могут сопровождаться неприемлемо низкой производительностью. Чтобы предотвратить излишнее использование поиска с возвратом, необходимо указать интервал времени ожидания при создании экземпляра объекта Regex или вызвать соответствующий метод статического регулярного выражения. Этот метод будет рассмотрен в следующем разделе. Кроме того, в .NET поддерживаются три элемента языка регулярных выражений, ограничивающих или подавляющих поиск с обратным отслеживанием, что позволяет выполнять сложные регулярные выражения, не теряя или почти не теряя в производительности: атомарные группы, утверждения просмотра назад и утверждения просмотра вперед. Дополнительные сведения о каждом элементе языка см. в разделе "Группировка конструкций".

Подсистема регулярных выражений без обратного отслеживания

Если вам не нужно использовать какие-либо конструкции, требующие обратного отслеживания (например, обходные пути, обратные ссылки или атомарные группы), рассмотрите возможность использования RegexOptions.NonBacktracking режима. Этот режим предназначен для выполнения во времени пропорционально длине входных данных. Дополнительные сведения см . в режиме NonBacktracking. Можно также задать значение времени ожидания.

Ограничение размера входных данных

Некоторые регулярные выражения имеют допустимую производительность, если входные данные не являются исключительно большими. Если все разумные текстовые входные данные в вашем сценарии, как известно, находятся под определенной длиной, попробуйте отклонить более длинные входные данные перед применением регулярного выражения к ним.

Указание интервала времени ожидания

Вы можете задать значение времени ожидания, представляющее самый длинный интервал, когда система регулярных выражений будет искать одно совпадение, прежде чем она отказывается от попытки и создает RegexMatchTimeoutException исключение. Чтобы задать интервал ожидания, укажите значение TimeSpan в конструкторе Regex(String, RegexOptions, TimeSpan) регулярных выражений экземпляра. Кроме того, каждый статический метод сравнения с шаблоном имеет перегруженную версию с параметром TimeSpan , который позволяет указать значение времени ожидания.

Если значение времени ожидания явно не задано, значение времени ожидания по умолчанию определяется следующим образом:

• При наличии значения времени ожидания на уровне приложения. Это может быть любое значение времени ожидания, которое применяется к домену приложения, в котором Regex создается экземпляр объекта или вызывается статический метод. Можно задать значение времени ожидания приложения, вызвав AppDomain.SetData метод, чтобы назначить строковое представление TimeSpan значения свойству REGEX_DEFAULT_MATCH_TIMEOUT .
• Если значение InfiniteMatchTimeoutвремени ожидания приложения не задано.

По умолчанию интервал времени ожидания задается в Regex.InfiniteMatchTimeout и время ожидания обработчика регулярных выражений не истекает.

Выражение RegexMatchTimeoutException указывает на то, что обработчику регулярных выражений не удалось найти совпадение в пределах заданного интервала времени ожидания, но не указывает причину создания исключения. Причина может быть чрезмерной обратной дорожкой, но также возможно, что интервал времени ожидания был установлен слишком низко, учитывая системную нагрузку во время возникновения исключения. При обработке исключения можно прервать дальнейший поиск совпадений входной строки или увеличить интервал времени ожидания и повторно выполнить операцию поиска.

Например, следующий код вызывает Regex(String, RegexOptions, TimeSpan) конструктор для создания экземпляра Regex объекта со значением времени ожидания 1 секунды. Шаблон регулярного выражения (a+)+$, который сопоставляется с последовательностью из одного или нескольких символов "a" в конце строки, относится к шаблонам с чрезмерным использованием поиска с возвратом. RegexMatchTimeoutException Если создается исключение, в примере увеличивается значение времени ожидания до максимального интервала в 3 секунды. После этого попытки найти соответствие шаблону будут прерваны.

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.

Атомарные группы

Элемент (?>языка вложенных выражений) является атомарным группированием. Он предотвращает обратный переход в подэкспрессию. После успешного сопоставления этого элемента языка он не будет отказаться от какой-либо части его соответствия после последующего обратного отслеживания. Например, в шаблоне (?>\w*\d*)1, если 1 не удается сопоставить, \d* не будет давать никаких соответствий, даже если это означает, что 1 будет успешно сопоставляться. Атомарные группы помогают предотвращать проблемы с производительностью, связанные с неуспешным совпадением.

В следующем примере показано, как подавление поиска с возвратом улучшает производительность при использовании вложенных квантификаторов. В нем измеряется время, которое требуется обработчику регулярных выражений, чтобы определить, что входная строка не совпадает с двумя регулярными выражениями. В первом регулярном выражении поиск с возвратом используется для поиска строки, содержащей последовательно одну и более шестнадцатеричных цифр, двоеточие, одну и более шестнадцатеричных цифр и два двоеточия. Второе регулярное выражение аналогично первому, но в нем отключен поиск с возвратом. Как показывают выходные данные примера, отключение поиска с возвратом приводит к существенному росту производительности.

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

Проверочные утверждения с просмотром назад

В платформу .NET входят два элемента языка, (?<=часть_выражения) и (?<!часть_выражения), которые сопоставляются с одним или несколькими предшествующими символами во входной строке. Оба элемента языка являются утверждениями нулевой ширины; они определяют, должны ли символы, непосредственно предшествующие текущему, соответствовать subexpression. Смещения или поиска с возвратом не происходит.

(?<=subexpression) — это утверждение положительного просмотра назад; символы, непосредственно предшествующие текущему, должны соответствовать subexpression. (?<!subexpression) — это утверждение отрицательного просмотра назад; символы, непосредственно предшествующие текущему, не должны соответствовать subexpression. Утверждения положительного и отрицательного просмотра назад наиболее полезны, если subexpression является подмножеством предыдущего подвыражения.

В следующем примере используются два равнозначных шаблона регулярных выражений, которые проверяют имя пользователя в адресе электронной почты. Первый шаблон демонстрирует низкую производительность из-за неоправданного использования поиска с возвратом. Во втором шаблоне то же самое регулярное выражение изменено. Вложенный квантификатор заменен на утверждение положительного просмотра назад. Выходные данные примера демонстрируют время выполнения метода Regex.IsMatch .

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

Первый шаблон регулярного выражения ^[0-9A-Z]([-.\w]*[0-9A-Z])*@определяется, как показано в следующей таблице.

Второй шаблон регулярного выражения ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@использует утверждение положительного просмотра назад. Определяется, как показано в следующей таблице.

Проверочные утверждения с просмотром вперед

В платформу .NET входят два элемента языка, (?=часть_выражения) и (?!часть_выражения), которые сопоставляются с одним или несколькими следующими символами во входной строке. Оба элемента языка являются утверждениями нулевой ширины; они определяют, должны ли символы, непосредственно следующие за текущим, соответствовать subexpression. Смещения или поиска с возвратом не происходит.

(?=subexpression) — это утверждение положительного просмотра вперед; символы, непосредственно следующие за текущим, должны соответствовать subexpression. (?!subexpression) — это утверждение отрицательного просмотра вперед; символы, непосредственно следующие за текущим, не должны соответствовать subexpression. Утверждения положительного и отрицательного просмотра вперед наиболее полезны, если subexpression является подмножеством следующего подвыражения.

В следующем примере используются два одинаковых шаблона регулярного выражения, проверяющих полное имя типа. Первый шаблон демонстрирует низкую производительность из-за неоправданного использования поиска с возвратом. Во втором шаблоне то же самое регулярное выражение изменено. Вложенный квантификатор заменен на утверждение положительного просмотра вперед. Выходные данные примера демонстрируют время выполнения метода Regex.IsMatch .

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

public class Example6
{
    public static void Run()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        bool result;
        Stopwatch sw;

        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine("{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

Первый шаблон регулярного выражения ^(([A-Z]\w*)+\.)*[A-Z]\w*$определяется, как показано в следующей таблице.

Второй шаблон регулярного выражения ^((?=[A-Z])\w+\.)*[A-Z]\w*$использует утверждение положительного просмотра вперед. Определяется, как показано в следующей таблице.

Общие рекомендации по производительности

Следующие предложения не специально предназначены для предотвращения чрезмерного обратного отслеживания, но могут помочь повысить производительность регулярного выражения:

1. Предварительно компилировать часто используемые шаблоны. Лучший способ сделать это — использовать генератор источника регулярных выражений для предварительной компиляции. Если генератор источника недоступен для приложения, например вы не предназначение для .NET 7 или более поздней версии, или вы не знаете шаблон во время компиляции, используйте RegexOptions.Compiled этот параметр.

2. Кэш часто используемых объектов Regex. Это происходит неявно при использовании генератора источника. В противном случае создайте объект Regex и сохраните его для повторного использования, а не с помощью статических методов Regex или создания и извлечения объекта Regex.

3. Начало сопоставления из смещения. Если вы знаете, что совпадения всегда начинаются за пределами определенного смещения в шаблон, передайте смещение с помощью перегрузки, например Regex.Match(String, Int32). Это приведет к сокращению объема текста, который необходимо учитывать подсистеме.

4. Соберите только необходимые сведения. Если вам нужно только знать, происходит ли совпадение, но не там, где происходит совпадение, предпочтительна Regex.IsMatch. Если вам нужно только знать, сколько раз что-то совпадает, предпочитаете использовать Regex.Count. Если вам нужно только знать границы совпадения, но не что-либо о захватах совпадения, предпочесть использовать Regex.EnumerateMatches. Чем меньше информации, тем лучше необходимо предоставить подсистему.

5. Избегайте ненужных захватов. Круглые скобки в шаблоне образуют группу записи по умолчанию. Если вам не нужны записи, укажите RegexOptions.ExplicitCapture или используйте группы без записи . Это позволяет сохранить механизм отслеживания этих записей.

См. также

• Регулярные выражения .NET
• Элементы языка регулярных выражений — краткий справочник
• Квантификаторы
• Alternation Constructs
• Конструкции группировки в регулярных выражениях