RE2/J：Java中的线性时间正则表达式匹配

RE2是一个运行时间与输入大小成线性关系的正则表达式引擎。RE2/J是C++库RE2的纯Java移植版。

Java的标准正则表达式包java.util.regex以及许多其他广泛使用的正则表达式包，如PCRE、Perl和Python，都使用回溯实现策略：当模式提供两个选择，如a|b时，引擎会首先尝试匹配子模式a，如果没有匹配成功，它会重置输入流并尝试匹配b。

如果这种选择被深度嵌套，该策略在检测输入是否匹配之前需要对输入数据进行指数级次数的遍历。如果输入很大，很容易构造出一个运行时间超过宇宙寿命的模式。这在接受来自不受信任源（如Web应用程序用户）的正则表达式模式时会创造安全风险。

相比之下，RE2算法通过使用非确定性有限自动机，在对输入数据的单次遍历中同时探索所有匹配。

PCRE或Perl正则表达式的某些特性无法在线性时间内实现，例如，后向引用，但实际上绝大多数正则表达式模式都避免使用这些特性。

为什么我应该切换？

如果你使用具有高度选择性的正则表达式模式，你的代码使用RE2/J可能会运行得更快。在最坏的情况下，java.util.regex匹配器可能会永远运行，或者超出可用的栈空间而失败；使用RE2/J永远不会发生这种情况。

注意事项

这不是Google的官方产品（无论是实验性的还是其他性质的），它只是恰好由Google拥有的代码。

RE2/J不是java.util.regex的直接替代品。除了不同的包名外，它不支持接口的以下部分：

MatchResult类
Matcher.hasAnchoringBounds()
Matcher.hasTransparentBounds()
Matcher.hitEnd()
Matcher.region(int, int)
Matcher.regionEnd()
Matcher.regionStart()
Matcher.requireEnd()
Matcher.toMatchResult()
Matcher.useAnchoringBounds(boolean)
Matcher.usePattern(Pattern)
Matcher.useTransparentBounds(boolean)
CANON_EQ
COMMENTS
LITERAL
UNICODE_CASE
UNICODE_CHARACTER_CLASS
UNIX_LINES
PatternSyntaxException.getMessage()

它也不完全支持Java的全部字符类和特殊正则表达式结构。

获取RE2/J

如果你使用Maven，可以在pom.xml中使用以下片段来获取RE2/J：

<dependency>
  <groupId>com.google.re2j</groupId>
  <artifactId>re2j</artifactId>
  <version>1.6</version>
</dependency>

你可以在任何与Maven中央仓库兼容的构建系统中使用相同的构件详情（如Gradle、Ivy）。

你也可以以传统方式下载RE2/J：前往RE2/J发布标签，下载RE2/J JAR并将其添加到你的CLASSPATH中。

讨论和贡献

我们已经建立了一个Google讨论组，如果你想取得联系，请加入RE2/J讨论列表。

如果你想贡献补丁，请参阅贡献者指南。

谁编写了这个？

RE2由Russ Cox设计并用C++实现。C++实现包括NFA和DFA引擎以及众多优化。Russ还将简化版的NFA移植到了Go语言。Alan Donovan将基于NFA的Go实现移植到了Java。Afroz Mohiuddin用熟悉的Java Matcher / Pattern API封装了引擎。James Ring准备了开源发布，并自那时起一直是其主要维护者。