正则表达式替换的复杂性

Question

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

编辑：我在 python 中工作。但想总体了解最流行的语言/工具（java、perl、sed）。

Answer 1

从纯粹的理论立场来看：

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

总的来说，我认为 O(2^m + n)。

Answer 2

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

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

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/itation.cfm?id=114877

通过简化顶点覆盖问题来解决，这是一个经典的 NP 完全问题。

为了确定性地匹配正则表达式，我们可以采用回溯（与Perl Regex引擎不同）来跟踪可以分配给R中变量的输入文本t的可能子字。只有o（| t |^2）子字可以分配给r中的任何一个变量。如果 r 中有 n 个变量，那么就有 O(|t|^2n) 个可能的变量。 任务。一旦子串到变量的赋值固定下来，那么 问题简化为普通的正则表达式匹配。因此 使用反向引用匹配正则表达式的最坏情况复杂度为 O(|t|^2n)。

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

以 "无所谓 "符号为例，它与其他符号的区别在于 经营者有几种多项式算法可以决定一组 模式匹配输入文本。例如，库切罗夫和鲁西诺维奇

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呢……:)

Answer 3

取决于您通过正则表达式定义的内容。如果允许连接、替代和 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*) 正则表达式更好。

Answer 4

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

Answer 5

取决于实施。什么语言/图书馆/课程？可能存在最好的情况，但它对于实现中的功能数量非常具体。

Answer 6

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

Answer 7

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

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

这（加上一些其他理论花絮）意味着使用正则表达式进行匹配和替换是 NP 完全的。

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