回溯 (Backtracking) 會在規則運算式模式包含選擇性的數量詞或替代建構，且規則運算式引擎返回之前儲存的狀態繼續搜尋相符項目時發生。 回溯是規則運算式的核心能力，可讓運算式功能強大且靈活，並且比對非常複雜的模式。 但同時，這項強大功能需付出相當的代價。 回溯經常是影響規則運算式引擎之效能最重要的一項因素。 所幸，開發人員可以控制正規表示式引擎的行為，以及其使用回溯的方式。 本文將說明回溯的運作方式，以及您如何控制它。
警告
若在不受信任的輸入下不受限制地使用， System.Text.RegularExpressions 應用程式可能會遭受 阻斷服務攻擊。 請參閱 .NET 中正則表達式的最佳實務，以獲得如何在不受信任輸入下安全使用 .NET 正規表達式的指引。
不進行回溯的線性比較
如果規則運算式模式沒有選擇性數量詞或替代建構，則規則運算式引擎會以線性時間執行。 也就是說，規則運算式引擎比對模式中的第一個語言項目與輸入字串中的文字之後，會嘗試比對模式中的下一個語言項目與輸入字串中的下一個字元或字元群組。 這個過程會持續進行，直到比對成功或失敗。 無論在哪一種情況下，規則運算式引擎都會在輸入字串中每次前進一個字元。
下列範例提供一個實例。 正規表示式 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($"{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
雖然這個規則運算式包括數量詞 {2}，但仍然會以線性方式進行評估。 規則運算式引擎不會回溯，因為 {2} 不是選擇性的數量詞，它指定了確切的數字，而不是前面的子運算式必須比對的可變次數。 因此，規則運算式引擎會嘗試比對規則運算式模式與輸入字串，如下表所示。
| 作業 | 模式中的位置 | 字串中的位置 | 結果 |
|---|---|---|---|
| 1 | e | 需要簧片（索引 0） | 沒有相符的項目。 |
| 2 | e | "eeding a reed"（索引 1） | 可能符合的結果。 |
| 3 | e{2} | "eding a reed" (索引 2) | 可能符合的結果。 |
| 4 | \w | 「敲擊簧片」（索引 3） | 可能符合的結果。 |
| 5 | \b | 「ing a reed」 （索引 4） | 可能的比對失敗。 |
| 6 | e | "eding a reed" (索引 2) | 可能符合的結果。 |
| 7 | e{2} | 「敲擊簧片」（索引 3） | 可能的比對失敗。 |
| 8 | e | 「敲擊簧片」（索引 3） | 比對失敗。 |
| 9 | e | 「ing a reed」 （索引 4） | 沒有相符的項目。 |
| 10 | e | "ng a reed" (索引 5) | 沒有相符的項目。 |
| 11 | e | 「g a reed」（索引 6） | 沒有相符的項目。 |
| 12 | e | " 蘆葦" (索引 7) | 沒有相符的項目。 |
| 13 | e | 蘆葦（索引 8） | 沒有相符的項目。 |
| 14 | e | " 蘆葦" (索引 9) | 沒有相符的項目。 |
| 15 | e | 蘆葦 | 沒有相符項目 |
| 16 | e | "eed" (索引 11) | 可能符合的結果。 |
| 17 | e{2} | "ed" (索引 12) | 可能符合的結果。 |
| 18 | \w | "d" (索引 13) | 可能符合的結果。 |
| 19 | \b | "" (索引 14) | 相符。 |
如果規則運算式模式未包含選擇性數量詞或交替建構，則比對規則運算式模式與輸入字串所需的比較次數上限，約相當於輸入字串中的字元數。 在這個案例中，規則運算式引擎會使用 19 項比較找出這 13 個字元字串中可能的相符項目。 換句話說，如果沒有選擇性數量詞或交替建構，規則運算式引擎就會以近似線性時間執行。
含有可選量詞或交替結構的回溯
當規則運算式包含選擇性數量詞或替代建構時，輸入字串的評估就不再是線性。 與非確定有限狀態自動機 (NFA) 引擎比對的模式是由規則運算式中的語言元素所引導，而不是由輸入字串中要比對的字元引導。 因此，規則運算式引擎會嘗試完全比對選擇性或可替代的子運算式。 當規則運算式引擎前進到子運算式中的下一個語言項目且比對失敗時，它可能會捨棄成功比對的一部分，並且返回之前儲存的狀態，以便完整比對規則運算式與輸入字串。 這個返回之前儲存狀態尋找符合結果的程序，就稱為回溯 (Backtracking)。
例如，想想規則運算式模式 .*(es)，它會比對字元 "es" 與其前面的所有字元。 如下列範例中所示，如果輸入字串為 "Essential services are provided by regular expressions."，則模式會比對整個字串直到 (且包含) "expressions" 中的 "es" 為止。
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" 與 "expressions" 中的第二個 "e"，並且尋找符合的結果。
它會將模式中的 "s" 與已比對成功的 "e" 字元後面的 "s" 進行比較（也就是 "expressions" 中的第一個 "s"）。 比對將會成功。
當您使用回溯時，比對規則運算式模式與長度 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"（以下稱為比對結果 1）、"aa"（比對結果 2）、"aaa"（比對結果 3）和 "aaaa"（比對結果 4）時的狀態資訊。回到先前儲存的第 4 個相符項目。 它判定有一個額外的「a」字元可分配給另一個擷取群組。 最後，它會檢查是否已到達字串結尾。 由於字串中還有一個額外的字元，因此比對失敗。 這次未成功的比對需要 4 次比較。 到目前為止，總共執行了 13 次比較。
會回到先前儲存的第 3 筆匹配結果。 它判定有兩個額外的「a」字元要指定給另一個擷取群組。 然而，字串結尾測試失敗。 接著它會回到第 3 次比對，並嘗試在另外兩個擷取群組中比對兩個額外的 "a" 字元。 字串結尾測試仍然失敗。 這些失敗的比對需要經過 12 次比較。 到目前為止，總共執行了 25 次比較。
輸入字串與規則運算式的比較會依照這種方式繼續進行，直到規則運算式引擎嘗試過所有可能的比對組合，然後得到沒有符合的結果這個結論。 由於巢狀數量詞的關係，這個比較是 O(2n) 或指數運算，其中 n 是輸入字串中的字元數。 這表示，在最糟的情況下，包含 30 個字元的輸入字串約需要進行 1,073,741,824 次比較，而包含 40 個字元的輸入字串約需要進行 1,099,511,627,776 次比較。 如果您使用這類長度甚至更長的字串，則規則運算式方法處理不符合規則運算式模式的輸入時，可能需要相當長的時間才能完成。
回溯控制
回溯可讓您建立強大且靈活的正規表示式。 不過，如前一節所示，這些好處可能伴隨著差到難以接受的效能表現。 為了避免大量回溯，當您具現化 Regex 物件或呼叫靜態規則運算式比對方法時，應該定義逾時間隔。 下一節將討論這個部分。 此外，.NET 支援三種可限制或抑制回溯的正規表示式語言元素，能以幾乎沒有或完全沒有任何效能負擔的方式支援複雜的正規表示式：原子群組、後顧判斷提示和前瞻判斷提示。 如需各語言元素的詳細資訊，請參閱 分組建構。
非回溯正則表達式引擎
如果您不需要使用任何需要回溯功能的建構（例如前後查找、反向參照或原子群組），請考慮使用 RegexOptions.NonBacktracking 模式。 此模式的設計目的是要與輸入長度成正比的時間執行。 如需詳細資訊，請參閱 非回溯模式。 您也可以設定逾時值。
限制輸入的大小
除非輸入非常大，否則某些規則運算式具有可接受的效能。 如果在您的情境中，所有合理的文字輸入都已知不會超過某個長度，請考慮在套用正規表示式之前，先拒絕超過該長度的輸入。
指定逾時間隔
您可以設定逾時值，表示規則運算式引擎開始搜尋單一符合項目到放棄嘗試並擲回 RegexMatchTimeoutException 例外狀況之前的最長間隔。 您可藉由將 TimeSpan 值提供給執行個體正則運算式的 Regex(String, RegexOptions, TimeSpan) 建構函式，來指定逾時間隔。 此外，每一個靜態模式比對方法都有 TimeSpan 參數的多載，可讓您指定逾時值。
如果您未明確設定逾時值，則會如下決定預設逾時值:
- 採用應用程式層級的逾時值（若有）。 這可以是任何套用至應用程式定義域 (在其中具現化 Regex 物件或進行靜態方法呼叫) 的逾時值。 您可以呼叫 AppDomain.SetData 方法來設定整個應用程式的逾時值，以將 TimeSpan 值的字串表示指派給
REGEX_DEFAULT_MATCH_TIMEOUT屬性。 - 如果未設定整個應用程式範圍的逾時值，則使用值 InfiniteMatchTimeout。
預設情況下，逾時間隔設為 Regex.InfiniteMatchTimeout，因此規則運算式引擎不會逾時。
重要
未使用 RegexOptions.NonBacktracking 時，如果您的規則運算式仰賴回溯或處理不受信任的輸入，我們建議您一律設定逾時期間。
RegexMatchTimeoutException 例外狀況表示規則運算式引擎在指定的逾時間隔內找不到相符項目，但不會指出擲回例外狀況的原因。 原因可能是回溯過多，但也可能是考量到擲回例外狀況當時的系統負載，逾時期間設定得太短。 當您處理例外狀況時，可以選擇放棄對輸入字串的進一步比對，或增加逾時期間後重新嘗試比對作業。
例如，下列程式碼會呼叫 Regex(String, RegexOptions, TimeSpan) 建構函式來具現化逾時值為 1 秒的 Regex 物件。 正則表達式模式 (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 {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.
原子群組
(?>
子運算式)語言元素是原子群組。 它可防止回溯到子運算式中。 一旦此語言元素成功完成比對，它就不會在後續回溯時放棄其比對結果中的任何部分。 例如，在模式 (?>\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: {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
後行斷言
.NET 包含兩個語言元素：(?<=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: {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
第一個規則運算式模式 ^[0-9A-Z]([-.\w]*[0-9A-Z])*@的定義如下表所示。
| 模式 | 描述 |
|---|---|
^ |
從字串的開頭開始比對。 |
[0-9A-Z] |
比對英數字元。 這項比較不區分大小寫，因為 Regex.IsMatch 方法是使用 RegexOptions.IgnoreCase 選項呼叫。 |
[-.\w]* |
比對連字號、句號或單字字元出現零次、一次或多次。 |
[0-9A-Z] |
比對英數字元。 |
([-.\w]*[0-9A-Z])* |
比對出現零次或多次的零個或多個連字號、句號或文字字元組合，後面接著英數字元。 這是第一個擷取群組。 |
@ |
比對 "@" 記號。 |
第二個正規表示式模式 ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@ 使用正向後行判斷提示。 其定義方式如下表所示。
| 模式 | 描述 |
|---|---|
^ |
從字串的開頭開始比對。 |
[0-9A-Z] |
比對英數字元。 這項比較不區分大小寫，因為 Regex.IsMatch 方法是使用 RegexOptions.IgnoreCase 選項呼叫。 |
[-.\w]* |
比對連字號、句點或文字字元出現零次或多次的情況。 |
(?<=[0-9A-Z]) |
回看最後一個符合的字元，若其為英數字，則繼續比對。 請注意，英數字元是由句號、連字號和所有文字字元組成之集合的子集。 |
@ |
比對 "@" 記號。 |
前瞻斷言
.NET 包含兩個語言元素：(?=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($"{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
第一個規則運算式模式 ^(([A-Z]\w*)+\.)*[A-Z]\w*$的定義如下表所示。
| 模式 | 描述 |
|---|---|
^ |
從字串的開頭開始比對。 |
([A-Z]\w*)+\. |
比對一個字母字元 (A-Z)，後接零個或多個單字字元，此模式重複一次或多次，最後接著一個句號。 這項比較不區分大小寫，因為 Regex.IsMatch 方法是使用 RegexOptions.IgnoreCase 選項呼叫。 |
(([A-Z]\w*)+\.)* |
比對前一個模式零次或多次。 |
[A-Z]\w* |
比對一個英文字母字元，後面接著零個或多個單字字元。 |
$ |
在輸入字串結尾結束比對。 |
第二個正規表示式模式，^((?=[A-Z])\w+\.)*[A-Z]\w*$，使用了正向前瞻判斷提示。 其定義方式如下表所示。
| 模式 | 描述 |
|---|---|
^ |
從字串的開頭開始比對。 |
(?=[A-Z]) |
向前查看第一個字元，如果該字元是英文字母（A-Z），則繼續比對。 這項比較不區分大小寫，因為 Regex.IsMatch 方法是使用 RegexOptions.IgnoreCase 選項呼叫。 |
\w+\. |
比對後面接著句號的一個或多個文字字元。 |
((?=[A-Z])\w+\.)* |
比對由一個或多個單字字元後接句號所組成，且可重複零次或多次的模式。 開頭的字元必須是英文字母。 |
[A-Z]\w* |
比對一個英文字母字元，後面接著零個或多個單字字元。 |
$ |
在輸入字串結尾結束比對。 |
一般效能考量
下列建議並非特別用來防止過度回溯，但可能有助於提升規則運算式的效能:
預先編譯大量使用的模式。 若要這樣做，最好的方法是使用 規則運算式來源產生器 來預先編譯它。 如果您的應用程式無法使用來源產生器，例如您不是以 .NET 7 或更新版本為目標，或在編譯階段不知道模式，請使用 RegexOptions.Compiled 選項。
快取大量使用的 Regex 物件。 當您使用來源產生器時，這會隱含發生。 否則，請建立 Regex 物件並儲存以供重複使用，而不是使用靜態 Regex 方法，或建立並擲回 Regex 物件。
從偏移量開始比對。 如果您知道比對一定會從模式中的某個位移之後開始，請使用例如 Regex.Match(String, Int32) 這類多載，並將該位移傳入。 這會減少引擎需要考慮的文字數量。
只收集您需要的資訊。 如果您只需要知道相符項目是否發生，但不是相符項目發生的位置，則偏好 Regex.IsMatch。 如果您只需要知道某個項目符合條件的次數，建議使用 Regex.Count。 如果您只需要知道相符項目的界限，但不需要任何相符項目的擷取，則偏好使用 Regex.EnumerateMatches。 引擎需要提供的資訊越少越好。
避免不必要的擷取。 根據預設，模式中的括弧會形成擷取群組。 如果您不需要擷取，請改為指定 RegexOptions.ExplicitCapture 或使用 非擷取群組。 這樣一來，引擎就不必追蹤這些擷取內容。
