尝试在 Java 中使用正则表达式时堆栈溢出

Question

我已经阅读了一些关于如何优化正则表达式的文章，但没有一个答案(更少的组，使用 {X，Y} 而不是 *(似乎阻止我的正则表达式出现堆栈溢出错误。

我正在尝试通过文件进行动态搜索。假设我正在一个非常大(2-4 mb(的文件中搜索"我打赌你找不到我"。我的正则表达式生成器将生成正则表达式：

i(?:.|s)*?bet(?:.|s)*?you(?:.|s)*?cannot(?:.|s)*?find(?:.|s)*?me

这个正则表达式的想法是，无论单词之间出现什么字符或空格，它都能找到确切的短语。但是，当我尝试使用时：

Pattern p = Pattern.compile(generatedRegex, Pattern.MULTILINE);
Matcher m = p.matcher(fileContentsAsString);
while (m.find()) {
System.out.println(m.group())
}

我收到堆栈溢出错误。我知道正则表达式使用递归，但这似乎并不是正则表达式的坏处。有什么方法可以优化这个正则表达式吗？谢谢！

答：

Pattern p = Pattern.compile("i(?:.*)bet(?:.*)you(?:.*)cannot(?:.*)find(?:.*?)me", Pattern.DOTALL);

是我最终使用的模式/正则表达式。看起来很快，不再出现堆栈溢出异常

Answer 1

我认为由于您不情愿的限定词(*?)，您得到了很多回溯。防止回溯的一种方法是使用原子分组(?>X)和/或所有格限定符(*+)。

根据评论，您也更喜欢只捕获最接近"bet"的"i"，以减少整体比赛的长度。既然你想得到最接近其余单词的"i"，那么在我为第二个单词添加负前瞻的地方，你也会在它旁边为单词 1 添加负前瞻。换句话说，(?!bet)会变得(?!i)(?!bet)或(?!i|bet)。我已经编辑了下面的代码以包含此要求。

String fileContentsAsString = "ii ... bet ... you, ibetyouyou";
String regex = "i(?>(?!i|bet).)*+bet(?>(?!you).)*+you";
Pattern p = Pattern.compile(regex, Pattern.DOTALL);
Matcher m = p.matcher(fileContentsAsString);
while (m.find()) {
    System.out.println(m.group());
}

输出：

我。。。。打赌。。。。你

伊贝特尤

解释(来源(：

"一个不情愿的量词的工作方式是，每次它应该尝试匹配时，它首先尝试让正则表达式的下一部分匹配。因此，它有效地在每次迭代开始时进行预测，这可能会变得非常昂贵，尤其是当量化部分每次迭代仅匹配一个字符时，例如.*？