8

在阅读了 RE/NFA 和 DFA 之后，似乎使用 RE 而不是蛮力 O(mn) 查找，在字符串中查找子字符串实际上可能会更快。我的理由是 DFA 实际上会保持状态并避免多次处理“干草堆”中的每个字符。因此，如果使用正则表达式，在长字符串中的搜索实际上可能会快得多。

当然，这仅对从 NFA 转换为 DFA 的 RE 匹配器有效。

在使用 RE 而不是蛮力匹配器时，有没有人在现实生活中体验过更好的字符串匹配性能？

4

3 回答 3

2

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

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

可以通过 DFA（使用组捕获）实现 RE，但它有开销（参见 Laurikari 的论文NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions）。

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

对于精确的子字符串搜索，您还可以尝试Boyer-Moore算法，它具有 O(mn) 最坏情况复杂度，但在实际数据上的平均效果优于 KMP。

于 2010-07-27T08:08:43.147 回答
2

实践中使用的正则表达式大多是 PCRE（Perl-Compatible Regular Expressions），它比正则语言更广泛，因此不能用正则语法来表达。PCRE 具有诸如正/负前瞻/后视断言甚至递归之类的东西，因此解析可能需要多次处理某些字符。当然，这一切都归结为特定的 RE 实现：如果表达式保持在常规语法的范围内，它是否被优化。

就个人而言，我没有对两者进行任何形式的性能比较。但是，根据我的经验，我从来没有遇到过蛮力查找和替换的性能问题，而我不得不不止一次地处理 RE 性能瓶颈。

于 2010-07-21T20:21:59.070 回答
1

如果您查看大多数语言的文档，它会提到如果您不需要正则表达式的强大功能，出于性能原因，您应该使用非正则表达式版本......示例：http ://www.php.net/manual/en/ function.preg-split.php声明：“如果您不需要正则表达式的强大功能，您可以选择更快（尽管更简单）的替代方法，例如 explode() 或 str_split()。”

这是无处不在的权衡。也就是说，解决方案越灵活、功能越丰富，其性能就越差。

于 2010-07-21T20:18:02.377 回答