子串与正则表达式匹配得更快？

Question

在阅读了RE/NFA和DFA之后,似乎找到一个字符串中的子字符串实际上可以使用RE而不是强力O(mn)查找渐近地更快.我的理由是DFA实际上会保持状态并避免不止一次地处理"haystack"中的每个字符.因此,如果使用正则表达式,长字符串中的搜索实际上可能会快得多.

当然,这仅适用于从NFA转换为DFA的RE匹配器.

在使用RE而不是强力匹配器时,有没有人在现实生活中经历过更好的弦乐匹配表现？

Answer 1

首先，我建议您阅读有关几种语言的正则表达式内部原理的文章：正则表达式匹配可以简单而快速。

\n\n

由于许多语言中的正则表达式不仅用于匹配，还提供了组捕获和反向引用的可能性，因此在执行从给定正则表达式构建的 NFA 时，几乎所有实现都使用所谓的“回溯”。而且这个实现具有指数时间复杂度（在最坏的情况下）。

\n\n

可以通过 DFA（带有组捕获）实现 RE，但它有一定的开销（请参阅 Laurikari 的论文NFA with Tagged Transitions, Their Conversion to Defineistic Automata and Application to Regular Expressions）。

\n\n

对于简单的子字符串搜索，您可以使用Knuth-Morris-Pratt算法，该算法构建 DFA 来搜索子字符串，并且具有最佳的 O(len(s)) 复杂度。但它也有开销，如果您在现实世界的单词和短语（不那么重复）上针对此最佳算法测试朴素方法（O（nm）），您可能会发现朴素方法平均而言更好。

\n\n

对于精确的子字符串搜索，您还可以尝试Boyer\xe2\x80\x93Moore算法，它的最坏情况复杂度为 O(mn)，但在实际数据上平均比 KMP 效果更好。

\n