正则表达式搜索非常慢

Question

我不太明白下面这个正则表达式搜索到底发生了什么：

>>> import re
>>> template = re.compile("(\w+)+\.")
>>> target = "a" * 30
>>> template.search(target)

search() 的调用需要几分钟才能完成，CPU使用率飙升到100%。在Python的2.7.5和3.3.3版本中，这种情况都是可以重现的。

有趣的是，如果字符串的长度少于20-25个字符，search() 几乎是瞬间就能返回结果。

这到底是怎么回事呢？

Answer 1

第二个加号引发了一些问题：

template = re.compile("(\w+)\.")

对我来说，这个没问题。要查看这个正则表达式的解析树，可以在编译时把 re.DEBUG 作为第二个参数传入：

import re

re.compile("(\w+)+\.", re.DEBUG)
print "\n\n"
re.compile("(\w+)\.", re.DEBUG)


max_repeat 1 65535
  subpattern 1
    max_repeat 1 65535
      in
        category category_word
literal 46


subpattern 1
  max_repeat 1 65535
    in
      category category_word
literal 46

程序以退出代码 0 结束

这证明了第二个加号引入了一个循环，而 Python 的正则表达式解析器必须把这个循环限制在 65535 次。这在某种程度上支持了我的理论。

需要注意的是，每次执行时你都需要一个新的 Python 解释器。因为 re.compile 会记住传入的值，所以它不会重复编译相同的正则表达式。例如，在 ipython 中反复运行这个代码，第一次运行后就不会再打印解析树了。

Answer 2

慢的原因是引擎在回溯：

(\w+)+\.

如果你的字符串末尾没有一个.，那么这个模式就会自然地发生回溯。引擎会先尽量匹配尽可能多的\w，但当它发现在字符串末尾之前还需要匹配更多字符时，就会回溯。

(a x 59) .
(a x 58) .
...
(a) .

最后，它会匹配失败。不过，你模式中的第二个+会让引擎检查(n-1)!种可能的路径，所以：

(a x 58) (a) .
(a x 57) (a) (a) .
(a x 57) (a x 2) .
...
(a) (a) (a) (a) (a) (a) (a) ...

去掉+可以防止出现异常多的回溯：

(\w+)\.

有些实现还支持占有量词，这在这种特定情况下可能更理想：

(\w++)\.

Answer 3

要理解这个问题，首先得知道NFA在正则表达式（RegExp）中是怎么工作的。

NFA的定义可能有点复杂，建议你去维基百科查一下，这样能更清楚。不过在这里，你可以把NFA想象成一个机器人，它的任务是找到你给定的模式。

简单实现的NFA有点傻，它只会往前看一两个你给的符号。所以在你给的例子中，NFA一开始只关注\w+（不考虑括号的分组）。

因为+是一个贪婪的量词，也就是说它会尽量匹配尽可能多的字符，所以NFA傻傻地继续从target中读取字符。读取了30个a后，NFA发现已经到字符串的末尾了。之后，NFA才意识到它需要匹配template中的其他符号。

下一个符号是+。NFA已经匹配了它，所以接着去匹配\.。这次它失败了。

NFA接下来做的是退回一个字符，尝试通过缩短\w+的匹配来找到模式。所以NFA把target分成了两部分：29个a对应一个\w+，还有一个多余的a。NFA首先尝试用这个多余的a去匹配第二个+，但在遇到\.时仍然失败。NFA会继续这个过程，直到找到完整的匹配，否则就会尝试所有可能的分割方式。

所以(\w+)+\.指示NFA以这样的方式分组target：将target分成一个或多个组，每组至少有一个字符，并且target以句号“.”结尾。只要句号没有匹配上，NFA就会尝试所有可能的分割方式。那么有多少种分割方式呢？是2的n次方（2^n）。可以想象在a之间插入分隔符，就像下面这样：

aaaaaaa a
aaaaaa aa
aaaaaa a a
.....
.......
aa a a ... a
a a a a a .... a

如果NFA匹配上了\.，那就没什么大不了的。但如果匹配失败，这个表达式就注定会变成无尽的指数级别的尝试。

我不是在做广告，但《正则表达式精髓》这本书很适合用来理解正则表达式背后的机制。