8

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

  • 用户名可以包含字母数字字符
  • 用户名可以有下划线、连字符或句点
  • 现在假设用户名是 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]+$
4

1 回答 1

5

当正则表达式引擎大量使用回溯时，匹配过程变得非常缓慢。当您让表达式的不同部分匹配输入的重叠部分时，会发生很多回溯，尤其是当没有匹配时：引擎尝试在正则表达式的各个部分之间拆分输入的不同可能性。

考虑一下您的正则表达式中的这个简单示例：让我们使用[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匹配字符串在三个匹配单词的子表达式中拆分的方式大致不同人物。

以下是有关相关主题的更多阅读：贪婪与懒惰量词的性能。

于 2013-04-29T21:03:29.920 回答