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

Question

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

我正在尝试通过文件进行动态搜索。假设我正在一个非常大的文件 (2-4 mb) 中搜索 'i bet you cannot find me'。我的正则表达式生成器会生成正则表达式：

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

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

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

是我最终使用的pattern/regex。看起来很快并且不再出现堆栈溢出异常

Answer 1

我认为你因为不情愿的预选赛而得到了很多回溯(*?)。防止回溯的一种方法是使用原子分组 (?>X)、and/or 所有格限定符 (*+).

根据评论，您也更喜欢只捕获最接近“bet”的“i”以减少整体比赛的长度。由于您想获得最接近 'i' 的其余单词，因此在我为单词 2 添加负前瞻的地方，您也可以在单词 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());
}

输出：

i .... bet .... you

ibetyou

解释 (source):

"The way a reluctant quantifier works is, each time it's supposed to try to match, it first tries to let the next part of the regex match instead. So it's effectively doing a lookahead at the beginning of each iteration, which can get pretty expensive, especially when the quantified part only matches one character per iteration, like .*?"

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

Stack overflow when trying to use regex in java

html

java

regex

stack-overflow

recursion