python - 非常慢的正则表达式搜索

Question

我不确定我是否完全理解以下正则表达式搜索的含义:

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

search() 调用需要几分钟才能完成，CPU 使用率达到 100%。该行为对于 2.7.5 和 3.3.3 Python 版本都是可重现的。

有趣的是，如果字符串的长度小于 20-25 个字符，search() 会立即返回。

发生了什么事？

Answer 1

理解这个问题需要理解 NFA 在 RegExp 下的工作原理。

详细阐述 NFA 的定义对我来说可能是一项过于沉重的任务。在 wiki 上搜索 NFA，它会给你一个更好的解释。这里只是认为 NFA 是一个机器人寻找你给出的模式。

粗略实现的 NFA 有点愚蠢，它只是向前看您提供的一两个 token 。因此，在您给出的综合示例中，NFA 首先看起来只是 \w+ (不是用于分组的括号)。

因为+是一个贪心量词，即匹配尽可能多的字符，所以NFA就傻傻的继续消耗target中的字符。在 30 个 a 之后，NFA 遇到字符串结尾。然后 NFA 意识到 he 需要匹配 template 中的其他 token 。下一个标记是 +。 NFA 已匹配它，因此它继续到 \.。这次失败了。

NFA 接下来要做的是后退一个字符，尝试通过截断 \w+ 的子匹配来匹配模式。所以 NFA 将 target 分成两组，29 个 a 一个 \w+，一个尾随 a . NFA 首先尝试通过将尾随 a 与第二个 + 进行匹配来使用它，但是当 NFA 遇到 \. 时它仍然失败。 NFA 继续上述过程，直到得到完全匹配，否则它将尝试所有可能的分区。

所以 (\w+)+\. 指示 NFA 以这种方式对 target 进行分组:target 被分成一组或多组，每组至少一个字符，目标以句点“.”结尾。只要期间不匹配。 NFA 尝试所有可能的分区。那么有多少分区呢？ 2^n，2 的指数。(想想在 a 之间插入分隔符)。如下图

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

如果 NFA 与 \. 匹配，则不会造成太大伤害。但是当匹配失败时，这个表达式就注定了是永无止境的指数。

我不是在打广告，但Mastering Regular Expression是一本了解RegExp下机制的好书。