由 Eyal Schneider 于 2009 年 5 月 21 日发布 java.util.regex 包在 Java 版本 1.4 中添加。它是一个非常强大的工具，需要成为大师才能正确使用它。即使
正则表达式为真，如果编写得不巧妙，它也可能会非常慢。如果您想了解问题的原因，请继续阅读，或者滚动到页面末尾，您将找到 10 个提高 Java 中正则表达式性能的有用技巧。
真的有那么慢吗？
假设我们只想选择包含字符“a”和“b”序列的行。正确的解决方案可能是：
(a*b*)* 但是，如果您使用字符串“aaaaaaaaaaaaaaaaaaaaaaaaaaaaax”运行表达式，则需要几分钟才能完成并报告没有匹配项！当然，在这种情况下最好的正则表达式是：
(a|b)* 在我的机器上使用相同的字符串花费不到一毫秒。显然这里存在性能问题。
为什么会发生这种情况？
与大多数正则表达式引擎一样，Java 使用 NFA（非确定性有限自动机）方法。引擎一一扫描正则表达式组件，并相应地遍历输入字符串。如果遇到“死胡同”，他还可以回到起点寻找合适的替代方案。通过使用常规结构（例如量词（
*、+、?）和交替（例如
a|b|c|d））可以获得替代结果。这种研究技术称为回溯。在上面可怕的例子中，引擎实际上会将符号“a”的所有系列分解为更小的系列，直到它意识到没有匹配。此示例显示回溯算法如何得出指数时间估计（取决于输入字符串的长度）。这也显示了 NFA 的一个重要属性：总会有最坏的情况几乎与模式匹配。如果找到匹配项，则搜索停止。正则表达式中使用的另一个主要方法是 DFA（确定性有限自动机）。在这种方法中，正则表达式实际上构建了一个自动机，用于逐个字符地遍历输入字符串而无需回溯。无论正则表达式的复杂性如何，这都会为整个输入提供线性时间。DFA 模拟并行扫描，而不是顺序扫描字符串以查找匹配项（如 NFA 中）。那么为什么 Java（以及 .NET、Perl、Python、Ruby、PHP 等）使用 NKA 而不是性能更好的 DKA？原因是NKA具有许多显着的优势：
- 编译速度更快并且需要更少的内存
- 允许一些有用的功能（详细信息请参阅Sun 的教程）：
- 群组捕获和反向链接
- 位置检查
- 扩展量词（贪婪和惰性）
值得注意的是，流行术语 NKA 和 DKA 在正则表达式上下文中使用时并不精确。理论上，这两种模型具有相同的计算能力。这意味着您无法在一个自动机模型中编写在另一自动机模型中无法表达的正则表达式。在实践中，需要更多的功能，以便两种类型的实现在语义上有所不同。NKA 引擎提供了更大的灵活性，使其在计算能力上优于 DKA。由于 DFA 的速度和 NFA 的独特功能，还有 2 种“预制”方式来实现正则表达式。一些实现同时使用这两种类型（例如 GNU egrep，它在运行时选择特定的引擎），而一些实现则设法实现了真正的混合版本（例如 Tcl regexps），并具有所有优点。
建议
以下是有关如何避免 Java 中正则表达式效率问题的一些技巧。其中许多旨在减少回报。
1）预编译
陈词滥调，但值得一提。如果多次使用正则表达式，请务必提前编译它：
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2）惰性量词与贪婪量词
默认情况下，量词 (
* + ? ) 是贪婪的。这意味着它们开始匹配最长的可能序列，然后在必要时逐渐返回。如果您事先知道匹配通常会很短，则应该使用惰性量词。他们从最小的匹配开始，并在必要时进一步移动。假设我们只想查找与序列“hello”匹配的行。常规的
.*hello.*会正确执行所有操作，但如果我们知道“hello”通常出现在更靠近文本开头的位置，那么
.*?hello.*平均会运行得更快。
3）尽可能使用超贪心量词
与影响性能但不影响正则行为的惰性量词不同，超贪婪量词实际上可以改变正则表达式的含义。当使用
*+而不是
*时，第一个匹配将是贪婪的（即尽可能最大，就好像它只是 * 一样），但如果失败则不会有回退，即使这会导致整个搜索失败。这什么时候有用？假设我们需要查找引号中的文本。常规的
\"[^\"]*\"可以正常工作。但是，在负数情况下它会产生不必要的缩进（例如，“bla bla bla）。使用
\"[^\"]*+\"将消除回滚而不改变表达式的含义。独立分组可达到相同的效果并提供更多控制（请参阅
Sun 的教程）。
4）避免集体抓捕
默认情况下，括号中的任何表达式都被视为一个组。这对性能影响很小。
尽可能以(?:而不是
( )开头，使您的组“不可捕获” 。
5）明智地使用交错
当使用交错时（例如
Paul|Jane|Chris），引擎尝试匹配选项的顺序与它们出现的顺序相同。您可以利用此功能并将最常见的选项放在靠近开头的位置。这将改善平均积极响应时间。
6）避免歧义
以最小化输入字符串中不同匹配项的数量的方式编写正则表达式。例如：文章开头给出的 正则表达式
(a*b*)*允许字符串“aabb”有太多的解释方式：而
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp
(a|b)*则只解释唯一的积极组合。这对于减少
近似匹配情况下的回报非常重要。
7) 预览
预览允许您添加对当前位置左侧/右侧序列的限制。特别是，通过负向前瞻，您可以搜索不包含某些序列的行（如果没有这个我们该怎么办！）。这如何有助于提高生产力？假设我们要从链接标记中获取 URL。考虑以下正则表达式：
a .* href=(\S*).*/ 对于常规标记，如果文本包含“href”属性，则此表达式仅匹配地址（\S 用于除分隔符之外的所有字符）。但在一些不寻常的标签上，例如，会发生回滚。例如：“a href= href=href=.... href=某事。” 当将表达式中的“.*”替换为与“href”不匹配的内容时，以下正则表达式将防止这种情况发生：
a ((?!href).)* href=(\S*)((?!href).)*/
8) 指定长度
Java 包含一个正则表达式优化器，它根据从正则表达式获得的最小和最大长度检查输入字符串的长度。这允许您在某些情况下立即停止搜索。为了协助此机制，应尽可能指定重复次数（例如，
[01]{6}匹配所有六个字符长的二进制字符串）。
9）选择相同的行
有时相同的字符串隐藏在组或替代项中：
(hello|hell|heel) 此表达式可以简化为：
he(llo|ll|el) 通过这样做，我们为正则表达式优化器提供了更多信息。
10) 测试你的正则表达式
当正则表达式用于性能关键型应用程序时，首先测试正则表达式可能是明智的做法。编写一个微基准测试您对各种输入数据的表达。请务必测试不同长度的数据以及与您的样本密切匹配的数据。
链接：
http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -表达处理/
GO TO FULL VERSION