正則表達式匹配需要很長時間才能執行

我寫了一個正則表達式，將文件路徑解析爲不同的組（DRIVE，DIR，FILE，EXTENSION）。正則表達式匹配需要很長時間才能執行

^((?<DRIVE>[a-zA-Z]):\\)*((?<DIR>[a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+)))\\)*(?<FILE>([a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+))\.(?<EXTENSION>[a-zA-Z0-9]{1,6})$))

我在C＃中做了一個測試。當我想測試的路徑是正確的。結果非常快，這就是我想要的。

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor.csproj";

=> OK

但是，當我嘗試，我知道這將不匹配的路徑來測試，這樣的：

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor?!??????";

=> BUG

測試當我稱這部分代碼時凍結

Match match = s_fileRegex.Match(path);

當我查看我的Process Explorer時，發現處理器的100％掛起了進程QTAgent32.exe。這是什麼意思？

來源

2010-08-04 RedPaladin

您在驗證之前是否考慮過[解析路徑]（http://stackoverflow.com/questions/3386258/parsing-a-given-path-in-c）？ – kennytm 2010-08-04 07:44:08

爲什麼不在Path類中使用有用的方法？沒有必要使用正則表達式來提取這些信息。 – Jens 2010-08-04 07:46:28

RegEx真的是走錯路。我仍然想知道爲什麼這RegEx殺死regexr.com：> – atamanroman 2010-08-04 07:48:02

您遇到的問題被稱爲catastrophic backtracking，這是由於正則表達式可以匹配字符串的開頭的大量方式，由於.NET中的回溯正則表達式引擎而導致性能降低。

我覺得你在正則表達式中使用的太頻繁了*。 *並不意味着「連接」 - 它表示「0次或更多次」。例如不應該有這裏*：

((?<DRIVE>[a-zA-Z]):\\)*

應該有最多一個驅動器規格。您應該在這裏使用?，否則，如果您希望驅動器規格是強制性的，則根本不使用量化器。類似地，在正則表達式中，量詞不正確的地方似乎還有其他地方。

來源

2010-08-04 07:54:14

好的答案，tyvm :)（+1）也許你可以把這個鏈接在你的答案，這很好解釋發生這種情況： http：// www.regular-expressions.info/catastrophic.html – atamanroman 2010-08-04 07:56:57

@fielding：當然。完成！ – 2010-08-04 08:00:05

爲什麼不只是使用System.IO.Path函數？

驅動器：http://msdn.microsoft.com/en-us/library/system.io.path.getpathroot.aspx
目錄：http://msdn.microsoft.com/en-us/library/system.io.path.getdirectoryname.aspx負什麼是得到了驅動
文件名：http://msdn.microsoft.com/en-us/library/system.io.path.getfilenamewithoutextension.aspx
擴展：http://msdn.microsoft.com/en-us/library/system.io.path.getextension.aspx

來源

2010-08-04 07:45:51 Amber

我只是使用FileInfo和Path類來獲取信息。

如果你選擇使用正則表達式，然後注意，正則表達式不匹配所有合法的文件名：有一大堆合法的文件名令牌從你的正則表達式中丟失。

來源

2010-08-04 07:53:53

馬克拜爾是正確的，該問題的原因是catastrophic backtracking，但它是導致問題的最後一部分，而不是與驅動器號相匹配的位。

例如，在

(?<FILE> 
    ([a-zA-Z0-9_]+ 
    (
     ([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+) 
    | 
     ([a-zA-Z0-9_]+) 
    )\. 
    (?<EXTENSION>[a-zA-Z0-9]{1,6}) 
    $) 
)

你可以看到，

([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+) 
| 
([a-zA-Z0-9_]+)

可以用多種不同的方式，將與文件名長度成倍增加匹配相同的字符串。

當正則表達式的擴展部分無法匹配時，正則表達式引擎會爲文件名部分回溯並嘗試一個不同的排列，希望這可以使擴展部分匹配 - 這當然不會發生，但正則表達式引擎無法弄清楚。當被要求在你提供的路徑上測試正則表達式時，RegexBuddy在1.000.000次迭代後中止匹配嘗試。 C＃正則表達式引擎將持續運行，直到它耗盡所有排列，在此期間將CPU固定在100％。

爲了解決這個問題，通常需要避免重複元素的重複，以避免匹配相同事物的變化，並且可能包含atomic groups中的匹配部分，如果後面的正則表達式不會被回溯到失敗。

就你而言，最好使用正確的工具來完成這個工作，而這些工具就是.NET的路徑操作函數。

來源

2010-08-04 08:07:56

非常感謝您的回覆。您有權利，我將使用.NET框架上提供的功能！ – RedPaladin 2010-08-04 08:16:26

正則表達式匹配需要很長時間才能執行

回答

相關問題