为什么这个正则表达式在 Java 中这么慢？

Question

我最近有一个SonarQube规则（https://rules.sonarsource.com/java/RSPEC-4784）引起了我的注意，一些性能问题可以用作对 Java 正则表达式实现的拒绝服务。

事实上，以下 Java 测试显示了错误的正则表达式的速度有多慢：

    import org.junit.Test;

    public class RegexTest {

    @Test
    public void fastRegex1() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)b");
    }

    @Test
    public void fastRegex2() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaab".matches("(a+)+b");
    }

    @Test
    public void slowRegex() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b");
    }
}

如您所见，前两个测试很快，第三个测试非常慢（在 Java 8 中）

然而，Perl 或 Python 中的相同数据和正则表达式一点也不慢，这让我想知道为什么这个正则表达式在 Java 中的计算速度如此之慢。

$ time perl -e '"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" =~ /(a+)+b/ && print "$1\n"'
aaaaaaaaaaaaaaaaaaaaaaaaaaaa

real    0m0.004s
user    0m0.000s
sys     0m0.004s

$ time python3 -c 'import re; m=re.search("(a+)+b","aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"); print(m.group(0))'
aaaaaaaaaaaaaaaaaaaaaaaaaaaab

real    0m0.018s
user    0m0.015s
sys     0m0.004s

数据中额外的匹配修饰符+或尾随字符s是什么导致这个正则表达式如此缓慢，为什么它只特定于 Java？

Answer 1

警告：我对正则表达式的内部结构知之甚少，这真的是猜测。而且我无法回答为什么 Java 会受此影响，但其他人不会（而且，当我运行它时，它比在 jshell 11 中的 12 秒快得多，因此它可能只影响某些版本）。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b")

许多as 可以通过多种方式匹配：

(a)(a)(a)(a)
(aa)(a)(a)
(a)(aa)(a)
(aa)(aa)
(a)(aaa)
etc.

对于输入 string "aaaaaaaaaaaaaaaaaaaaaaaaaaaab"，它将a在一次传递中贪婪地匹配所有这些s，匹配b，job done。

对于"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"，当它到达末尾并发现字符串不匹配时（因为s），它没有正确识别出s它永远无法匹配的意思。因此，经过并可能匹配为

(aaaaaaaaaaaaaaaaaaaaaaaaaaaa)bs

它认为“哦，也许它失败了，因为我将as分组的方式- 然后回去尝试as 的所有其他组合。

(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a)bs  // Nope, still no match
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaa)(aaa)bs  // ...
...
(a)(aaaaaaaaaaaaaaaaaaaaaaaaaaa)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaaa(a)(a)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaa(aa)(a)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaa(aaa)(a)bs  // ...
...

有很多这样的（我认为有类似 2^27 - 即 134,217,728 - 28a秒的组合，因为每个a都可以是前一组的一部分，也可以开始自己的组），所以需要很长时间。

Answer 2

我不太了解 Perl，但 Python 版本并不等同于 Java 版本。您正在使用，search()但 Java 版本正在使用matches(). Python 中的等效方法是fullmatch()

当我在 Python (3.8.2) 中运行您的示例时，search()我会像您一样快速获得结果。当我运行它时，fullmatch()我的执行时间很差（多秒）。难道您的 Perl 示例也没有进行完整匹配？

顺便说一句：如果您想尝试搜索的 Java 版本，您可以使用：

Pattern.compile("(a+)+b").matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaabs").find();

语义上可能有一些细微差别，但它应该足够接近此目的。

Answer 3

+当字符串无法匹配时，额外的会导致大量回溯（在幼稚的正则表达式实现中）。如果字符串可以匹配，则在第一次尝试时就知道答案。这就解释了为什么情况 2 很快，而只有情况 3 很慢。

Answer 4

站点https://swtch.com/~rsc/regexp/regexp1.html有一些关于正则表达式实现技术及其背后理论的详细信息。我知道仅链接的答案很糟糕，但这值得一读，它展示了一个示例正则表达式，它在 30 微秒内完成，使用更好的实现，60 秒（慢 200 万倍）使用更广为人知和更明显的方式。

它说

“今天，正则表达式也成为了一个光辉的例子，说明忽视好的理论会导致糟糕的程序。今天流行的工具使用的正则表达式实现比许多 30 年前的 Unix 工具使用的要慢得多。”

其他答案说额外+导致太多回溯是正确的，但前提是您忽略了好的理论。