Backtracking nelle espressioni regolari

Il backtracking si verifica quando un modello di espressione regolare contiene quantificatori o costrutti di alternanza facoltativi e il motore delle espressioni regolari torna a uno stato salvato in precedenza per continuare la ricerca di una corrispondenza. Il backtracking è alla base della potenza delle espressioni regolari; consente loro di essere potenti e flessibili e di corrispondere a pattern molto complessi. Allo stesso tempo, questa potenza ha un costo. Il backtracking è spesso il fattore più importante che influisce sulle prestazioni del motore di espressioni regolari. Fortunatamente, lo sviluppatore è in grado di controllare il comportamento del motore delle espressioni regolari e il modo in cui viene utilizzato il backtracking. In questo articolo viene illustrato il funzionamento del backtracking e il modo in cui può essere controllato.

Confronto lineare senza tornare indietro

Se un modello di espressione regolare non contiene quantificatori facoltativi o costrutti di alternanza, il motore delle espressioni regolari viene eseguito in un tempo lineare, ovvero dopo che il motore delle espressioni regolari trova una corrispondenza tra il primo elemento del linguaggio del modello e il testo della stringa di input, prova a trovare una corrispondenza tra l'elemento del linguaggio successivo del modello e il carattere o il gruppo di caratteri successivi della stringa di input. Questo continua finché la corrispondenza non ha esito positivo o negativo. In entrambi i casi, il motore delle espressioni regolari avanza di un carattere alla volta nella stringa di input.

Di seguito ne viene illustrato un esempio. L'espressione regolare e{2}\w\b cerca due occorrenze della lettera "e", seguite da qualsiasi carattere alfanumerico, seguito da un confine di parola.

using System;
using System.Text.RegularExpressions;

public class Example1
{
    public static void Run()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        foreach (Match match in Regex.Matches(input, pattern))
            Console.WriteLine($"{match.Value} found at position {match.Index}");
    }
}
// The example displays the following output:
//       eed found at position 11

Imports System.Text.RegularExpressions

Module Example1
    Public Sub Run()
        Dim input As String = "needing a reed"
        Dim pattern As String = "e{2}\w\b"
        For Each match As Match In Regex.Matches(input, pattern)
            Console.WriteLine("{0} found at position {1}",
                              match.Value, match.Index)
        Next
    End Sub
End Module
' The example displays the following output:
'       eed found at position 11

Benché questa espressione regolare includa il quantificatore {2}, viene valutata in modo lineare. Il motore delle espressioni regolari non esegue il backtracking perché {2} non è un quantificatore facoltativo, ma specifica un numero esatto e non un numero variabile di volte in cui trovare la corrispondenza della sottoespressione precedente. Di conseguenza, il motore delle espressioni regolari tenta di trovare una corrispondenza tra il modello di espressione regolare e la stringa di input come illustrato nella tabella seguente.

Se un modello di espressione regolare non include quantificatori facoltativi o costrutti di alternanza, il numero massimo di confronti necessari per trovare una corrispondenza tra il modello di espressione regolare e la stringa di input equivale approssimativamente al numero di caratteri della stringa di input. In questo caso, il motore delle espressioni regolari utilizza 19 confronti per identificare le possibili corrispondenze in questa stringa di 13 caratteri. In altre parole, il motore delle espressioni regolari viene eseguito in un tempo quasi lineare se non contiene quantificatori facoltativi o costrutti di alternanza.

Backtracking con quantificatori opzionali o costrutti di alternanza

