用户名的正则表达式会增加CPU消耗

Question

我们的用户名验证有以下规则:

• 用户名可以包含字母数字字符
• 用户名可以有下划线,连字符或句点
• 现在假设用户名是ASCII
• 用户名无法以句点开头或结尾
• 用户名无法启动,结束或有任何空格

我们有以下正则表达式:

^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$

现在尝试匹配特定的字符串,CPU使用率呈指数级增长.例如:

M45766235H.M96312865E@EXAMPLE.COM

显然,匹配像上面的字符串应该立即失败但我想知道为什么它需要那么多的CPU周期.最终代码:

import java.util.regex.*;
public class R {
    static final Pattern namePattern = Pattern.compile("^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$");

    public static void main(String... args) {
        final String userName = "M45766235H.M96312865E@EXAMPLE.COM";
        Matcher matcher = namePattern.matcher(userName);
        System.out.println(matcher.matches());
    }
}

在不同的路线上,我重写了下面的正则表达式并且很好地展示了它:

^[\\w]+[\\w-_\\.]*[\\w]+$

Answer 1

当正则表达式引擎大量使用回溯时,匹配过程变得非常缓慢.当你让表达式的不同部分与输入的重叠部分匹配时,回溯会发生很多,特别是当没有匹配时:引擎会尝试在正则表达式的各个部分之间分割输入的不同可能性.

从正则表达式中考虑这个简单的例子:让我们使用[a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*匹配M45766235H.注意,有两个子表达式可以覆盖从第二个开始的所有字符:引擎必须考虑所有这些可能性:

[a-zA-Z0-9]+ [a-zA-Z0-9]*
------------ ------------
M45766235H   <nothing>
M45766235    H
M4576623     5H
M457662      35H
M45766       235H
M4576        6235H
M457         66235H
M45          766235H
M4           5766235H
M            45766235H

鉴于没有匹配,那就是十次无用的重复.但那不是它的结束!当混合中存在可能产生模糊覆盖的其他子表达式时,将对字符串中的每个可能匹配尝试这十个可能的匹配.

要说回溯的影响很快就加起来是一种轻描淡写:它们以几何级数增加,最终耗费了大量的CPU.

这个故事的寓意是试图减少回溯的数量.例如,你的第二个表达式

^[\\w]+[\\w-_\\.]*[\\w]+$

可以像这样重写:

^\\w[\\w-_\\.]*\\w$

这两个表达式将匹配相同的输入集,但是当存在匹配时,第二个表达式将具有唯一匹配,而原始表达式将具有大致(N-2)^3不同的方式在匹配单词的三个子表达式中分割匹配的字符串字符.

以下是关于相关主题的更多阅读:贪婪与懒惰量词的表现.