Java正則表達式庫是否針對任何字符進行優化？

Question

我有一個匹配正則表達式的包裝類。顯然，你可以像這樣編譯一個正則表達式爲Pattern。

Pattern pattern = Pattern.compile(regex); 

但假設我使用.*來指定任意數量的字符。所以它基本上是一個通配符。

Pattern pattern = Pattern.compile(".*"); 

模式優化是否總是返回true並且沒有真正計算任何東西？或者我應該讓我的包裝實現優化？我這樣做是因爲我可以在一個流程中輕鬆處理數十萬個正則表達式操作。如果一個正則表達式參數爲null我把它合併到.*

Answer 1

在你的情況，我可以只使用一個佔有慾量詞，以避免任何回溯：

.*+ 

Java的模式匹配引擎有幾個優化其處置，並可以自動應用它們。

以下是Cristian Mocanu's writes in his Optimizing regular expressions in Java大約類似於.*情況：

Java的正則表達式引擎無法優化表達.*abc.*。我預計它會在輸入字符串中搜索abc，並很快報告失敗，但事實並非如此。在相同的輸入字符串上，使用String.indexOf("abc")的速度比我改進的正則表達式快三倍。似乎只有當已知的字符串在其開頭或其內部的預定位置處正確時，引擎才能優化該表達式。例如，如果我將表達式重新編寫爲.{100}abc.*，則引擎的匹配速度會快十倍以上。爲什麼？因爲現在強制字符串abc位於字符串內部的已知位置（應該在其之前有一百個字符）。

一些hints on Java regex optimization from the same source：

• 如果正則表達式包含必須存在於輸入字符串（或者整個表達式將不匹配）的字符串時，發動機有時可以搜索該字符串優先，如果未找到匹配則報告失敗，而不檢查整個正則表達式。
• 自動優化正則表達式的另一個非常有用的方法是讓引擎根據正則表達式檢查輸入字符串的長度與期望的長度。例如，表達式\d{100}在內部進行了優化，以便如果輸入字符串的長度不是100個字符，則引擎將報告失敗而不評估整個正則表達式。
• 不要在分組或更改中隱藏強制字符串，因爲引擎將無法識別它們。如果可能，指定要匹配的輸入字符串的長度也是有幫助的
• 如果您要在程序中多次使用正則表達式，請務必使用Pattern.compile()而不是直接編譯該模式Pattern.matches()。
• 還要記住，您可以通過調用方法reset()來重新使用Matcher對象作爲不同的輸入字符串。
• 小心輪換。像(X|Y|Z)這樣的正則表達式因緩慢而聲名顯着，所以請留意。首先，交替順序的數量，所以在前面放置更常見的選項，以便他們可以更快地匹配。另外，嘗試提取常見模式;例如，而不是(abcd|abef)使用ab(cd|ef)。
• 無論何時您使用否定字符類別來匹配別的東西，請使用所有格量詞：而不是[^a]*a使用[^a]*+a。
• 不匹配的字符串可能會導致您的代碼凍結比包含匹配的代碼更頻繁。 請記住總是首先使用不匹配的字符串測試您的正則表達式！
• 當心一個known bug #5050507（當正則表達式Pattern類會引發的StackOverflowError），如果遇到此錯誤，請嘗試重寫正則表達式或將其分割成幾個子表達式和分開運行的。後一種技術有時甚至可以提高性能。

• 而不是懶點匹配，使用緩和貪婪標記（例如(?:(?!something).)*）或unrolling the loop techinque（今天得到了投票，不知道爲什麼）。

  不幸的是，你不能總是依靠引擎來優化正則表達式。在上面的例子中，正則表達式實際上匹配得相當快，但是在很多情況下，表達式太複雜，輸入字符串太大，引擎不能優化。