Quando un'espressione regolare include quantificatori facoltativi o costrutti di alternanza, la valutazione della stringa di input non è più lineare. La ricerca di corrispondenza di modelli con un motore NFA (Nondeterministic Finite Automaton) è guidata dagli elementi del linguaggio dell'espressione regolare e non dai caratteri per i quali trovare corrispondenza nella stringa di input. Il motore delle espressioni regolari prova pertanto a trovare una piena corrispondenza con le sottoespressioni facoltative o alternative. Quando passa all'elemento del linguaggio successivo nella sottoespressione e il tentativo di corrispondenza non riesce, il motore delle espressioni regolari può abbandonare una parte della corrispondenza riuscita e tornare a uno stato precedente salvato, per far corrispondere l'espressione regolare nel suo complesso alla stringa di input. Questo processo che consiste nel tornare a uno stato precedentemente salvato per trovare una corrispondenza è noto come backtracking.

Si consideri, ad esempio, il modello di espressione regolare .*(es)che cerca una corrispondenza con i caratteri "es" e tutti i caratteri che li precedono. Come illustrato nell'esempio seguente, se la stringa di input è "Essential services are provided by regular expressions.", il modello cerca una corrispondenza con l'intera stringa fino ai caratteri "es" in "expressions" compresi.

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

A tale scopo, il motore delle espressioni regolari utilizza il backtracking come segue:

• Fa corrispondere .* (che corrisponde a zero, una o più occorrenze di qualsiasi carattere) all'intera stringa di input.

• Tenta di trovare una corrispondenza di "e" nel modello di espressione regolare. Tuttavia, nella stringa di input non sono presenti altri caratteri di cui cercare una corrispondenza.

• Esegue il backtracking fino all'ultima corrispondenza esatta, "Essential services are provided by regular expressions", e tenta di trovare una corrispondenza di "e" con il punto alla fine della frase. La corrispondenza ha esito negativo.

• Continua a tornare indietro fino a una precedente corrispondenza riuscita, un carattere alla volta, finché la sottostringa associata provvisoriamente non è "Essential services are provided by regular expr". Confronta quindi la "e" nel modello con la seconda "e" in "expressions" e trova una corrispondenza.

• Confronta la "s" nel modello con la "s" che segue il carattere "e" corrispondente (la prima "s" in "expressions"). La corrispondenza è riuscita.

Quando si utilizza il backtracking, la ricerca di una corrispondenza tra il modello di espressione regolare e la stringa di input, con una lunghezza pari a 55 caratteri, richiede 67 operazioni di confronto. In genere, se un modello di espressione regolare include un singolo costrutto di alternanza o un singolo quantificatore facoltativo, il numero di operazioni di confronto necessarie per trovare una corrispondenza del modello è più del doppio rispetto al numero di caratteri della stringa di input.

Backtracking con quantificatori opzionali annidati

Il numero di operazioni di confronto necessarie per trovare una corrispondenza di un modello di espressione regolare può aumentare in modo esponenziale se il modello include un numero elevato di costrutti di alternanza, se include costrutti di alternanza annidati o se include sopratutto quantificatori facoltativi annidati. Il modello di espressione regolare ^(a+)+$ , ad esempio, è progettato per cercare una corrispondenza con una stringa completa contenente uno o più caratteri "a". Nell'esempio vengono fornite due stringhe di input di lunghezza identica, ma solo la prima stringa corrisponde al modello. La classe System.Diagnostics.Stopwatch viene utilizzata per determinare il tempo richiesto dall'operazione di corrispondenza.

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

Come illustrato nell'output dell'esempio, il motore delle espressioni regolari ha impiegato significativamente più tempo per rilevare che una stringa di input non corrisponde al modello rispetto al tempo impiegato per identificare una stringa corrispondente. Ciò è dovuto al fatto che una corrispondenza negativa rappresenta sempre lo scenario peggiore. Il motore delle espressioni regolari deve utilizzare l'espressione regolare per seguire tutti i percorsi possibili nei dati prima di poter concludere che la corrispondenza è negativa e le parentesi annidate creano molti percorsi aggiuntivi nei dati. Il motore delle espressioni regolari conclude che la seconda stringa non corrisponde al modello effettuando le operazioni seguenti:

