正则表达式挂起程序（100％CPU使用率）

问题描述：

当我使用下面的字符串作为正则表达式的输入时，Java以100％的CPU使用率挂起。正则表达式挂起程序（100％CPU使用率）

使用正则表达式：

下面是用于在我的应用程序说明字段的正则表达式。用于测试

^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+

字符串：

SaaS服务VLAN从Provider_One
与迪迪埃SPT第2次尝试，因为第一次他给了我错了:-(

当我用不同的组合分割相同的字符串时，它正常工作，比如“来自Provider_One的SaaS服务VLAN”，“他给我的第一个错误:-(”，等等。Java是hangi只适用于上面给定的字符串。

我也尝试过优化正则表达式，如下所示。

^([\\w\\-\\.\\&\\,]+[\\s]*)+

即使这是行不通的。

你想匹配或从该字符串中提取什么？你的正则表达式似乎基本上匹配任何句子。 – nickb 2012-07-17 13:02:48

@ user1531484 - 可以发布整个代码，即Pattern，Matcher和代码以获取。 – Saurabh 2012-07-17 13:04:12

当您从字符串中删除笑脸和数字时它工作吗？ – amon 2012-07-17 13:05:06

答

首先，你需要认识到你的regexes不能匹配提供的输入字符串。这些字符串包含不是“单词”字符的数字字符（'<' '>' '/' ':'和')'）。

那为什么要这么长时间？

基本上是“灾难性的回溯”。更具体地说，正则表达式的重复结构给出指数正则表达式回溯算法的替代方案的数量！

这是你的正则表达式这样说：

一个或多个单词字符
后跟零个或多个空格字符
重复前面的2种模式多次，只要你喜欢。

问题出在“零个或多个空格字符”部分。第一次，匹配器会匹配第一个意想不到的字符（即'<'）。然后，它会退后一步，用另一种替代方法再次尝试......在最后一个字母之前涉及“零空格”，然后在失败时将“零空格”移回一个位置。

问题是，对于字符串N非空格字符，有N不同的地方，“零空格”可以匹配，并且这使得2^N不同的组合。随着N的增长，这会迅速变成一个很大的数字，最终的结果很难与无限循环区分开来。

答

catastrophic backtracking的另一个经典案例。

你嵌套，导致排列的巨大数量的量词进行检查时，正则表达式中，是不是你的性格类的一部分（您使用的.matches()方法假设）您输入的字符串到达:。

让我们简化问题，这个正则表达式：

^([^:]+)+$

与此字符串：

1234:

正则表达式引擎需要检查

1234 # no repetition of the capturing group 
123 4 # first repetition of the group: 123; second repetition: 4 
12 34 # etc. 
12 3 4 
1 234 
1 23 4 
1 2 34 
1 2 3 4

...这只是为了四个字符。在你的示例字符串上，RegexBuddy在100万次尝试后中止。 Java会高兴地继续徘徊...在最终承认这些组合中没有一个允许以下:匹配。

你如何解决这个问题？

您可以通过使用possessive quantifiers回溯禁止正则表达式：

^([A-Za-z0-9_.&,-]++\\s*+)+

将允许正则表达式失败得更快。顺便说一下，我删除了所有不必要的反斜杠。

编辑：

几个测量：

关于字符串"was wrong :-)"，它需要使用RegexBuddy 862个步骤，找出不匹配。
对于"me was wrong :-)"，它是1,742步。
对于"gave me was wrong :-)",14204步骤。
对于"he gave me was wrong :-)",28,046步骤。
对于"one he gave me was wrong :-)",112,222步骤。
对于"first one he gave me was wrong :-)"，> 1,000,000步。

您需要保留'.'的反斜杠。 – Thor84no 2012-07-17 13:25:22

+24

@ Thor84no：不。在一个角色类中，一个点代表一个点。 – 2012-07-17 13:26:46

感谢您的回答。是。我正在使用.matches（）方法。更新后的正则表达式工作正常。你能否解释一下反斜杠是如何影响性能的？在上面的正则表达式中++有什么意义？谢谢 – user1531484 2012-07-18 06:09:29

答

为什么你将whitespace与其他字符分开匹配？你为什么要在比赛开始时固定比赛，但不是最后？如果你想确保字符串不启动或空格结束，你应该做这样的事情：

^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$

现在只有一个“路径”正则表达式引擎可以通过串。如果在达到结尾之前用完与[A-Za-z0-9_.&,-]匹配的字符，并且下一个字符与\s不匹配，则立即失败。如果在仍然匹配空白字符的情况下达到最后，则会失败，因为在每次运行空白后需要至少匹配一个非空白字符。

如果你想确保有只有一个空格字符分隔非空白的运行，只是从\s+删除量词：

^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$

如果你不关心空格是相对于非空白，只是比赛他们都具有相同的字符类：

^[A-Za-z0-9_.&,\s-]+$

我假设你知道你的正则表达式不会给定的输入匹配，因为在SMI的:和(的莱伊，你只是想知道为什么要失败这么长时间。

和当然，因为你创造了一个Java字符串字面形式的正则表达式，你可以这样写：

"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$"

或

"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$"

或

"^[A-Za-z0-9_.&,\\s-]+$"

（我知道你在原始问题中有双反斜杠，但这可能只是为了让他们展示适当的因为你没有使用SO的优秀代码格式化功能。）

“^ [A-Za-z0-9 _。＆， - ] +（？：\\ s [A-Za-z0-9 _。＆， - ] +）* $”与原始字符不匹配，因为它不会与具有两个连续空格的字符串匹配。但你的正则表达式“^ [A-Za-z0-9 _。＆， - ] +（？：\\ s + [A-Za-z0-9 _。＆， - ] +）* $”并且我更喜欢它比Tim Pietzcker的掌握量词解决方案 - 后者太聪明了。 :-) – 2012-07-21 19:59:49

正则表达式挂起程序（100％CPU使用率）

相关推荐