java - Java 中的正则表达式非常慢

Question

使用Java，我想检测一行是否以单词和分隔符开头，然后是“myword”，但是这个正则表达式花费的时间太长。什么是不正确的？

^\s*(\w+(\s|/|&|-)*)*myword

Answer 1

由于嵌套量词，模式 ^\s*(\w+(\s|/|&|-)*)*myword 效率不高。 \w+ 需要至少一个单词字符，而 (\s|/|&|-)* 可以匹配零个或多个某些字符。当 * 应用于组并且输入字符串在单词字符之间没有分隔符时，表达式变得类似于经典的 (\w+)* 模式catastrophical backtracking issue图案。

只是 \w+ 和 (\w+)* 性能的一个小说明:

\w+:                                                 (\w+)*

您的模式更加复杂，并且涉及更多回溯步骤。为了避免此类问题，模式不应在量化组内具有可选子模式。也就是说，创建一个具有强制子模式的组，并将必要的量词应用于该组。

在这种情况下，您可以展开您拥有的组

String rx = "^\\s*(\\w+(?:[\\s/&-]+\\w+)*)[\\s/&-]+myword";

参见IDEONE demo

这里， (\w+(\s|/|&|-)*)* 展开为 (\w+(?:[\s/&-]+\w+ )*) (我保留了外括号来生成捕获组#1，如果您对它们不感兴趣，可以删除这些括号)。 \w+ 匹配一个或多个单词字符(因此，它是一个强制子模式)，并且 (?:[\s/&-]+\w+)* 子模式匹配零个或多个(*，因此，整个组是可选的)来自已定义字符类 [\s/&-]+ 的一个或多个字符序列(因此，这是强制性的)后跟一个或多个单词字符 \w+.