失控的正規表示式：過多重複

但如果你對重複 one 數百萬次的字串使用這個正規表示式，你可能會遇到正規表示式引擎的限制，它被設計成在嘗試記住所有回溯位置時，避免記憶體用盡。這可能會阻止引擎找到極長的配對。

上述範例透過使用 擷取群組 讓情況變得更糟。在成功配對的結尾，擷取群組將會包含字串中 one 或 two 的最後一個出現。但在配對嘗試期間，它也會在每次反覆運算中包含 one 或 two 的最新配對。這會在群組的每次反覆運算以及每次群組被回溯時，為正規表示式引擎造成額外的負擔。

使用非擷取和原子群組進行最佳化

我們可以最佳化這個正規表示式，以減少正規表示式引擎必須執行的負擔。這些都是適用於所有正規表示式的良好技巧。即使你只會在效能差異難以衡量的較短字串上使用正規表示式，你也應該將它們視為良好的編碼習慣。

首先，只有在真的想要擷取正規表示式配對的一部分時，才使用擷取群組。否則，你隨時可以使用非擷取群組。將沒有反向引用的擷取群組轉換為非擷取群組，永遠不會改變正規表示式應該配對的內容。因此 ^(?:one|two)*done$ 是我們的第一次最佳化。

在這種情況下，這兩個選項是互斥的。two 永遠不會在 one 已配對的位置配對。因此，所有回溯都是不必要的。我們可以使用 原子群組 告訴正規表示式引擎：^(?>one|two)*done$。現在，正規表示式引擎每次重複群組時，都會捨棄交替運算子的回溯位置。它不再嘗試在 one 已配對的位置配對 two。

使用佔有量詞進行最佳化

但是量詞 * 仍然會回溯。^(?>one|two)*done$ 仍然會在量詞回溯時，在 one 已配對的每個位置嘗試配對 done。為了解決這個問題，我們可以讓量詞 佔有：^(?>one|two)*+done$。這個正規表示式完全不會回溯。

這個正規表示式是否真的可以配對任意長度的 oneoneone…done 序列，取決於正規表示式引擎如何實作佔有量詞。如果佔有量詞根本不儲存回溯位置，那麼它就可以。但在某些正規表示式風格中，佔有量詞是撰寫 ^(?>(?>one|two)*)done$ 的另一種方式。在這種情況下，量詞仍然會儲存所有回溯位置，只會在正規表示式引擎離開外部原子群組時將它們捨棄。當 done 無法配對時，這確實會提升效能。但如果正規表示式引擎受到量詞可以儲存的回溯位置數量限制，它就不允許更長的成功配對。

消除不必要的群組

比將擷取群組轉換為非擷取或原子群組更好的方法是消除不必要的群組。人們有時會不必要地將正規表示式符號分組，因為他們不了解正規表示式中運算子的優先順序。交替運算子具有最低的優先順序。它會在正規表示式或包含它的群組中，交替位於其左側和右側的所有內容。量詞具有較高的優先順序。它只重複其前面的符號或群組。

因此，one|two* 會比對 one、tw、two、twoo、twooo 等。我們需要群組來重複交替，而不仅仅是最後一個 o。但是，我們不需要在替代方案周圍添加額外的群組。在 (?:(?:one)|(?:two))* 中的兩個巢狀群組是不必要的。

(?:[ab])+ 也有不必要的群組。字元類別被視為單一正規表示式符號。量詞可以直接重複它：[ab]+。

這些不必要的群組會產生多大的影響取決於正規表示式引擎。如果您遵循使用非擷取群組的建議，那麼引擎可能會優化掉不必要的群組。但是，如果您有不需要的擷取群組，它就無法做到這一點。正規表示式引擎無法知道您是否需要在之後擷取由擷取群組比對的文字，因此它無法移除它們。

重複單一符號

理論上，^(?:a|b|c)+$ 和 ^[abc]+$ 是相同的。實際上，大多數回溯引擎執行後者的速度要快得多。字元類別可以同時嘗試兩個字元。它不需要像交替運算子那樣回溯來嘗試其他字元。字元類別的每次迭代都完全比對一個字元。雖然量詞可能需要回溯，但它不需要回溯位置來執行此操作。它只需要記住迭代次數。它可以通過在字串中向後移動一個字元並遞減迭代次數來回溯。這使得 ^[abc]+$ 可以比對任何長度的字串。

"(?:[^"]|\\.)*" 是一個簡化的解決方案，用於比對雙引號字串，如果雙引號是由反斜線跳脫，則可以包含雙引號。我們允許換行，並假設 點 與換行相符。

上述正規表示法在於它比對所有雙引號字串且沒有其他內容的意義上是正確的。但它很簡化，因為它的效能很差。至少它使用非擷取群組。如果我們翻轉兩個選項，我們可以使用原子群組（請記住正規表示法引擎是 急切的）。但是，除非正規表示法引擎具有完全不儲存回溯位置的佔有量化詞，否則我們無法讓這個正規表示法比對數百萬個字元的雙引號字串，只要我們重複字串中每個字元的群組。

要最佳化這個正規表示法，我們需要重複否定字元類別："(?:[^"\\]+|\\.)*"。這允許正規表示法快速比對字串中未跳脫字元的執行。由於這些字元比跳脫字元更常見，這會大幅減少正規表示法引擎需要記住的回溯位置數量。外層群組只會對每個未跳脫字元的執行重複一次，並對每個跳脫字元重複一次。如果結尾引號比對失敗，兩個量化詞仍會回溯。但大多數反覆運算將是內部量化詞，它可以更快地回溯。

請注意，否定的字元類別現在包含反斜線。這確保兩個選項互斥。這很重要。如果您注意 災難性回溯 主題，您會注意到類似的巢狀量化詞模式。儘管我們的正規表示法在結尾引號比對失敗時會回溯，但它會線性回溯，因為第二個選項永遠無法比對第一個選項比對的字元。

我們可以將此最佳化再進一步。我們不需要重複非跳脫字元的執行群組，也不需要在跳脫和非跳脫字元之間交替。我們只需要群組來處理跳脫字元即可。"[^"\\]*(?:\\.[^"\\]*)*" 將雙引號字串視為一系列零個或多個非跳脫字元，後接零個或多個跳脫字元，而每個跳脫字元後又接零個或多個非跳脫字元。現在，群組僅記住字串中每個非跳脫字元的單一反向追蹤位置。這使正規表示式能夠匹配幾乎任何長度的字串。如果字串包含數百萬個跳脫字元，它只會遇到正規表示式引擎限制。如果關閉引號無法匹配，它將反向追蹤。但所有反向追蹤嘗試都將立即失敗，因為群組以 \\. 開頭，而 \\. 與 [^"\\]* 互斥。

如果正規表示式引擎支援原子群組或佔有量詞，那麼我們可以使用 "(?>[^"\\]*(?>\\.[^"\\]*)*)" 或 "[^"\\]*+(?:\\.[^"\\]*+)*+" 為其錦上添花。這兩個正規表示式在嘗試匹配關閉雙引號時會捨棄所有反向追蹤位置。因此，它們根本不會反向追蹤。