• Verifica di essere all'inizio della stringa, quindi cerca una corrispondenza tra i primi cinque caratteri della stringa e il modello a+. Determina quindi che non esistono altri gruppi di caratteri "a" nella stringa. Infine, verifica la fine della stringa. Poiché nella stringa rimane un ulteriore carattere, la corrispondenza ha esito negativo. Questa mancata corrispondenza richiede 9 confronti. Il motore delle espressioni regolari salva inoltre informazioni di stato sulle corrispondenze di "a" (che chiameremo corrispondenza 1), "aa" (corrispondenza 2), "aaa" (corrispondenza 3) e "aaaa" (corrispondenza 4).

• Torna alla corrispondenza 4 salvata in precedenza. Determina che esiste un altro carattere "a" da assegnare a un gruppo acquisito aggiuntivo. Infine, verifica la fine della stringa. Poiché nella stringa rimane un carattere aggiuntivo, la corrispondenza ha esito negativo. Questo confronto non riuscito richiede 4 confronti. Fino a questo momento sono stati eseguiti complessivamente 13 confronti.

• Torna alla corrispondenza 3 salvata in precedenza. Determina che ci sono altri due caratteri "a" da assegnare a un ulteriore gruppo catturato. Tuttavia, il test di fine della stringa ha esito negativo. Torna quindi al match 3 e cerca di far corrispondere i due caratteri "a" aggiuntivi in ulteriori due gruppi acquisiti. Il test di fine della stringa ha ancora esito negativo. Queste corrispondenze non riuscite richiedono 12 confronti. Fino a questo punto, sono stati eseguiti complessivamente 25 confronti.

Il confronto della stringa di input con l'espressione regolare continua in questo modo fino a quando il motore delle espressioni regolari non ha tentato tutte le combinazioni di corrispondenze possibili, concludendo infine che non vi è alcuna corrispondenza. A causa dei quantificatori annidati, questo confronto è un'operazione O(2ⁿ) o un'operazione esponenziale, dove n è il numero di caratteri all'interno della stringa di input. Ciò significa che nei casi peggiori una stringa di input di 30 caratteri richiede circa 1.073.741.824 confronti e una stringa di input di 40 caratteri richiede circa 1.099.511.627.776 confronti. Se si utilizzano stringhe di queste lunghezze o di lunghezze ancora maggiore, i metodi delle espressioni regolari possono richiedere una quantità di tempo eccessiva per il completamento quando elaborano un input che non corrisponde al modello di espressione regolare.

Controllare il backtracking

Il backtracking consente di creare espressioni regolari potenti e flessibili. Tuttavia, come mostrato nella sezione precedente, questi vantaggi possono essere accompagnati da prestazioni inaccettabilmente scarse. Per evitare un utilizzo eccessivo del backtracking, è necessario definire un intervallo di timeout quando si crea un'istanza di un oggetto Regex o si chiama un metodo di espressione regolare statica corrispondente. Questo è discusso nella sezione seguente. .NET supporta anche tre elementi del linguaggio delle espressioni regolari che limitano o evitano del tutto l'uso del backtracking e che supportano espressioni regolari complesse senza o con una minima riduzione delle prestazioni: gruppi atomici, asserzioni lookbehind e asserzioni lookahead. Per altre informazioni su ogni elemento del linguaggio, vedere Costrutti di raggruppamento.

Motore delle espressioni regolari senza backtracking

Se non è necessario usare costrutti che richiedono il backtracking, ad esempio, lookaround, backreference o gruppi atomici, è consigliabile usare la modalità RegexOptions.NonBacktracking. Questa modalità è progettata per l'esecuzione con una durata proporzionale alla lunghezza dell'input. Per ulteriori informazioni, vedi modalità NonBacktracking. È anche possibile impostare un valore di timeout.

Limitare le dimensioni degli input

