Java中长字符串的正则表达式模式匹配性能问题

Question

我有一个正则表达式，当匹配成功时非常快（500纳秒），但是在没有匹配的情况下需要很长时间（超过3秒）。我怀疑这可能是由于回溯引起的。我尝试了一些选项，比如根据一些文档将.*转换为(.*)?，但没有帮助。

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

要匹配的正则表达式：.*substring1.*substring2.* 我正在预编译模式并重复使用匹配器，我还能尝试什么？

这是我的代码片段 - 我将使用数百万个不同的输入字符串调用此方法，但只有少数正则表达式。

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);
 }

- user100001

---

你在这里的目标是什么？你需要使用正则表达式吗？ - Pshemo

请展示你的代码 - Nicolas Filotto

@Pshemo - 是的，我必须使用正则表达式。 - user100001

你需要在表达式前后加上 .* 的原因是什么？如果你使用 find() 替代 match() 并且去掉表达式开头和结尾的 .* 前缀和后缀，速度会更快。 - Chill

你是将这些模式硬编码还是动态构建的？我可以建议使用展开的模式，例如substring1[^s]*(?:s(?!ubstring2)[^s]*)*substring2。 - Wiktor Stribiżew

Answer 1

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

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

这将产生：substring1.*?substring2。

- Strikeskids

---

太好了。这比我之前用的正则表达式性能更好。感谢你的回答。 - user100001

Answer 2

您可以使用indexOf()来验证该模式是否匹配：

int pos1 = str.indexOf("substring1");
int pos2 = str.indexOf("substring2", pos1);

if(pos1 != -1 && pos2 != -1){
  // regex
}

---

当正则表达式无法匹配时，将会发生灾难性回溯。实际上，即使有匹配项，您的模式也可能会进行大量回溯。 .* 将吞掉整个字符串，然后需要向后移动，不情愿地放回字符。

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

正则表达式的性能取决于子字符串是什么，以及它们匹配的内容是什么。如果您的字符串看起来像这样：substring1........50000个字符......substring2，那么您将使用您所拥有的.*获得更好的性能。

- Laurel

Answer 3

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

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;
}

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

- Michael Shopsin

---

这个想法不错，但如果在 string1 之前和之后都有两个 string2 的话，这种方法会失败。最好先找到 string1，然后使用它的索引作为查找 string2 的起始索引。 - tobias_k

很遗憾，这不起作用，因为我的函数应该能够处理任何正则表达式。感谢您的回答。 - user100001

@user100001 真遗憾，在一个20MB文本的实际案例中，我尽可能多地使用了indexOf()和contains()，只有在复杂情况下才使用正则表达式。在大型文档上谨慎使用正则表达式可以获得数个数量级的性能提升。 - Michael Shopsin

Answer 4

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

应该这样做，因为包含一个子字符串多次但不按顺序的字符串不会无限回溯。 如果您不需要匹配器以输入结尾结束，则可以在末尾放弃.*?\Z。

- Mike Samuel