为什么这种模式需要很长时间才能在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.* 

通过更改为‘[^ |]’“。‘你缩小发动机的，因为第一个焦点将不急于抢了先’*”，‘|’。