Alcune espressioni regolari hanno prestazioni accettabili, a meno che l'input non sia estremamente grande. Se è noto che tutti gli input di testo ragionevoli nello scenario sono al di sotto di una determinata lunghezza, è consigliabile rifiutare input più lunghi prima di applicarli all'espressione regolare.

Specificare un intervallo di timeout

È possibile impostare un valore di timeout che rappresenta l'intervallo più lungo per cui il motore delle espressioni regolari cercherà una singola corrispondenza prima di abbandonare il tentativo e generare un'eccezione RegexMatchTimeoutException. Specificare l'intervallo di timeout fornendo un valore TimeSpan al costruttore Regex(String, RegexOptions, TimeSpan) per instanziare espressioni regolari. Inoltre, ogni metodo statico di corrispondenza dei modelli ha un overload con un parametro TimeSpan che consente di specificare un valore di time-out.

Se non si imposta un valore di timeout in modo esplicito, il valore di timeout predefinito viene determinato nel modo seguente:

• Usando il valore di timeout a livello di applicazione, se presente. Può trattarsi di qualsiasi valore di timeout applicabile al dominio dell'applicazione in cui viene creata un'istanza dell'oggetto Regex oppure viene eseguita la chiamata al metodo statico. È possibile impostare il valore di timeout a livello di applicazione chiamando il metodo AppDomain.SetData per assegnare la rappresentazione di stringa di un valore TimeSpan alla proprietà REGEX_DEFAULT_MATCH_TIMEOUT.
• Usando il valore InfiniteMatchTimeout, se non è stato impostato alcun valore di timeout a livello di applicazione.

Per impostazione predefinita, l'intervallo di timeout viene impostato su Regex.InfiniteMatchTimeout e il motore delle espressioni regolari non ha timeout.

Un'eccezione RegexMatchTimeoutException indica che il motore delle espressioni regolari non è in grado di trovare una corrispondenza nell'intervallo di timeout specificato, ma non indica perché è stata generata l'eccezione. Il motivo può essere l'utilizzo eccessivo del backtracking, ma è anche possibile che l'intervallo di timeout sia stato impostato su un valore troppo basso dato il carico di sistema al momento in cui l'eccezione è stata generata. Quando si gestisce l'eccezione, è possibile scegliere di ignorare ulteriori corrispondenze con la stringa di input o aumentare l'intervallo di timeout e ritentare l'operazione corrispondente.

Ad esempio, il codice seguente chiama il costruttore Regex(String, RegexOptions, TimeSpan) per creare un'istanza di un oggetto Regex con un valore di timeout di 1 secondo. Il modello di espressione regolare (a+)+$, che corrisponde a uno o più sequenze di uno o più caratteri "a" alla fine di una riga, è soggetto all'utilizzo eccessivo del backtracking. Se viene generata una RegexMatchTimeoutException, l'esempio aumenta il valore di timeout fino a un intervallo massimo di 3 secondi. Dopodiché, abbandona il tentativo di far corrispondere il modello.

using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading;

public class Example
{
    const int MaxTimeoutInSeconds = 3;

    public static void Main()
    {
        string pattern = @"(a+)+$";    // DO NOT REUSE THIS PATTERN.
        Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));
        Stopwatch? sw = null;

        string[] inputs = { "aa", "aaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                         "aaaaaaaaaaaaaaaaaaaaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };

        foreach (var inputValue in inputs)
        {
            Console.WriteLine($"Processing {inputValue}");
            bool timedOut = false;
            do
            {
                try
                {
                    sw = Stopwatch.StartNew();
                    // Display the result.
                    if (rgx.IsMatch(inputValue))
                    {
                        sw.Stop();
                        Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                    else
                    {
                        sw.Stop();
                        Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                }
                catch (RegexMatchTimeoutException e)
                {
                    sw.Stop();
                    // Display the elapsed time until the exception.
                    Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed);
                    Thread.Sleep(1500);       // Pause for 1.5 seconds.

                    // Increase the timeout interval and retry.
                    TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
                    if (timeout.TotalSeconds > MaxTimeoutInSeconds)
                    {
                        Console.WriteLine($"Maximum timeout interval of {MaxTimeoutInSeconds} seconds exceeded.");
                        timedOut = false;
                    }
                    else
                    {
                        Console.WriteLine($"Changing the timeout interval to {timeout}");
                        rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
                        timedOut = true;
                    }
                }
            } while (timedOut);
            Console.WriteLine();
        }
    }
}
// The example displays output like the following :
//    Processing aa
//    Valid: 'aa' (00.0000779 seconds)
//
//    Processing aaaa>
//    'aaaa>' is not a valid string. (00.00005 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
//    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
//    Changing the timeout interval to 00:00:02
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
//    Changing the timeout interval to 00:00:03
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
//    Maximum timeout interval of 3 seconds exceeded.
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
//    Maximum timeout interval of 3 seconds exceeded.

Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading

