基于DFA的Java正则表达式引擎，支持捕获功能

Question

11

有没有Java的（免费）正则表达式引擎，可以将正则表达式编译为DFA，并在匹配DFA时进行组捕获？

我找到了dk.brics.automaton和jrexx，它们都编译为DFA，但似乎都不能进行组捕获。而我找到的其他引擎似乎都编译为NFA。

- Sami

1

为了性能优化。 - Sami

3

我之所以问这个问题，是因为通常这些性能优势来自DFA引擎无法回溯的能力。如果是这种情况，也许您可以使用原子分组/占有量词来达到同样的效果。也许您可以发布一些您想要实现的示例？ - Tim Pietzcker

1

能否举几个例子，以便我们看看是否可以用不同的方法解决您的问题——因为似乎没有人知道带组捕获的Java DFA正则表达式引擎…如果这真的是一个问题而不是过早优化 :) - Tim Pietzcker

谢谢您的关注，但实际上并没有需要用不同方式解决的问题。我只是想看看基于DFA的引擎对我的应用程序会产生什么性能影响。 - Sami

如果NFA不使用回溯，那么DFA和NFA引擎之间不应该有任何明显的差异。如果你找到了一个良好的线性空间时间NFA引擎，你应该使用它。即使是一个天真的实现，在没有组的情况下仍然是常数空间/线性时间的。 - Recurse

5个回答

1

最近我写了一个: tree-regex。

- nes1983

0

对于 C 语言，有 TRE 和 Google 的 RE2 库。TRE 使用 DFA，RE2 使用 NFA（据我所知），两者都可以进行子组匹配。但是我没有看到 Java 的类似库。

- Dmitry

1

RE2实际上非常快。当人们询问正则表达式和速度时，指向它是值得的。 - nes1983

2

你搞混了。TRE使用NFA，RE2同时使用NFAs和DFAs。具体而言，如果最多只有一个捕获组，RE2使用DFA，否则使用NFA。 - nes1983

-2

你可以尝试使用 Pat 正则表达式库 @ http://www.javaregex.com/。

- Jeremy Gwa

从网站上看，这个引擎至少不明显地表明它是基于DFA的，也没有表明它支持组捕获。如果它确实是这样，并且支持，您能否确认一下。 - Sami

那个库（Stevesoft Pat）确实支持捕获组，但它绝对不是基于DFA的。 - Alan Moore

-2

dk.brics.automaton 是一个DFA，似乎不支持捕获组。我预计这个特性是在两年内新增的。请查看 AutomatonMatcher 类。

- Darren Gilroy

它实际上不支持组匹配。 - nes1983

已更新，附上组捕获API链接。 - Darren Gilroy

2

是的，但你有读过那个链接吗？“不支持捕获组，唯一有效的组是0（整个匹配）。 - nes1983

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bartosz.r · Accepted Answer

根据该测试http://tusker.org/regex/regex_benchmark.html，两者都很快（我们都知道基准测试只测试基准测试创建者想要测试的内容）。

当我需要真正快速的DFA正则表达式时，我会生成一个使用grep的进程；-)（对于一个6GB的日志文件，它将我的时间从10分钟缩短到了几秒钟）。