由 Eyal Schneider 於 2009 年 5 月 21 日發布 java.util.regex 套件在 Java 版本 1.4 中新增。它是一個非常強大的工具，需要成為大師才能正確使用它。即使
正規表示式為真，如果寫得不巧妙，它也可能會非常慢。如果您想了解問題的原因，請繼續閱讀，或捲動到頁面末尾，您將找到 10 個提高 Java 中正規表示式效能的有用技巧。
真的有那麼慢嗎？
假設我們只想選擇包含字元“a”和“b”序列的行。正確的解決方案可能是：
(a*b*)* 但是，如果您使用字串“aaaaaaaaaaaaaaaaaaaaaaaaaaaaax”運行表達式，則需要幾分鐘才能完成並報告沒有匹配項！當然，在這種情況下最好的正規表示式是：
(a|b)* 在我的機器上使用相同的字串花費不到一毫秒。顯然這裡有效能問題。
為什麼會發生這種情況？
與大多數正規表示式引擎一樣，Java 使用 NFA（非確定性有限自動機）方法。引擎一一掃描正規表示式組件，並相應地遍歷輸入字串。如果遇到“死胡同”，他還可以回到起點尋找合適的替代方案。透過使用常規結構（例如量詞（
*、+、?）和交替（例如
a|b|c|d））可以獲得替代結果。這種研究技術稱為回溯。在上面可怕的例子中，引擎實際上會將符號“a”的所有系列分解為更小的系列，直到它意識到沒有匹配。此範例顯示回溯演算法如何得出指數時間估計（取決於輸入字串的長度）。這也顯示了 NFA 的一個重要屬性：總是會有最壞的情況幾乎與模式相符。如果找到匹配項，則搜尋停止。正規表示式中使用的另一個主要方法是 DFA（確定性有限自動機）。在這種方法中，正規表示式實際上建立了一個自動機，用於逐個字元地遍歷輸入字串而無需回溯。無論正規表示式的複雜性如何，這都會為整個輸入提供線性時間。DFA 模擬並行掃描，而不是順序掃描字串以查找匹配項（如 NFA 中）。那麼為什麼 Java（以及 .NET、Perl、Python、Ruby、PHP 等）使用 NKA 而不是表現更好的 DKA？原因是NKA具有許多顯著的優勢：
- 編譯速度更快並且需要更少的內存
- 允許一些有用的功能（詳細資訊請參閱Sun 的教學）：
- 群組捕獲和反向鏈接
- 位置檢查
- 擴展量詞（貪婪和惰性）
值得注意的是，流行術語 NKA 和 DKA 在正規表示式上下文中使用時並不精確。理論上，這兩種模型具有相同的計算能力。這意味著您無法在一個自動機模型中編寫在另一個自動機模型中無法表達的正規表示式。在實踐中，需要更多的功能，以便兩種類型的實現在語義上有所不同。NKA 引擎提供了更大的靈活性，使其在運算能力上優於 DKA。由於 DFA 的速度和 NFA 的獨特功能，還有 2 種「預製」方式來實現正規表示式。有些實作使用這兩種類型（例如 GNU egrep，它在運行時選擇特定引擎），而某些實作則設法實現真正的混合版本（例如 Tcl regexps），並具有所有優點。
建議
以下是有關如何避免 Java 中正規表示式效率問題的一些技巧。其中許多旨在減少回報。
1）預編譯
陳腔濫調，但值得一提。如果多次使用正規表示式，請務必提前編譯它：
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2）惰性量詞與貪婪量詞
預設情況下，量詞 (
* + ? ) 是貪婪的。這意味著它們開始匹配最長的可能序列，然後在必要時逐漸返回。如果您事先知道匹配通常會很短，則應該使用惰性量詞。他們從最小的匹配開始，並在必要時進一步移動。假設我們只想尋找與序列“hello”相符的行。常規的
.*hello.*會正確執行所有操作，但如果我們知道「hello」通常出現在更靠近文字開頭的位置，那麼
.*?hello.*平均會運行得更快。
3）盡量使用超貪心量詞
與影響性能但不影響正規行為的惰性量詞不同，超貪婪量詞實際上可以改變正規表示式的意思。當使用
*+而不是
*時，第一個匹配將是貪婪的（即盡可能最大，就好像它只是 * 一樣），但如果失敗則不會有回退，即使這會導致整個搜索失敗。什麼時候有用？假設我們需要尋找引號中的文字。常規的
\"[^\"]*\"可以正常工作。但是，在負數情況下它會產生不必要的縮排（例如，“bla bla bla）。使用
\"[^\"]*+\ "將消除回滾而不改變表達式的含義。獨立分組可達到相同的效果並提供更多控制（請參閱
Sun 的教學）。
4）避免集體抓捕
預設情況下，括號中的任何表達式都被視為一個群組。這對性能影響很小。
盡可能以(?:而不是
( )開頭，使您的組「不可捕獲」。
5）明智地使用交錯
當使用交錯時（例如
Paul|Jane|Chris），引擎嘗試匹配選項的順序與它們出現的順序相同。您可以利用此功能並將最常見的選項放在靠近開頭的位置。這將改善平均積極回應時間。
6）避免歧義
以最小化輸入字串中不同匹配項的數量的方式編寫正規表示式。例如：文章開頭給出的 正規表示式
(a*b*)*允許字串「aabb」有太多的解釋方式：而
(a|b)*
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp 這對於減少
近似匹配情況下的回報非常重要。
7) 預覽
預覽可讓您新增對目前位置左側/右側序列的限制。特別是，透過負向前瞻，您可以搜尋不包含某些序列的行（如果沒有這個我們該怎麼辦！）。這如何有助於提高生產力？假設我們要從連結標記中取得 URL。考慮以下正規表示式：
a .* href=(\S*).*/ 對於常規標記，如果文字包含「href」屬性，則此表達式僅符合位址（\S 用於分隔符號之外的所有字元）。但在一些不尋常的標籤上，例如，會發生回溯。例如：「a href= href=href=.... href=某事。” 當將表達式中的「.*」替換為與「href」不符的內容時，下列正規表示式將防止這種情況發生：
a ((?!href).)* href=(\S*)((?!href).)*/
8) 指定長度
Java 包含一個正規表示式優化器，它根據從正規表示式獲得的最小和最大長度檢查輸入字串的長度。這允許您在某些情況下立即停止搜尋。為了協助此機制，應盡可能指定重複次數（例如，
[01]{6}匹配所有六個字元長的二進位字串）。
9）選擇相同的行
有時相同的字串隱藏在群組或替代項中：
(hello|hell|heel) 此表達式可以簡化為：
he(llo|ll|el) 透過這樣做，我們為正規表示式優化器提供了更多資訊。
10) 測試你的正規表示式
當正規表示式用於效能關鍵型應用程式時，首先測試正規表示式可能是明智的做法。編寫一個微基準測試您對各種輸入資料的表達。請務必測試不同長度的數據以及與您的樣本密切匹配的數據。
連結：
http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -表達處理/
GO TO FULL VERSION