爲什麼這種模式需要很長時間才能在java中匹配？

Question

以下正則表達式模式，當施加到非常長的字符串（60KB），使Java來似乎是「掛起」。

.*\Q|\E.*\Q|\E.*\Q|\E.*bundle.* 

我不明白爲什麼。

Answer 1

基本上，「*」（匹配任意數量的任何東西）是指試圖將整個字符串匹配，如果不匹配，然後回去再試試，等使用，其中之一是沒有太多的問題，但使用多於一個的時間必須呈指數增長。這是這類事情的一個相當深入的（和非常更準確）的討論：http://discovery.bmc.com/confluence/display/Configipedia/Writing+Efficient+Regex

編輯：（我希望你真的想知道爲什麼）

示例源字符串：

aaffg, ";;p[p09978|ksjfsadfas|2936827634876|2345.4564a bundle of sticks 

一種方式看它的：

的過程需要很長時間，因爲.*的entir匹配e源字符串（aaffg, ";;p[p09978|ksjfsadfas|2936827634876|2345.4564a bundle of sticks），只發現它不以|符號結束，然後回溯到|符號的最後一種情況（...4876|2345...），然後嘗試將下一個.*一直匹配到字符串的末尾。

它開始尋找你的表達指定的下一個|符號，並沒有找到它，它再回溯到第一|符號，它是匹配的（那個在...4876|2345...），放棄那場比賽之前找到的最接近| （...dfas|2936...），使之能夠在第二|符號在你的匹配表達式匹配。

它將然後進行匹配.*到2936827634876和第二|到一個在...4876|2345...和下.*到剩餘的文字，才發現你想要的又一|。然後它會一次又一次地回溯，直到它匹配您指定的所有符號。

看它的另一種方法：

（原始表達式）：

.*\Q|\E.*\Q|\E.*\Q|\E.*bundle.* 

此大致翻譯

match: 
       any number of anything, 
followed by a single '|', 
followed by any number of anything, 
followed by a single '|', 
followed by any number of anything, 
followed by a single '|', 
followed by any number of anything, 
followed by the literal string 'bundle', 
followed by any number of anything 

問題是any number of anything包括|符號，要求一遍又一遍地分析整個字符串，你真正的意思是什麼any number of anything that is not a '|'

要解決或改善的表達，我會建議三兩件事：

首先（也是最顯著），更換大多數「匹配任何」 S（.*）與否定的字符類（[^|] ）像這樣：

[^|]*\Q|\E[^|]*\Q|\E[^|]*\Q|\E.*bundle.* 

...這會阻止它一遍又一遍匹配字符串的結尾，而是匹配所有的非|符號最多，是不是第一個字符一個「不是一個符號|」（即雙負意味着直到第一|符號），則匹配|符號，然後轉到下一個，等...

第二個變化（有點顯著，這取決於在你的源字符串中）應該是倒數第二個「匹配任何數目的任何東西」（.*）變成「懶」或「不情願」類型的「任意數目」（.*?）。這將使它試圖與尋找bundle而不是跳過bundle並匹配字符串的其餘部分的想法相匹配，只是意識到一旦到達那裏就有更多匹配，必須回溯。這將導致：

[^|]*\Q|\E[^|]*\Q|\E[^|]*\Q|\E.*?bundle.* 

第三個變化我建議是可讀性 - 在\|有一個逃生更換\Q\E塊，如，像這樣：

[^|]*\|[^|]*\|[^|]*\|[^|].*?bundle.* 

這是怎麼了該表達式無論如何都是在內部處理的 - 實際上有一種函數將表達式轉換爲「轉義\ Q和\ E之間的所有特殊字符」 - \Q\E僅用於速記，並且如果它不會使表達式更短或更簡單讀，它守ld不能使用。期。

由於|在字符類的上下文中不是特殊字符，所以否定的字符類別有一個未轉義的| - 但是，我們不要過多地離題。如果你願意，你可以逃脫它們，但是你不需要。

最終的表達大致翻譯爲：

match: 
       any number of anything that is not a '|', 
followed by a single '|', 
followed by any number of anything that is not a '|', 
followed by a single '|', 
followed by any number of anything that is not a '|', 
followed by a single '|', 
followed by any number of anything, up until the next expression can be matched, 
followed by the literal string 'bundle', 
followed by any number of anything 

一個很好的工具，我使用（但花費一些錢）被稱爲使用RegexBuddy - 伴侶/免費網站了解正則表達式的是http://www.regular-expressions.info，以及特定頁面解釋重複是http://www.regular-expressions.info/repeat.html

RegexBuddy模擬其他正則表達式引擎，並說您的原始正則表達式需要544'步驟'來匹配，而不是我提供的版本35'步驟'。

稍長示例源String一個：

aaffg, ";;p[p09978|ksjfsadfas|12936827634876|2345.4564a bundle of sticks 

略長實施例源串B：

aaffg, ";;p[p09978|ksjfsadfas|2936827634876|2345.4564a bundle of sticks4me 

更長源串 'A'（加入12936827634876之前）不影響我的建議的替換，但增加了原來的6個步驟

更長的源字符串「B」（在表達式的末尾添加'4me'）agai n表示沒有影響我的建議的替代品，但添加步驟原來

因此，根據一個字符串是如何從上面的例子不同，一個60K串只能走544步，或者它可能需要不止一百萬步

Answer 2

你必須在正則表達式5急於/貪婪量詞，所以你完全可以做一個巨大的回溯量。

This article詳盡解釋這種行爲，並且具有爲使您的正則表達式的性能更好的建議。

在這種情況下，答案可能是與非貪婪的人來取代貪婪量詞，或者更好的是使用非回溯子模式。

Answer 3

首先，我認爲你可以簡化你的正則表達式如下：

.*\Q|\E.*\Q|\E.*\Q|\E.*bundle.* 

可能成爲

.*\|.*\|.*\|.*bundle.* 

二，八九不離十回答你的問題，事實上，你有這麼多的」 * 「在你的正則表達式中意味着正則表達式解決方案必須通過TON的可能性。如果這可以適用於您的情況，以下方式可能會運行得更快。

(?:[^\|]*\|){3}[^|]*bundle.* 

通過更改爲‘[^ |]’「。‘你縮小發動機的，因爲第一個焦點將不急於搶了先’*」，‘|’。