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

Question

这个问题在这里已经有了答案:





How can I recognize an evil regex?

(8 个回答)


去年关闭。




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

有很多方法，很多 a s 可以匹配:

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

对于输入字符串 "aaaaaaaaaaaaaaaaaaaaaaaaaaaab" ，它将贪婪地匹配所有这些 a s 在一次传递中，匹配 b ， 任务完成。
对于 "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" ，当它到达最后并发现字符串不匹配时(因为 s )，它没有正确识别 s意味着它永远无法匹配。因此，经过并可能匹配为

(aaaaaaaaaaaaaaaaaaaaaaaaaaaa)bs

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

(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 a 的组合，因为每个 a 可以是前一组的一部分，也可以开始自己的组)，所以它花费很长时间。