28

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

使用的正则表达式：

这是我的应用程序中用于描述字段的正则表达式。

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

用于测试的字符串：

来自 Provider_One 的 SaaS 服务 VLAN
与 Didier SPT 的第二次尝试，因为他给我的第一个是错误的 :-(

当我将相同的字符串拆分为不同的组合时，它可以正常工作。就像“Provider_One 的 SaaS 服务 VLAN”、“他给我的第一个是错误的 :-(”等。Java 仅针对上面给定的字符串挂起。

我还尝试如下优化正则表达式。

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

即使这样也行不通。

4

3 回答 3

60

另一个灾难性回溯的经典案例。

您有嵌套的量词，当正则表达式到达:不属于您的字符类的输入字符串时，会检查大量排列（假设您正在使用该.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 会很高兴地继续努力……在最终承认这些组合都不允许以下:匹配之前。

你怎么能解决这个问题？

您可以使用所有格量词来禁止正则表达式回溯：

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

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

编辑：

一些测量：

在 string"was wrong :-)"上，它需要 RegexBuddy 862 个步骤来找出不匹配的。
对于"me was wrong :-)"，它是 1,742 步。
对于"gave me was wrong :-)", 14,014 步。
对于"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 步。

于 2012-07-17T13:11:46.603 回答
17

首先，您需要意识到您的正则表达式不能匹配提供的输入字符串。字符串包含许多不是“单词”字符的字符 ('<' '>' '/' ':'和)。')'

那么为什么需要这么长时间呢？

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

这是您的正则表达式所说的：

  1. 一个或多个单词字符
  2. 后跟零个或多个空格字符
  3. 根据需要重复前 2 个模式。

问题在于“零个或多个空格字符”部分。第一次，匹配器会将所有内容匹配到第一个意外字符（即'<'）。然后它会稍微退后一点，然后用不同的替代方案重试……在最后一个字母之前涉及“零空格”，然后当失败时，它将“零空格”移回一个位置。

问题在于，对于具有N非空格字符的字符串，N可以匹配“零空格”的不同位置，从而产生2^N不同的组合。随着增长，这迅速变成一个巨大的数字N，最终结果很难与无限循环区分开来。

于 2012-07-17T13:11:18.883 回答
4

为什么将空格与其他字符分开匹配？为什么你在开始时锚定比赛，而不是在结束时？如果要确保字符串不以空格开头或结尾，则应执行以下操作：

^[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-]+$

我假设您知道由于笑脸中的:and而您的正则表达式与给定的输入不匹配(，并且您只想知道为什么需要这么长时间才能失败。

当然，由于您正在以 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 出色的代码格式化功能。）

于 2012-07-17T15:34:43.523 回答