Regex模式匹配Java中长字符串的性能

Question

我有一个正则表达式，当找到匹配项时效果很好（500纳秒），但当没有匹配项时需要花费大量时间（超过3秒）。我怀疑这可能是因为回溯。我尝试了一些选项，比如根据一些文档将.*转换为(.*)?，但没有帮助。

输入：一个非常长的字符串-在某些情况下为5k个字符。

要匹配的Regex：.*substring1.*substring2.*

我正在预编译模式并重新使用匹配器，我还能尝试什么？

这是我的代码片段——我将使用数百万个不同的输入字符串来调用这个方法，但只有少数regex模式。

private static HashMap<String, Pattern> patternMap = new HashMap<String, Pattern>();
private static HashMap<String, Matcher> matcherMap = new HashMap<String, Matcher>();

这是我的方法：

public static Boolean regex_match(String line, String regex) {
    if (regex == null || line == null) {
      return null;
    }
    if (!patternMap.containsKey(regex)) {
      patternMap.put(regex, Pattern.compile(regex));
      matcherMap.put(regex,patternMap.get(regex).matcher(""));
    }
    return matcherMap.get(regex).reset(line).find(0);
 }

Answer 1

正如您所暗示的，您的正则表达式会遇到一个称为灾难性回溯的问题。本质上，第一个.*将匹配整个字符串，然后回溯直到substring1匹配。这将在substring2中重复。由于substring2失败，第二个.*将需要找到substring2开始匹配的另一个位置，然后它将再次失败。每次substring1匹配时，我们都需要检查substring2可能匹配的每个位置。

您已经在使用pattern.find()，因此可以省略起始和结束.*。然后，将内部.*更改为.*?可以通过将贪婪匹配器变为懒惰匹配器来提高性能。

这会产生：substring1.*?substring2

Answer 2

如果使用indexOf():，您可以验证模式是否匹配

int pos1 = str.indexOf("substring1");
int pos2 = str.indexOf("substring2", pos1);
if(pos1 != -1 && pos2 != -1){
  // regex
}

---

当正则表达式不匹配时，您将得到灾难性的回溯。事实上，即使有匹配，你的模式也可能会进行大量的回溯。.*将吃掉整个字符串，然后需要倒退，不情愿地返回字符。

如果您的字符串看起来像：substring1 substring2........50000 more characters......，那么使用懒惰的.*?将获得更好的性能。请注意，(.*)?与.*?不同。

正则表达式的性能会因子字符串的内容以及匹配的内容而异。若您的字符串看起来像：substring1........50000 more characters...... substring2，那个么您将使用现有的.*获得更好的性能。

Answer 3

如果情况足够简单，使用String.indexOf()比Regex快得多。您可以将问题重新编码为：

public static boolean containsStrings(String source, String string1, String string2) {
  long pos1, pos2;
  pos1 = source.indexOf(string1);
  if(pos1 > -1) {
    pos2 = source.indexOf(string2,pos1 + string1.length);
    if(pos2 > pos1 && source.indexOf(string1,pos2 + string2.length) < -1) {
      return true;
    }
  }
  return false;
}

请注意，我的解决方案不处理string1中包含string2的情况，如果是这种情况，则需要将其添加到逻辑中。

Answer 4

^((?!substring1).)*substring1((?!substring2).)*substring2.*?Z

应该这样做，因为一个多次包含一个子字符串但不是同时包含两个子字符串的字符串不会反悔。你可以放下。*？\如果您不需要匹配器在输入的末尾结束，则在末尾使用Z。