Module Example
    Const MaxTimeoutInSeconds As Integer = 3

    Public Sub Main()
        Dim pattern As String = "(a+)+$"    ' DO NOT REUSE THIS PATTERN.
        Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))
        Dim sw As Stopwatch = Nothing

        Dim inputs() As String = {"aa", "aaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                                   "aaaaaaaaaaaaaaaaaaaaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>"}

        For Each inputValue In inputs
            Console.WriteLine("Processing {0}", inputValue)
            Dim timedOut As Boolean = False
            Do
                Try
                    sw = Stopwatch.StartNew()
                    ' Display the result.
                    If rgx.IsMatch(inputValue) Then
                        sw.Stop()
                        Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed)
                    Else
                        sw.Stop()
                        Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed)
                    End If
                Catch e As RegexMatchTimeoutException
                    sw.Stop()
                    ' Display the elapsed time until the exception.
                    Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed)
                    Thread.Sleep(1500)       ' Pause for 1.5 seconds.

                    ' Increase the timeout interval and retry.
                    Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
                    If timeout.TotalSeconds > MaxTimeoutInSeconds Then
                        Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                          MaxTimeoutInSeconds)
                        timedOut = False
                    Else
                        Console.WriteLine("Changing the timeout interval to {0}",
                                          timeout)
                        rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
                        timedOut = True
                    End If
                End Try
            Loop While timedOut
            Console.WriteLine()
        Next
    End Sub
End Module
' The example displays output like the following:
'    Processing aa
'    Valid: 'aa' (00.0000779 seconds)
'    
'    Processing aaaa>
'    'aaaa>' is not a valid string. (00.00005 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
'    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
'    Changing the timeout interval to 00:00:02
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
'    Changing the timeout interval to 00:00:03
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
'    Maximum timeout interval of 3 seconds exceeded.
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
'    Maximum timeout interval of 3 seconds exceeded.

Gruppi atomici

L'elemento del linguaggio (?>sottoespressione) è un raggruppamento atomico. Impedisce il backtracking all'interno della sottoespressione. Una volta che questo elemento del linguaggio ha trovato una corrispondenza, non cederà alcuna parte di tale corrispondenza al backtracking successivo. Ad esempio, se nel modello (?>\w*\d*)1 non è possibile trovare corrispondenze per 1, \d* non rinuncia ad alcuna corrispondenza, anche se ciò significa che si consente una corrispondenza corretta per 1. I gruppi atomici consentono di evitare i problemi di prestazioni associati a corrispondenze non riuscite.

L'esempio seguente illustra come la soppressione del backtracking migliori le prestazioni quando si utilizzano quantificatori annidati. Viene calcolato il tempo impiegato dal motore delle espressioni regolari per determinare che una stringa di input non corrisponde a due espressioni regolari. La prima espressione regolare utilizza il backtracking per tentare di trovare una corrispondenza con una stringa contenente una o più occorrenze di una o più cifre esadecimali seguite da due punti, seguiti da una o più cifre esadecimali, seguite da un doppio due punti. La seconda espressione regolare è identica alla prima, con la differenza che il backtracking è disabilitato. Come illustrato nell'output dell'esempio, il miglioramento delle prestazioni derivante dalla disabilitazione del backtracking è significativo.

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

