java - Java 正则表达式库是否针对任何字符进行了优化。*？

Question

我有一个用于匹配正则表达式的包装器类。显然，您将正则表达式编译成这样的 Pattern。

Pattern pattern = Pattern.compile(regex);

但假设我使用 .* 来指定任意数量的字符。所以它基本上是一个通配符。

Pattern pattern = Pattern.compile(".*");

模式是否优化为始终返回 true 而不是真正计算任何东西？或者我应该让我的包装器实现该优化吗？我这样做是因为我可以轻松地在一个进程中处理数十万个正则表达式操作。如果正则表达式参数为空，我将其合并为 .*

Answer 1

在您的情况下，我可以只使用所有格量词来避免任何回溯:

.*+

Java 模式匹配引擎有多种优化可供选择，并且可以自动应用它们。

这是Cristian Mocanu's writes in his Optimizing regular expressions in Java关于类似于 .* 的情况:

Java regex engine was not able to optimize the expression .*abc.*. I expected it would search for abc in the input string and report a failure very quickly, but it didn't. On the same input string, using String.indexOf("abc") was three times faster then my improved regular expression. It seems that the engine can optimize this expression only when the known string is right at its beginning or at a predetermined position inside it. For example, if I re-write the expression as .{100}abc.* the engine will match it more than ten times faster. Why? Because now the mandatory string abc is at a known position inside the string (there should be exactly one hundred characters before it).

一些 hints on Java regex optimization from the same source :

• 如果正则表达式包含一个必须出现在输入字符串中的字符串(否则整个表达式将不匹配)，引擎有时会先搜索该字符串，如果不匹配则报告失败查找匹配项，而不检查整个正则表达式。

• 自动优化正则表达式的另一种非常有用的方法是让引擎根据正则表达式检查输入字符串的长度与预期长度。例如，表达式 \d{100} 在内部进行了优化，如果输入字符串的长度不是 100 个字符，引擎将报告失败而不评估整个正则表达式。

• 不要在分组或交替中隐藏强制性字符串，因为引擎将无法识别它们。如果可能，指定要匹配的输入字符串的长度也很有帮助

• 如果您将在程序中多次使用正则表达式，请务必使用 Pattern.compile() 而不是更直接的 Pattern.matches 来编译模式()。

• 另请记住，您可以通过调用方法 reset() 为不同的输入字符串重新使用 Matcher 对象。

• 注意交替。像 (X|Y|Z) 这样的正则表达式以速度慢着称，所以要小心它们。首先，交替的顺序很重要，所以将更常见的选项放在前面，这样可以更快地匹配它们。此外，尝试提取常见模式；例如，使用 ab(cd|ef) 代替 (abcd|abef)。

• 每当您使用否定字符类来匹配其他内容时，请使用所有格量词:使用 [^a]*+ 而不是 [^a]*a一个。

• 与包含匹配项的字符串相比，不匹配的字符串可能会更频繁地导致您的代码卡住。 请记住始终先使用不匹配的字符串测试您的正则表达式!

• 当心known bug #5050507 (当正则表达式Pattern类抛出StackOverflowError时)，如果遇到这个错误，尝试重写正则表达式或者拆分成几个子表达式分别运行。后一种技术有时甚至可以提高性能。

• 代替惰性点匹配，使用缓和贪婪标记(例如 (?:(?!something).)*)或 unrolling the loop techinque (今天被否决了，不知道为什么)。

  Unfortunately you can't rely on the engine to optimize your regular expressions all the time. In the above example, the regular expression is actually matched pretty fast, but in many cases the expression is too complex and the input string too large for the engine to optimize.