java - 带有前后(。*)慢的Java正则表达式

Question

我注意到，当我在文本上匹配以下表达式之类的正则表达式时，它比不带前尾部分（.*）的正则表达式要慢得多。我在perl上做了同样的事情，发现对于perl几乎没有什么不同。有什么方法可以优化Java的原始正则表达式"(.*)someRegex(.*)"？

Pattern p = Pattern.compile("(.*)someRegex(.*)");
Matcher m = p.matcher("some text");
m.matches();

Pattern p = Pattern.compile("someRegex");
Matcher m = p.matcher("some text");
m.matches();

编辑：
这是一个具体的例子：

(.*?)<b>\s*([^<]*)\s*<\/b>(.*)

Answer 1

最好的选择是根本不尝试匹配字符串的开头和结尾。如果使用matches()方法，则必须这样做，但如果使用find()方法，则不必这样做。那可能就是您想要的。

Pattern p = Pattern.compile("<b>\\s*([^<]*)\\s*<\\/b>");
Matcher m = p.matcher("some <b>text</b>");
m.find();

您可以使用 start()和 end()在包含匹配项的源字符串中查找索引。您可以使用 group()在比赛中找到 ()捕获的内容（即，粗体标记内的文本）。

以我的经验，使用正则表达式来处理HTML非常脆弱，并且仅在最普通的情况下才能很好地工作。改用完整的XML解析器可能会带来更好的运气，但是，如果这是那些琐碎的情况之一，那就加油吧。

原始答案：这是我的原始答案，分享了为什么比赛开始时 .*的表现如此差劲。

在前面使用 .*的问题是，它将导致比赛中发生大量回溯。例如，考虑以下内容：

Pattern p = Pattern.compile("(.*)ab(.*)");
Matcher m = p.matcher("aaabaaa");
m.matches();

比赛将像这样进行：


匹配器将尝试将整个字符串“ aaabaaa”吸入第一个 .*，但随后尝试匹配 a并失败。
匹配器将备份并匹配“ aaabaa”，然后尝试匹配 a并成功，但是尝试匹配 b并失败。
匹配器将备份并匹配“ aaaba”，然后尝试匹配 a并成功，但是尝试匹配 b并失败。
匹配器将备份并匹配“ aaab”，然后尝试匹配 a并成功，但是尝试匹配 b并失败。
匹配器将备份并匹配“ aaa”，然后尝试匹配 a并失败。
匹配器将备份并匹配“ aa”，然后尝试匹配 a并成功，尝试 b并成功，然后将“ aaa”匹配到最终的 .*。成功。


您希望尽可能避免在模式匹配开始时出现真正广泛的匹配。如果不知道您的实际问题，很难提出更好的建议。

更新：Anirudha建议使用 (.*?)ab(.*)作为可能的解决方案，以避免回溯。这会在某种程度上缩短回溯的时间，但会以尝试在每次尝试中应用下一个匹配项为代价。因此，现在考虑以下几点：

Pattern p = Pattern.compile("(.*?)ab(.*)");
Matcher m = p.matcher("aaabaaa");
m.matches();

它将像这样进行：


匹配器将尝试在第一个 .*?中不匹配任何内容“”，尝试匹配 a并成功，但不匹配 b。
匹配器将尝试将第一个字母“ a”匹配到第一个 .*?中，尝试匹配 a并成功，但是不匹配 b。
匹配器将尝试将前两个字母“ aa”匹配到第一个 .*?中，尝试匹配 a并成功，尝试匹配 b并成功，然后将其余部分混入 .* ，“ aaa”。成功。


这次没有任何回溯，但对于 .*?中的每个前进，我们仍然有一个更复杂的匹配过程。这可能是特定比赛的性能提升，或者如果在向前进行的比赛中进行迭代的速度较慢，则可能会导致性能下降。

这也改变了比赛进行的方式。 .*匹配是贪婪的，它尝试尽可能地匹配 .*?更保守的位置。

例如，字符串“ aaabaaabaaa”。

第一个模式 (.*)ab(.*)将“ aaabaa”与第一个捕获匹配，将“ aaa”与第二个捕获匹配。

第二个模式 (.*?)ab(.*)将“ aa”匹配到第一个捕获，将“ aaabaaa”匹配到第二个捕获。