平均正则表达式算法的时间复杂度是什么？

Question

我并不陌生于使用正则表达式，我理解它们基于有限状态机的基本原理。

然而，我的算法分析能力不太行，我不太明白正则表达式与基本的线性搜索相比如何。我问这个问题是因为从表面上看，它似乎是一个线性数组搜索（如果正则表达式很简单的话）。

我可以去哪里学习更多关于实现正则表达式引擎的内容？

- avgvstvs

---

由于回溯，正则表达式引擎可能会表现出灾难性时间复杂度。我不确定'catastrophic'在O()符号中属于哪种复杂度，但它肯定不是线性的。 - sarnold

为什么这个被投票关闭了？ - ocodo

可能是正则表达式替换的复杂度的重复问题。 - Kevin

虽然回顾起来，最初的问题确实过于宽泛，但我最初是想要一个线性搜索和NFA搜索之间的并列比较。链接的问题并不真正是一个重复问题。 - avgvstvs

Answer 1

这是最受欢迎的大纲之一：正则表达式匹配可以简单而快速。对一个字符串运行经过DFA编译的正则表达式确实是O(n)的，但可能需要高达O(2^m)的构建时间/空间（其中m = 正则表达式大小）。

- porges

---

这个比较太棒了...让我灵感涌现，开始寻找一种实现更好的Java正则表达式库的方法...这是一个很高的目标，但当前的引擎非常丑陋。 - avgvstvs

时间复杂度为O(n)，但请注意，在对字符串执行部分匹配时，您需要大约m*n步骤，因为如果正则表达式引擎无法在第一个字符中匹配模式，则必须从第二个、第三个字符开始重新尝试，直到找到匹配的序列。 - Calmarius

@Calmarius，这对我来说没有意义。部分匹配表达式A只是匹配表达式.（A）。并收集组。 - jobermark

@jobermark 我写下这条评论是9年前的事情，当时我还不理解正则表达式。 - Calmarius

@Calmarius 而且我猜你还是不会明白？ …如果你说你明白，那就说明你不明白 :D - Gareth Ma

Answer 2

你是否熟悉“确定性/非确定性有限状态自动机”这个术语？

真正的正则表达式(当我说真正的时，指的是那些可以识别正则语言的正则表达式，而不是几乎每种编程语言都包含带有反向引用等内容的正则表达式)可以转换为DFA/NFA，并且两者都可以在编程语言中以机械方式实现(NFA可以转换为DFA)。

您需要做的是：

1. 找到一种将正则表达式转换为自动机的方法
2. 在您选择的编程语言中实现自动机的识别

这样，给定一个正则表达式，您可以将其转换为DFA并运行它，以查看它是否与指定的文本匹配。

这可以在O(n)中实现，因为DFA不会向后退(像图灵机一样)，所以它要么匹配字符串，要么不匹配。这是假设您不考虑重叠的匹配，否则您将不得不返回并重新开始匹配...

- Oscar Mederos

---

只是一个提示：前瞻和后顾不会增加正则表达式的能力，它们仍然是正则的。 - porges

事实上，当你说“真实”时，你的意思是“理论上的”。 :) - Kobi

此外，你是不是指的是“回溯引用”而不是“回溯”？ - Kobi

我在一门编程语言课上学了一些有关DFA和NFA的知识（编译器构建的前置课程）。我曾认为它应该是O(n)的。 - avgvstvs

Answer 3

经典正则表达式可以以实践中快速但最坏情况下性能极差的方式实现（标准DFA），也可以保持为NFA，具有保证合理最坏情况下性能的优点。标准DFA可以扩展以支持许多额外的匹配字符和标志，利用它基本上是回溯搜索的事实。

标准方法的示例随处可见（例如内置于Perl中）。这里有一个声称在http://code.google.com/p/re2/具有良好最坏情况行为的示例-实际上它在最坏情况下甚至比我预期的要好，所以他们可能发现了一两个额外的诀窍。

如果您对此有任何兴趣，或者关心编写可以通过病态输入被锁定的程序，请阅读http://swtch.com/~rsc/regexp/regexp1.html。

- mcdowella

---

我对这个很感兴趣... 我感兴趣的研究领域之一是输入验证技术，以提高安全性。 - avgvstvs

FYI：RE2 具有保证的最坏情况下的行为，因为它不支持回溯引用。请注意，支持回溯引用在最坏情况下需要解决一个 NP 困难问题。参见：https://perl.plover.com/NPC/NPC-3SAT.html - Bill Province