regex - 哪个正则表达式表现更好？

Question

我想匹配具有公共(public)前缀 (/files) 但仅包含两个特定目录(图像和视频)的 URL。我可以为此想到两个正则表达式:

/files/(images/.*|videos/.*)

和

/files/(image|video)s/.*

这里有两个问题:

1. 从性能角度来看，哪个更好？我的猜测是第二个，因为它的 DFA 将具有较少数量的状态。
2. 是否存在一种通用编程语言，其内置的正则表达式编译器会将给定的正则表达式简化为最小的 DFA？

性能对我来说很重要，因为我将使用它来匹配数十亿个字符串。因此，任何微小的改进对我来说也很重要。

Answer 1

Which one is better from a performance perspective? My guess is the second one since its DFA will have a smaller number of states.

这两个表达式在最小 DFA 中具有相同数量的状态，并且它们的 DFA 匹配相同的“语言”(理论上)。

无论 DFA 中的状态数量如何，性能在理论上都是相同的，因为在将输入提供给自动机时，您将确定性地遍历状态。

在实践中，可能会因缓存未命中而有所不同，当状态更多时，这种情况可能会更频繁地发生。但是，除非您在正则表达式引擎上工作，否则我想不出有什么好的理由花时间进行黑盒优化。

Is there a general purpose programming language whose built-in regex compiler will reduce the given regex into the minimal DFA?

Go ( re2 ) 和 Haskell 具有将正则表达式转换为 DFA 的引擎。不过，我不知道 DFA 是否是最小的。

由于 POSIX ERE 不支持反向引用(反向引用不同于对替换中捕获组的引用)，可以为 POSIX ERE 编写在 DFA 上运行的引擎或高效的 NFA 模拟。但是，由于标准不强制要求这样的实现，只要结果是正确的(匹配最左边最长的字符串)，该实现可以详尽地搜索与 NFA 回溯引擎上的正则表达式匹配的所有字符串。

但是，至少 GNU egrep seems to implements POSIX ERE with DFA (基于文件名 dfa.c)。

---

供您引用，有3 approaches to implement a regular expression matching :

• DFA
• NFA 模拟算法
• NFA 回溯

有关更多详细信息，请访问此 article (在 this question 中引用)解释说:

• 对于(理论上的)正则表达式，存在具有子匹配跟踪(捕获组)的高效 NFA 模拟算法。
• 为什么回溯引擎如此突出(例如 Java、Python、Perl²，...)
  _{^{2:Perl 实现了带内存的回溯引擎。}}
• 回溯引擎可能在输入长度上花费指数时间，而 Thompson 的 NFA 模拟算法花费 O(mn) 时间，其中 m 是正则表达式的长度，n 是输入的长度。
• 目前已知的将(ir)正则表达式与反向引用匹配的最有效算法是回溯法。因此，一些引擎决定不支持反向引用以提高匹配效率。
• 回溯引擎(即使有内存)比 Thompson 的 NFA 模拟算法慢。

顺便说一下，re2 引擎(上面提到的)包括基于 DFA 和基于 NFA(高效模拟)的匹配算法的实现。