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

Question

我不是新手使用正则表达式,我理解他们所基于的基本理论 - 有限状态机.

我不太擅长算法分析,也不理解正则表达式与基本线性搜索的比较.我问,因为从表面上看,它似乎是一个线性阵列搜索.(如果正则表达式很简单.)

我在哪里可以了解有关实现正则表达式引擎的更多信息？

Answer 1

这是最受欢迎的大纲之一:正则表达式匹配可以简单快速 .针对字符串运行DFA编译的正则表达式确实是O(n),但是可能需要最多O(2 ^ m)的构造时间/空间(其中m =正则表达式大小).

这种比较太棒了……并且给了我灵感，让我开始寻找一种为 Java 实现更好的正则表达式库的方法……一个远大的目标，是的，但是当前的引擎太丑了。 (2认同)
时间复杂度为 O(n)，但请注意，对字符串进行部分匹配时，大约需要 m*n 步，因为如果正则表达式引擎无法匹配第一个字符中的模式，则必须重试从第二个、第三个字符开始，依此类推，直到找到匹配的序列。 (2认同)
@Calmarius 这对我来说没有意义。部分匹配表达式 A 只是匹配表达式 .*(A).* 并收集该组。 (2认同)
@jobermark 我九年前写了这条评论，当时我不理解正则表达式。 (2认同)

Answer 2

您是否熟悉术语确定性/非确定性有限自动机？

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

你要做的是:

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

这可以实现O(n),因为DFA不会后退(如图灵机),所以它匹配或不匹配.假设您不会接受计数重叠匹配,否则您将不得不重新开始匹配...

Answer 3

经典正则表达式可以在实践中快速实现,但具有非常糟糕的最坏情况行为(标准DFA)或以确保合理的最坏情况行为(将其保持为NFA)的方式实现.可以扩展标准DFA以支持许多额外匹配的字符和标志,这些字符和标志利用了它基本上是跟踪搜索的事实.

标准方法的示例无处不在(例如内置于Perl中).有一个例子声称在http://code.google.com/p/re2/上有一个好的最坏情况行为- 实际上它比我在最坏的情况下预期的要好,所以他们可能已经找到了额外的一招或者两个.

如果你在所有的兴趣在此,或关心编写,可向锁固给出病理输入程序,读取http://swtch.com/~rsc/regexp/regexp1.html.