为什么这个正则表达式需要很长时间才能执行？

我发现，例如这条线的执行时间非常长：

System.out.println( ".. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .... .. .." .matches("(?i)(?:.* )?\\W?([a-z0-9-_\\.]+((?: *)\\.(?: *))+(?:DE))(?:[0-9]{1,5})?") ); 

如果我减少字符串开头的点数，则执行时间会降低（看起来像指数）。 这是挂起线程的堆栈跟踪：

 [Repeating text]... Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Loop.match(Matcher, int, CharSequence) line: 4785 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Loop.match(Matcher, int, CharSequence) line: 4785 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4279 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Loop.matchInit(Matcher, int, CharSequence) line: 4801 Pattern$Prolog.match(Matcher, int, CharSequence) line: 4741 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Ques.match(Matcher, int, CharSequence) line: 4182 Pattern$BranchConn.match(Matcher, int, CharSequence) line: 4568 Pattern$GroupTail.match(Matcher, int, CharSequence) line: 4717 Pattern$Single(Pattern$BmpCharProperty).match(Matcher, int, CharSequence) line: 3798 Pattern$Curly.match0(Matcher, int, int, CharSequence) line: 4272 Pattern$Curly.match(Matcher, int, CharSequence) line: 4234 Pattern$GroupHead.match(Matcher, int, CharSequence) line: 4658 Pattern$Branch.match(Matcher, int, CharSequence) line: 4604 Matcher.match(int, int) line: 1270 Matcher.matches() line: 604 Pattern.matches(String, CharSequence) line: 1135 String.matches(String) line: 2121 Main.main(String[]) line: 11 

为什么会这样？

Answer 1

当模式x可选时 – 使用? 或*量词（或{0,} ） – 根据所使用的量词的性质，引擎有两条路径：

• 消费然后回溯其他模式（贪婪的情况，即.* , .? ）
• 首先不消耗并立即查看其他模式（懒惰的情况.*? ）

有人可能不知道正则表达式或者不关心性能和抛出.*无论何时他需要在字符串中的某个地方进行匹配而且引擎来回如此之快以至于没有任何模式不可能是奇怪或缓慢找到。

时间复杂度从O(n)并继续O(n^2b) ，其中b是嵌套量词的级别。 因此，失败的引擎步数是巨大的。

为了避免这种情况，有人需要考虑一些指导原则：

• 指定边界。 如果模式应该在数字之前停止某处.* 。 而是做\D* 。

• 使用条件。 在使用前瞻^(?=[^x]*x)运行整个匹配之前，您可以检查模式/字母x存在。 这导致早期失败。

• 使用所有格量词或primefaces组（如果可用）。 这两个避免回溯。 有时你不需要回溯。

• 不要做(.*)+或类似的模式。 而是重新考虑您的要求或至少使用primefaces组(?>.*)+ 。

你自己的正则表达式也不例外。 它有很多贪婪和可选的比赛，需要一段时间来重新训练。