public class Example4
{
    public static void Run()
    {
        string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
        bool matched;
        Stopwatch sw;

        Console.WriteLine("With backtracking:");
        string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, backPattern);
        sw.Stop();
        Console.WriteLine($"Match: {Regex.IsMatch(input, backPattern)} in {sw.Elapsed}");
        Console.WriteLine();

        Console.WriteLine("Without backtracking:");
        string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, noBackPattern);
        sw.Stop();
        Console.WriteLine($"Match: {Regex.IsMatch(input, noBackPattern)} in {sw.Elapsed}");
    }
}
// The example displays output like the following:
//       With backtracking:
//       Match: False in 00:00:27.4282019
//
//       Without backtracking:
//       Match: False in 00:00:00.0001391

Imports System.Text.RegularExpressions

Module Example4
    Public Sub Run()
        Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
        Dim matched As Boolean
        Dim sw As Stopwatch

        Console.WriteLine("With backtracking:")
        Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, backPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
        Console.WriteLine()

        Console.WriteLine("Without backtracking:")
        Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, noBackPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       With backtracking:
'       Match: False in 00:00:27.4282019
'       
'       Without backtracking:
'       Match: False in 00:00:00.0001391

Asserzioni retrovisive

.NET include due costrutti del linguaggio, (?<=sottoespressione) e (?<!sottoespressione), che corrispondono al carattere o ai caratteri precedenti nella stringa di input. Entrambi gli elementi del linguaggio sono asserzioni di larghezza zero; vale a dire, determinano se il carattere o i caratteri che precedono immediatamente il carattere corrente possono corrispondere a sottoespressione, senza avanzare né retrocedere.

(?<= sottoespressione) è un'asserzione lookbehind positiva, ovvero il carattere o i caratteri prima della posizione corrente devono corrispondere a sottoespressione. (?<! sottoespressione) è un'asserzione lookbehind negativa, ovvero il carattere o i caratteri prima della posizione corrente non devono corrispondere a sottoespressione. Le asserzioni lookbehind, sia positive che negative, sono particolarmente utili quando la sottoespressione è un sottoinsieme della sottoespressione precedente.

L'esempio seguente usa due modelli di espressione regolare equivalenti che convalidano il nome utente in un indirizzo di posta elettronica. Il primo modello è soggetto a una riduzione delle prestazioni a causa di un utilizzo eccessivo del backtracking. Il secondo modello modifica la prima espressione regolare sostituendo un quantificatore annidato con un'asserzione lookbehind positiva. Nell'output dell'esempio viene visualizzato il tempo di esecuzione del metodo 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: {result} in {sw.Elapsed}");

        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"Match with Lookbehind: {result} in {sw.Elapsed}");
    }
}
// The example displays output similar to the following:
//       Match: True in 00:00:00.0017549
//       Match with Lookbehind: True in 00:00:00.0000659

Module Example5
    Public Sub Run()
        Dim sw As Stopwatch
        Dim input As String = "test@contoso.com"
        Dim result As Boolean

        Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)

        Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays output similar to the following:
'       Match: True in 00:00:00.0017549
'       Match with Lookbehind: True in 00:00:00.0000659

Il primo criterio di espressione regolare, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, è definito nel modo illustrato nella tabella seguente.

Il secondo criterio di espressione regolare, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, usa un'asserzione lookbehind positiva e viene definito come illustrato nella tabella seguente.

Asserzioni di lookahead

.NET comprende due costrutti del linguaggio, (?=sottoespressione) e (?!sottoespressione), che corrispondono al carattere o ai caratteri successivi nella stringa di input. Entrambi gli elementi del linguaggio sono asserzioni di larghezza zero; vale a dire, determinano se il carattere o i caratteri che seguono immediatamente il carattere corrente possono corrispondere a sottoespressione, senza avanzare né retrocedere.

