Regex在Java中执行速度太慢

Question

我的目的是匹配这种不同的网址：url.commy.url.commy.extended.url.coma.super.extended.url.com等等...

因此，我决定构建正则表达式以在URL的开头和结尾具有字母或数字，并具有无数个带有字母数字字符和点的“子域”。例如，在“ my.extended.url.com”中，“ my”中的“ m”是正则表达式的第一类，“ com”中的“ m”是正则表达式的最后一个类，而“ y”， “扩展。”和“网址”。是正则表达式的第二类。

使用下面的代码中的模式和主题，我希望find方法向我返回false，因为此url必须不匹配，但是它使用100％的CPU，并且似乎处于无限循环中。

  
    String subject = "www.association-belgo-palestinienne-be";
    Pattern pattern = Pattern.compile("^[A-Za-z0-9]\\.?([A-Za-z0-9_-]+\\.?)*[A-Za-z0-9]\\.[A-Za-z]{2,6}");

    Matcher m = pattern.matcher(subject);
    System.out.println("    Start");
    boolean hasFind = m.find();
    System.out.println("    Finish : " + hasFind);
  

仅打印：

      Start
  

我无法使用正则表达式测试器重现该问题。正常吗？问题来自我的正则表达式吗？可能是由于我的Java版本（1.6.0_22-b04 / JVM 64位17.1-b03）吗？

感谢您的帮助。

Answer 1

这不是无限循环。问题在于它正在检查所有可能的匹配项，但没有找到匹配项。如果您让它运行了数百万年，它将最终终止。请参阅this article，以了解有关引擎盖下发生的情况的详细说明。

也许此正则表达式令人满意（它终止于给定的字符串）：^[A-Za-z0-9][A-Za-z0-9_-]*(\\.[A-Za-z0-9_-]+)*\\.[A-Za-z]{2,6}$（请参阅http://ideone.com/Z0rlg）

Answer 2

问题是正则表达式的([A-Za-z0-9_-]+\\.?)*部分。请注意，它在另一个量词（*）内有一个量词（+）。这导致catastrophic backtracking-基本上，它必须尝试以指数形式进行匹配以检查正则表达式，至少是大多数正则表达式引擎的实现方式（包括Java）。

如果使用possessive quantifiers，您将能够避免此问题，但是，这将改变正则表达式的含义，并且将不再与您要匹配的内容匹配。

我认为，这里的诀窍是找到一个表达正则表达式的正则表达式，而没有双量词。例如，以下应该工作：

Pattern.compile("^[A-Za-z0-9]\\.?([A-Za-z0-9_-]|[A-Za-z0-9_-]\\.)*[A-Za-z0-9]\\.[A-Za-z]{2,6}$");

我认为这表示您要匹配的同一类字符串，并且应该快得多。

Answer 3

这实际上不是无限循环，只是花费了[[really长时间。出于所有实际目的，我们可以将其称为挂起。

您的正则表达式可能会得到改善。

尝试将$放在末尾。它将说这是行的结尾。它可以帮助您节省时间。

编辑：

 String subject = "www-association-belgo-palestinienne-be";
 Pattern pattern = Pattern.compile("^[A-Za-z0-9]([-_A-Za-z0-9]*)(\\.[-_A-Za-z0-9]+)*\\.([-_A-Za-z0-9]+\\.)*([-_A-Za-z0-9]*)[A-Za-z0-9]$");

 Matcher m = pattern.matcher(subject);
 System.out.println("    Start");
 boolean hasFind = m.find();
 System.out.println("    Finish : " + hasFind);

Answer 4

请参见How do you debug a regex?。

具体来说，我会尝试regexpal，并将Java反斜杠更改为单个反斜杠。

Answer 5

这是一个明显的Java regexp实现错误。用您的正则表达式查看结果并输入数据here

您将看到评估的速度有多快