非常慢的正则表达式搜索

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

>>> 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()返回.

怎么了？

了解此问题需要了解NFA在RegExp下的工作方式.

阐述NFA的定义对我来说可能是一项过于繁重的任务.在维基上搜索NFA,它会为您提供更好的解释.这里只想NFA是一个机器人发现你给出的模式.

粗暴地实施NFA有点愚蠢,它只是向前看你给的一两个代币.所以在你给出的合成例子中,NFA \w+首先看一下(不是用于分组的括号).

因为+是一个贪婪的量词,也就是说,匹配尽可能多的字符,所以NFA愚蠢地继续消耗字符target.30 a秒后,NFA遇到字符串结尾.之后,NFA意识到他需要匹配其他令牌template.下一个标记是+.NFA已匹配,因此它继续进行\..这次失败了.

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

因此,(\w+)+\.指示NFA以target这种方式分组:目标被划分为一个或多个组,每组至少一个字符,目标以句点"."结束.只要期间不匹配.NFA尝试所有分区.那么有多少分区？2 ^ n,指数为2.(JUst认为插入分隔符之间a).如下

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

如果NFA匹配\.,它不会伤害太多.但是当它无法匹配时,这个表达式注定永无止境的指数.

我不是广告,但掌握正则表达式是理解RegExp机制的好书.

缓慢是由引擎的回溯引起的:

(\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++)\.