(?= sottoespressione) è un'asserzione lookahead positiva, ovvero il carattere o i caratteri dopo la posizione corrente devono corrispondere a sottoespressione. (?! sottoespressione) è un'asserzione lookahead negativa, ovvero il carattere o i caratteri dopo la posizione corrente non devono corrispondere a sottoespressione. Le asserzioni lookahead positive e negative sono entrambe particolarmente utili quando sottoespressione è un subset della sottoespressione successiva.

Nell'esempio seguente vengono utilizzati due modelli di espressione regolare equivalenti per verificare un nome di tipo completo. Il primo modello è soggetto a una riduzione delle prestazioni a causa di un utilizzo eccessivo del backtracking. Il secondo modello modifica la prima espressione regolare sostituendo un quantificatore annidato con un'asserzione lookahead positiva. Nell'output dell'esempio viene visualizzato il tempo di esecuzione del metodo 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($"{result} in {sw.Elapsed}");

        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"{result} in {sw.Elapsed}");
    }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866

Imports System.Text.RegularExpressions

Module Example6
    Public Sub Run()
        Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
        Dim result As Boolean
        Dim sw As Stopwatch

        Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)

        Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       False in 00:00:03.8003793
'       False in 00:00:00.0000866

Il primo criterio di espressione regolare, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, è definito nel modo illustrato nella tabella seguente.

Il secondo modello di espressione regolare, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, usa un'asserzione di anticipazione positiva. e viene definito come illustrato nella tabella seguente.

Considerazioni generali sulle prestazioni

I suggerimenti seguenti non servono specificamente a evitare un backtracking eccessivo, ma possono contribuire ad aumentare le prestazioni dell'espressione regolare:

1. Precompilare modelli usati di frequente. Il modo migliore per eseguire questa operazione consiste nell'usare il generatore di origini delle espressioni regolari per la precompilazione. Se il generatore di origini non è disponibile per l'app, ad esempio non si ha come destinazione .NET 7 o versione successiva o non si conosce il modello in fase di compilazione, usare l'opzione RegexOptions.Compiled.

2. Memorizzare nella cache oggetti Regex usati di frequente. Ciò si verifica in modo implicito quando si usa il generatore di origini. In caso contrario, creare un oggetto Regex e archiviarlo per il riutilizzo, anziché usare i metodi Regex statici o creare e rimuovere un oggetto Regex.

3. Avviare l'abbinamento a partire da un offset. Se si è certi che le corrispondenze inizieranno sempre oltre un determinato offset nel modello, passare l'offset usando un overload come Regex.Match(String, Int32). In questo modo si ridurrà la quantità di testo che il motore deve prendere in considerazione.

4. Raccogliere solo le informazioni necessarie. Se è sufficiente sapere solo se si verifica una corrispondenza ma non dove si verifica la corrispondenza, preferire Regex.IsMatch. Se ti serve solo sapere quante volte qualcosa corrisponde, è preferibile usare Regex.Count. Se è sufficiente conoscere i limiti di una corrispondenza, ma non sono necessarie informazioni sulle acquisizioni di una corrispondenza, preferire l'uso di Regex.EnumerateMatches. È consigliabile ridurre al minimo la quantità di informazioni che il motore deve fornire.

5. Evitare acquisizioni non necessarie. Le parentesi nel modello formano un gruppo di acquisizione per impostazione predefinita. Se non sono necessarie acquisizioni, specificare RegexOptions.ExplicitCapture o usare invece gruppi non di acquisizione. Questo evita al motore di tenere traccia di queste acquisizioni.

Vedi anche

• Espressioni regolari .NET
• Linguaggio di espressioni regolari - Riferimento rapido
• Quantificatori
• Costrutti di alternanza
• Costrutti di raggruppamento