为什么我的Python正则表达式检查多个组花了这么长时间？

Question

这个问题起源于Django URL解析器,但问题似乎是一般的问题.

我想匹配这样构建的URL:

1,2,3,4,5,6/10,11,12/

我正在使用的正则表达式是:

^(?P<apples>([0123456789]+,?)+)/(?P<oranges>([0123456789]+,?)+)/$

当我尝试将其与"有效"URL(即匹配的URL)匹配时,我得到即时匹配:

In [11]: print datetime.datetime.now(); re.compile(r"^(?P<apples>([0123456789]+,?)+)/(?P<oranges>([0123456789]+,?)+)/$").search("114,414,415,416,417,418,419,420,113,410,411,412,413/1/"); print datetime.datetime.now()
2011-10-18 14:27:42.087883
Out[11]: <_sre.SRE_Match object at 0x2ab0960>
2011-10-18 14:27:42.088145

但是,当我尝试匹配"无效"URL(不匹配)时,整个正则表达式需要一定的时间才能返回任何内容:

In [12]: print datetime.datetime.now(); re.compile(r"^(?P<apples>([0123456789]+,?)+)/(?P<oranges>([0123456789]+,?)+)/").search("114,414,415,416,417,418,419,420,113,410,411,412,413/"); print datetime.datetime.now()
2011-10-18 14:29:21.011342
2011-10-18 14:30:00.573270

我假设regexp引擎中有一些东西在需要匹配几个组时极度减慢.这有什么解决方法吗？也许我的正则表达式需要修复？

Answer 1

这是许多正则表达式引擎中的已知缺陷,包括Python和Perl.正在发生的事情是引擎正在回溯并且可能会出现指数级别的可能匹配.更好的正则表达式引擎不会使用回溯来实现这种简单的正则表达式.

您可以通过删除可选的逗号来修复它.这就是让发动机看像一个字符串123,并决定是否将其解析为(123)或(12)(3)或(1)(23)或(1)(2)(3).这是为了尝试三位数而进行的很多比赛,所以你可以看到它会如何快速地爆发几十个数字.

^(?P<apples>[0-9]+(,[0-9]+)*)/(?P<oranges>[0-9]+(,[0-9]+)*)/$

这将使正则表达式引擎始终组123,456的(123),(456)和从来没有像(12)(3),(4)(56)或别的东西.因为它只会以这种方式匹配,所以回溯引擎不会遇到可能的解析组合爆炸.同样,更好的正则表达式引擎不会受到这个缺陷的影响.

更新:如果我正在写它,我会这样做:

^(?P<apples>[0-9,]+)/(?P<oranges>[0-9,]+)$

这会匹配一些伪造的URL(例如,/,),但是在解析并路由它之后总是可以返回404.

try:
    apples = [int(x) for x in apples.split(',')]
except ValueError:
    # return 404 error