閱讀827 返回首頁    go 小米 go MIUI米柚

《正則表達式經典實例（第2版）》——2.15　避免失控重複

本節書摘來自異步社區《正則表達式經典實例（第2版）》一書中的第2章，第2.15節，作者： 【美】Jan Goyvaerts , Steven Levithan著，更多章節內容可以訪問雲棲社區“異步社區”公眾號查看

2.15　避免失控重複

問題描述
使用一個正則表達式來匹配一個完整的HTML文件，並檢查其中的html、head、title和body標簽是否進行了正確嵌套。當HTML文件中不擁有正確標簽的時候，該正則表達式必須能夠高效地宣布匹配失敗。

解決方案

<html>(?>.*?<head>)(?>.*?<title>)(?>.*?</title>)
(?>.*?</head>)(?>.*?<body[^>]*>)(?>.*?</body>).*?</html>
正則選項：不區分大小寫、點號匹配換行符
正則流派：.NET、Java、PCRE、Perl、Ruby

JavaScript和Python不支持固化分組。因此在這兩種正則流派中無法消除不必要的回溯。當使用JavaScript或者Python編程時，可以通過對這些標簽一一進行字麵文本查找來解決這個問題，在找到一個標簽之後，再在剩餘的目標文本中查找下一個標簽。

討論
從下麵這個最原始的解答入手，對這個問題的正確解答會更加容易理解：

<html>.*?<head>.*?<title>.*?</title>↵
.*?</head>.*?<body[^>]*>.*?</body>.*?</html>
正則選項：不區分大小寫、點號匹配換行符
正則流派：.NET、Java、JavaScript、PCRE、Perl、Python、Ruby

如果你在一個規範正確的HTML文件上測試這個正則表達式，它會完全正常地運行。‹.*?›會略過所有的內容，因為我們打開了“點號匹配換行符”的選項。懶惰的星號量詞會確保這個正則表達式一次隻會前進一個字符，每次都會檢查是否匹配到了下一個標簽。實例2.4和實例2.13中已經講解過這一切。

但是，如果這個正則表達式需要處理並不包含所有這些HTML標簽的目標文本，你就遇到麻煩了。最壞的情形是當</html>缺失的時候。

設想，正則引擎已經匹配了所有前麵的標簽，現在正在忙著處理最後‹.*?›的匹配。因為‹</html>›永遠無法匹配，所以‹.*?›會一直匹配到文件的結尾。現在它無法匹配更多字符，所以宣布匹配失敗。

但是這還不是故事的結束。另外6個‹.*?›都記住了一個回溯位置，因此會允許它們進一步擴展。當最後一個‹.*?›匹配失敗的時候，它前麵的那個會進行擴展，逐步匹配到< /body >。該標簽之前被正則表達式中的字麵量‹</body>›匹配。這個‹.*?›會一直擴展到文件的結尾，在它之前所有的‹.*?›惰性點號量詞也同樣會這樣做。隻有當第一個到達了文件末尾的時候，正則引擎才會宣布匹配失敗。

這個正則表達式擁有最壞情形的複雜度1FFO(n7)，也就是目標文本長度的7次方。其中包含7個惰性點號量詞，每一個都可能嚐試匹配到文件的結尾。如果文件的大小增加一倍，正則表達式就可能需要增加128倍的處理步驟才能計算出它無法匹配。

我們把這種情形稱作災難性回溯（catastrophic backtracking）。由於出現了太多的回溯，正則表達式會無休止的匹配下去或者讓你的應用程序崩潰。一些正則表達式實現會比較聰明，可能會及早退出這種失控的匹配嚐試，但是即使在這種情況下，正則表達式也還是會嚴重影響程序的性能。

screenshot災難回溯是一種被稱作組合爆炸（combinatorial explosion）的現象的一種實例，其中幾種正交條件交織起來，不得不嚐試所有的組合。你也可以說正則表達式是不同重複操作符的笛卡爾乘積。
解決方案是使用固化分組來避免不必要的回溯。在‹< /body >›匹配成功之後，第6個‹.*?›就沒有必要進行擴展。如果‹< /html >›匹配失敗的話，那麼擴展第6個惰性點號也不可能神奇地變出一個html終止標簽。

要想使一個量詞化的正則表達式記號在緊隨其後的分界符匹配之後停止擴展，就需要把正則表達式的量詞部分與分界符一起放到一個固化分組中：‹(?>.*?</ body >)›。這樣正則引擎就會在找到‹</ body >›之後丟棄‹.*?</ body >›所有的匹配位置。如果‹</ html >›隨後匹配失敗的話，因為正則引擎已經忘記了‹.*?</ body >›的回溯位置，所以不會進行任何擴展。

如果我們對正則表達式中所有其他的‹.*?›都做同樣的操作，那麼它們就都不會再繼續擴展。雖然在正則表達式中還是存在7個惰性點號，但是它們永遠也不會產生交叉。這樣就會把正則表達式的複雜度降低到O(n)，它與目標文本的長度之間是線性關係。而正則表達式的效率不可能比這更高了。

變體
如果你確實想知道災難性回溯如何執行，那麼可以在xxxxxxxxxx之上測試一下‹(x+x+)+y›。如果它很快就會失敗，那麼在目標文本中再添加一個x。重複這個過程，直到正則表達式要花費很長的時間來完成匹配或者你的應用程序因此崩潰。除非你使用的是Perl，否則並不需要添加太多的x字符就會出問題。

在本書中討論的所有正則流派中，隻有Perl有能力檢測過分複雜的正則表達式，並且它會終止匹配嚐試，而不會造成程序崩潰。

這個正則表達式的複雜度是O(2n)。當‹y›匹配失敗的時候，正則引擎會嚐試所有可能的排列組合，重複每個‹x+›以及包含它們的分組。例如，在嚐試的過程後期，會出現一個這樣的排列：‹x+›匹配xxx，第二個‹x+›匹配x，然後接著這個分組會被重複3次，其中每個‹x+›匹配x。如果存在10個x字符的話，就會存在1024種組合。如果把這個數量加到32，那麼我們就會要處理超過40億種組合，這肯定會讓任何一種正則引擎耗盡內存，除非它包含一個安全開關，能夠自己放棄，並且宣布你的正則表達式過於複雜。

該例中，這個沒有多大意義的正則表達式可以很容易被重寫為‹xx+y›，這樣它就可以在線性時間內找到完全一樣的匹配。在實踐中，對於更加複雜的正則表達式可能就不會找到這樣顯而易見的解決方案了。

本質上來說，必須要小心某個正則表達式的兩個或者更多個部分會匹配相同文本的情形。在這些情形中，可能會需要固化分組來確保正則引擎不會去嚐試所有的方式以把目標文本根據正則表達式的這兩個部分進行分割。在測試你的正則表達式時，應該總要使用包含部分可以匹配，但是又不能整體被正則表達式匹配的（較長）測試目標文本。

最後更新：2017-06-06 07:35:42

  上一篇：go  那些高考結束後，我們才明白的道理
  下一篇：go  高考將至，聽聽那些關於高考的經典段子吧