正则表达式挂起程序(100%CPU使用率)
当我使用下面的字符串作为正则表达式的输入时,Java挂起了100%的CPU使用率。
使用RegEx:
这是我的应用程序中描述字段使用的正则表达式。
^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+
用于测试的字符串:
Provider_One中的SaaS服务VLAN
Didier SPT的第二次尝试,因为他给我的第一个是错的:-(
当我以不同的组合分割相同的字符串时,它可以正常工作。 就像“来自Provider_One的SaaS服务VLAN”,“他给我的第一个是错误的:-(”等.Java仅挂起以上给定的字符串。
我也试过优化正则表达式如下。
^([\\w\\-\\.\\&\\,]+[\\s]*)+
即使这样也行不通。
灾难性回溯的另一个经典案例。
当正则表达式到达您的输入字符串中时,您有嵌套的量词导致大量的排列被检查:
输入字符串不是您的字符类的一部分(假设您正在使用.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*+)+
将允许正则表达式更快失败。 顺便说一下,我删除了所有那些不必要的反斜杠。
编辑:
一些测量:
在字符串"was wrong :-)"
,需要RegexBuddy 862步才能找出不匹配。
因为"me was wrong :-)"
,这是1,742步。
因为"gave me was wrong :-)"
,14014步。
因为"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步。
首先,您需要意识到您的正则表达式与提供的输入字符串不匹配。 字符串包含不是“单词”字符的数字字符( '<' '>' '/' ':'
和')'
)。
那么为什么需要这么长时间?
基本上是“灾难性的回溯”。 更具体地说,正则表达式的重复结构为正则表达式回溯算法提供了指数级的替代方案!
这是你的正则表达式所说的:
- 一个或多个单词字符
- 后跟零个或多个空格字符
- 根据需要重复前两个模式。
问题在于“零个或多个空格字符”部分。 第一次,匹配器将匹配第一个意外字符(即'<'
)的所有内容。 然后它将退回一点并再次尝试使用另一个替代方案......在最后一个字母之前涉及“零空格”,然后当它失败时,它将“零空间”移回一个位置。
问题是对于具有N
非空格字符的String,有N
不同的地方可以匹配“零空间”,并且这会产生2^N
不同的组合。 随着N
增长,这迅速变成了一个巨大的数字,最终结果很难与无限循环区分开来。
为什么要将空格与其他字符分开匹配? 你为什么要在开始时锚定比赛,但不是最后? 如果你想确保字符串不以空格开头或结尾,你应该这样做:
^[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-]+$
我假设你知道你的正则表达式与给定的输入不匹配,因为:
和(
在笑脸中,你只想知道为什么它需要这么长时间才能失败。
当然,既然你是以Java字符串文字的forms创建正则表达式,那么你会写:
"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$"
要么
"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$"
要么
"^[A-Za-z0-9_.&,\\s-]+$"
(我知道你在原始问题中有双反斜杠,但这可能只是为了让它们正确显示,因为你没有使用SO的优秀代码格式化function。)