正则表达式替换的复杂性

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

编辑:我在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的匹配问题和O(| r | | t |)时间和O(| 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正则表达式引擎不同)来跟踪可以分配给r中的变量的输入文本t的可能子字.只有O(| t | ^ 2)个子字可以分配给r中的任何一个变量.如果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中所有单词的长度

知道这些复杂性度量如何结合以及具有反向引用的正则表达式的匹配问题的复杂性度量,"不关心"以及实际正则表达式的其他有趣特征将是有趣的.

唉,我还没有说过关于Python的话...... :)

取决于你用正则表达式定义的内容.如果你允许连接,替代和Kleene-star的运算符,那么时间实际上可以是O(m*n+m),m正则表达式的大小和n字符串的长度.你可以通过构造NFA(线性输入m),然后通过维护你所处的状态集来模拟它,并O(m)为每个输入字母更新(in ).

使正则表达式解析变得困难的事情:

括号和反向引用:使用上述算法捕获仍然可以,尽管它会使复杂性更高,因此它可能是不可行的.反向引用提高了正则表达式的识别能力,其难度很大

积极的前瞻:只是交集的另一个名称,它将上述算法的复杂性提高到了 O(m^2+n)

负面预测:构建自动机的灾难(O(2^m)可能是PSPACE完成).但仍然可以用类似的动态算法来解决O(n^2*m)

请注意,通过具体实现,事情可能变得更好或更糟.根据经验,简单的特征应该足够快,并且明确(例如,不喜欢a*a*)正则表达式更好.