正则表达式 – 子串匹配正则表达式更快？
发布时间：2020-12-14 06:22:51 所属栏目：百科 来源：网络整理
导读：在阅读了RE / NFA和DFA之后,似乎找到一个字符串中的子字符串实际上可以使用RE而不是强力O(mn)find渐近地更快.我的理由是DFA实际上会保持状态并避免不止一次地处理“haystack”中的每个字符.因此,如果使用正则表达式,长字符串中的搜索实际上可能会快得多. 当
|
在阅读了RE / NFA和DFA之后,似乎找到一个字符串中的子字符串实际上可以使用RE而不是强力O(mn)find渐近地更快.我的理由是DFA实际上会保持状态并避免不止一次地处理“haystack”中的每个字符.因此,如果使用正则表达式,长字符串中的搜索实际上可能会快得多.
当然,这仅适用于从NFA转换为DFA的RE匹配器. 在使用RE而不是强力匹配器时,有没有人在现实生活中经历过更好的弦乐匹配表现？
首先,我建议您阅读有关几种语言的正则表达式内部的文章：
Regular Expression Matching Can Be Simple And Fast.
由于许多语言中的regexp不仅仅用于匹配,而且还提供了组捕获和反向引用的可能性,因此在执行从给定regexp构建的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更好. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |