我在任何地方都没有得到答案。正则表达式匹配和替换的运行时间复杂度是多少？
编辑：我使用Python。但是想了解大多数流行的语言/工具（Java，Perl，Sed）的情况。
8个回答
15
从纯理论的角度来看：
我熟悉的实现方式是构建一个确定性有限自动机以识别正则表达式。这是使用标准算法，时间复杂度为O(2^m)，其中m是正则表达式的大小。一旦构建完成，在其中运行字符串的时间复杂度是线性的，即O(n)，其中n是字符串长度。在字符串中找到匹配项并进行替换应该是常数时间。
因此，总的时间复杂度为O(2^m + n)。
- theprise
5
当考虑到某些量词需要回溯时，复杂度是否仍然是线性的？ - Joey
1我对“这是使用标准算法在O(2^m)的时间复杂度内完成的，其中m是正则表达式的大小”这一命题的证明很感兴趣。您是如何想出来的呢？ - Léo Léopold Hertz 준영
在极端情况下，操作次数是否存在调和级数？ - Léo Léopold Hertz 준영
O(2^m)实际上太悲观了；你无需创建DFA即可运行它 :) - jpalecek
这是一篇包含事实证明的文章链接：A. V. Aho，“Algorithms for finding patterns in strings”，收录于《理论计算机科学手册》第A卷，由Elsevier出版，1990年，页码为255-300。全文 - Dennis Golomazov
7
其他可能感兴趣的理论信息。
为了清晰起见，请假定正则表达式的标准定义。
http://en.wikipedia.org/wiki/Regular_language
这段文字来自形式语言理论。实际上，这意味着唯一的构建材料是字母表符号，串联、交替和Kleene闭包运算符，以及单位和零常数（出于群论原因）。通常最好不要过度使用这个术语，尽管脚本语言中的日常实践会导致歧义。
有一种NFA构造方法可以在O（|r| |t|）时间和O（|r|）空间内解决正则表达式r和输入文本t的匹配问题，其中|-|是长度函数。这个算法被Myers进一步改进。
http://doi.acm.org/10.1145/128749.128755
通过使用自动机节点列表和四个俄罗斯人的范例，时间和空间复杂度可降至 O(|r| |t| / log |t|)。这个范例似乎是以四位写了一篇开创性论文但不在网上的俄罗斯人命名的。然而，这个范例在计算生物学的讲义中有详细说明。
http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf
我觉得以作者的数字和国籍来命名范例而不是他们的姓氏非常滑稽。正则表达式与添加反向引用的匹配问题是NP完全的，这是由Aho证明的。
http://portal.acm.org/citation.cfm?id=114877
通过将问题规约到经典的NP完全问题顶点覆盖问题，可以匹配具有反向引用的正则表达式来确定地使用回溯（类似于Perl正则表达式引擎）来跟踪输入文本t中可以分配给r中变量的可能子字符串。对于r中的任何一个变量，只有O（|t|^2）个子字符串可以被分配。如果r中有n个变量，则存在O（|t|^2n）种可能的分配方式。一旦确定了子串分配给变量的分配，问题就会转化为普通的正则表达式匹配。因此，具有反向引用的正则表达式匹配的最坏复杂度为O（|t|^2n）。然而请注意，带有反向引用的正则表达式还没有成为功能齐全的正则表达式。
例如，与任何其他运算符分开的"不关心"符号。有几个多项式算法可以决定一组模式是否与输入文本匹配。例如，Kucherov和Rusinowitch。
http://dx.doi.org/10.1007/3-540-60044-2_46
将模式定义为一个单词w_1@w_2@...@w_n，其中每个w_i都是一个单词（而不是正则表达式），"@"是一个变长的“不关心”符号，不包含在任何w_i中。他们推导出一种O((|t|+|P|)log|P|)算法，用于将一组模式P与输入文本t进行匹配，其中|t|是文本长度，|P|是P中所有单词的长度。了解这些复杂度措施如何组合以及具有反向引用、“不关心”和其他实用正则表达式特性的正则表达式匹配问题的复杂度措施将是很有趣的。
唉，我还没有提到Python... :)
- user108761
5
这取决于你对正则表达式的定义。如果你允许使用连接、或和Kleene星号运算符，时间复杂度实际上可以是O(m*n+m)，其中m是正则表达式的大小，n是字符串的长度。你需要构造一个NFA（在m中是线性的），然后通过维护您所在状态的集合并更新它（在每个输入字母中都需要O(m)）来模拟它。
使正则表达式解析变得困难的因素：
- 括号和反向引用：捕获与前述算法仍然可行，尽管它会使复杂度更高，因此可能不可行。反向引用提高了正则表达式的识别能力，使其难度增加。
- 正向先行断言: 只是交集的另一个名称，将上述算法的复杂度提高到
O(m^2+n) - 负向先行断言: 对于构建自动机而言是一场灾难(
O(2^m)，可能是PSPACE完全问题)。但是应该仍然可以通过像O(n^2*m)这样的动态算法来解决
请注意，具体实现时，情况可能会好转或恶化。作为经验法则，简单的特征应该足够快，不歧义(例如，不像a*a*)的正则表达式更好。
- jpalecek
3
想要深入了解prise的回答，对于自动机的构建，O(2^m)是最坏情况，但实际上这取决于正则表达式的形式（对于一个非常简单的匹配单词的正则表达式，可以使用例如Knuth-Morris-Pratt算法，时间复杂度为O(m)）。
- OysterD
1
这取决于具体实现。使用的是什么语言/库/类？可能有一个最佳情况，但它非常特定于实现中功能的数量。
- Chris Fournier
0
如果你想要匹配和替换，那就意味着需要分组和反向引用。
这里有一个 Perl 的例子，其中可以使用分组和反向引用来解决 NP 完全问题： http://perl.plover.com/NPC/NPC-3SAT.html
这意味着（再加上其他一些理论知识），使用正则表达式进行匹配和替换是 NP 完全的。
请注意，这与正则表达式的形式定义不同 - 正则表达式没有分组的概念 - 并且像其他答案所描述的那样在多项式时间内匹配。
- Dave
2
很抱歉，我不明白您所说的“解决NP完全问题”的意思。由于它是NP完全问题，因此没有有效（多项式时间）的算法来计算3-CNF-SAT实例。人们需要这样的算法来解决这个问题。事实上，可以使用正则表达式对3-CNF-SAT进行编码，但这并不意味着正则表达式可以解决3-CNF-SAT，因为没有多项式时间算法来计算正则表达式。 - user108761
我最初没有提到多项式时间 - 我认为我的答案暗示了正则表达式匹配和替换在NP中，尽管经过反思，从我写的方式并不是很清楚。我稍微修改了我的答案，希望能更清楚地解释。感谢您的反馈。 - Dave
0
你可以通过构建非确定有限状态自动机（NFA）而不是确定有限状态自动机（DFA）来将空间换成速度。这可以在线性时间内遍历。当然，在最坏情况下，这可能需要O（2 ^ m）的空间。但我认为这个权衡是值得的。
- Pramod
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接