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

regex performance python java perl

2022-08-31 20:31:27

我最近有一个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

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

答案 1

警告：我对正则表达式内部式了解不多，这确实是猜想。我无法回答为什么Java会受到这种影响，但其他的则不然（而且，当我运行Java时，它比jshell 11中的12秒快得多，所以它可能只影响某些版本）。

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

有很多方法可以匹配：a

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

对于输入字符串，它将贪婪地在一次传递中匹配所有这些，匹配，完成的工作。"aaaaaaaaaaaaaaaaaaaaaaaaaaaab"ab

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

(aaaaaaaaaaaaaaaaaaaaaaaaaaaa)bs

它认为“哦，也许它失败了，因为我对s进行分组的方式 - 然后返回并尝试s的所有其他组合。aa

(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 - 28 s的组合，因为每个组合都可以是前一个组的一部分，或者开始自己的组），所以需要很长时间。aa

答案 2

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

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

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

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

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