NFA和DFA之间的并行正则表达式匹配？哪个更快？

Question

我正在阅读关于NFA和DFA的内容，似乎实现正则表达式匹配器的最流行和最快的方法是从正则表达式创建NFA，将其转换为DFA，最小化该DFA，在任何语言中实现它并使用它。

DFA比NFA更好的选择是因为它只有一个输入的转移，而NFA可以有多个。因此，DFA只有一条路径可供跟随，而NFA则有多条路径。

但是，这就是我不明白的地方。为什么我们必须跟踪NFA状态并返回到它们，这会减慢我们的速度，当遇到一个输入时，我们是否可以将其拆分成不同的线程，并并行计算每个路径？这样会比DFA更快吗？还是我漏掉了什么？

- Dennis Grinch

---

问题太宽泛了。"哪个更快？"是一个无效的问题。它们各自适用于特定的任务，在某些情况下甚至需要两者兼备。 - Mulan

当模拟NFA时，任何状态只有一次转换到任何其他状态。但是，这些状态被表示为集合。它们不仅仅是从转换表中提取的简单整数。 - Kaz

Answer 1

一般来说，DFA更快，但NFA更紧凑。 NFA与正则表达式的大小成比例。（非正式证明：正则表达式语法中的每个操作节点只会向NFA图添加一个新节点。）因为DFA是由NFA状态集的子集形成的，所以在某些情况下它可能非常大。在最坏的情况下，DFA相对于正则表达式的大小呈指数级增长。这种情况的一个示例是形如(a|b)(a|b)(a|b)(a|b)...(a|b)的表达式，其中有N个(a|b)单元，将被翻译为一个大小为O（2 ** N）的DFA。它包含了所有a和b组合的唯一状态转换。在某些情况下，退化的DFA可能会超过CPU缓存的大小，因为模拟等效的NFA所需的数据结构适合缓存。

由于额外的步骤，DFA需要更多的前期成本。因此需要权衡：是否有足够的数据要通过NFA模拟器来证明建立DFA的必要性。

一个NFA模拟可以完全避免触及正则表达式中根本不适用于输入的部分。例如，假设一个正则表达式采用R1|R2形式，其中R1非常简单小巧，而R2是一个庞大而复杂的怪物。假设输入通常只匹配R1，而R2几乎从不应用（例如，由于某些不匹配的前缀根本没有任何部分）。这影响了权衡：编译到DFA意味着一切都被编译，简单的R1部分和庞大的R2部分。

最后，实现不必严格遵循NFA或DFA。NFA模拟器可以缓存计算出的状态。这些缓存状态等同于DFA状态，并提供与编译成DFA类似的好处。您可以将此视为“NFA的JIT”。缓存可以被修剪到一定的固定大小，并受替换策略的约束，以便处理完整DFA会很大的表达式时可以在较少的内存中处理（如果数据在缓存中显示良好的引用局部性，则几乎与快速相同）。

- Kaz