正则表达式替换的复杂性

Complexity of Regex substitution

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

编辑：我在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)中)状态进行模拟来实现此目的。

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