正则表达式替换的复杂性

我在任何地方都没有得到答案。 正则表达式匹配和替换的运行时复杂度是多少？

编辑：我在python中工作。 但想大致了解大多数流行的语言/工具(java，perl，sed)。

---

从纯粹的理论立场来看：

我熟悉的实现是建立确定性有限自动机来识别正则表达式。使用标准算法在O(2 ^ m)中完成，m为正则表达式的大小。一旦构建完成，通过它运行的字符串的长度就是线性的-O(n)，n是字符串的长度。在字符串中找到的匹配项的替换应该是恒定时间。

因此，总的来说，我假设O(2 ^ m + n)。

---

其他可能感兴趣的理论信息。

为了清楚起见，假定正则表达式为标准定义

http://en.wikipedia.org/wiki/Regular_language

来自形式语言理论实际上，这意味着唯一的建筑物
材料是字母符号，串联，交替和
Kleene闭包，以及单位和零常数(对于
群体理论的原因)。通常，最好不要超载此词
尽管脚本语言的日常实践导致
含糊不清。

有一个NFA结构可以解决常规匹配问题
表达式r和输入文本t在O(| r | | t |)时间和O(| r |)空间中，其中
|-|是长度函数。 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-complete，由Aho证明

http://portal.acm.org/citation.cfm?id=114877

通过减少顶点覆盖问题来解决，该问题是经典的NP完全问题。

为了确定性地将正则表达式与反向引用匹配，我们可以
采用回溯(与Perl regex引擎相同)来跟踪
可以将输入文本t的可能子词分配给in中的变量
河只有O(| t | ^ 2)个子字可以分配给任何一个变量
在河如果r中有n个变量，则可能有O(| t | ^ 2n)
作业。将子字符串分配给变量固定后，
问题简化为普通的正则表达式匹配。因此
匹配正则表达式和反向引用的最坏情况的复杂度是
O(| t | ^ 2n)。

但是请注意，尚没有带有反向引用的正则表达式
功能齐全的regexen。

以"无关"符号为例
操作员。有几种多项式算法可确定是否一组
模式与输入文本匹配。例如，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中所有单词的长度。

知道这些复杂性度量如何结合以及什么是有趣的
是正则表达式匹配问题的复杂性度量
反向引用，"无关"和其他实用的有趣功能
常用表达。

las，我还没说关于Python的话... :)

---

取决于您通过正则表达式定义的内容。如果允许串联，替代和Kleene-star运算符，则时间实际上可以是O(m*n+m)，其中m是正则表达式的大小，n是字符串的长度。您可以通过构造NFA(在m中为线性)，然后通过维护您所处的状态集并为每个输入字母更新(在O(m)中)状态进行模拟来实现此目的。

正则表达式解析困难的事情：

• 括号和后向引用：尽管使用上述算法可以提高捕获的复杂性，但仍然可以使用捕获算法，因此可能不可行。反向引用提高了正则表达式的识别能力，它的难度很好
• 正向前方：只是交集的另一个名称，这将上述算法的复杂度提高到O(m^2+n)
• 否定的前瞻：构造自动机的灾难(O(2^m)，可能是PSPACE完整的)。但是应该仍然可以使用O(n^2*m)之类的动态算法来解决

请注意，通过具体的实现，情况可能会变好或变坏。根据经验，简单的功能应该足够快，并且明确的(例如，不像a*a*这样的)正则表达式更好。

---

为了探究企业的答案，对于自动机的构造，O(2 ^ m)是最坏的情况，尽管它实际上取决于正则表达式的形式(对于一个与单词匹配的非常简单的表达式，它在O( m)，例如使用Knuth-Morris-Pratt算法)。

---

取决于实现。什么语言/图书馆/班级？可能是最好的情况，但这将取决于实现中的功能数量。

---

如果要进行匹配和替换，则意味着分组和反向引用。

这是一个perl示例，其中可以使用分组和反向引用来解决NP完全问题：
http://perl.plover.com/NPC/NPC-3SAT.html

这(再加上其他一些理论知识)意味着使用正则表达式进行匹配和替换是NP完全的。

请注意，这不同于正则表达式的形式定义-正则表达式没有分组的概念-并按其他答案所述在多项式时间内匹配。

---

您可以通过建立不确定的有限自动机而不是DFA来以空间换取速度。可以线性时间遍历。当然，在最坏的情况下，这可能需要O(2 ^ m)空间。我希望权衡是值得的。

---