java - 用户名的正则表达式会增加 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 在匹配单词字符的三个子表达式中拆分匹配字符串的不同方式。

这里有一些关于相关主题的更多阅读:Performance of Greedy vs. Lazy Quantifiers .