为什么我的Python正则表达式模式运行得这么慢？

Question

请参阅我的正则表达式模式代码:

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import re

print 'Start'
str1 = 'abcdefgasdsdfswossdfasdaef'
m = re.match(r"([A-Za-z\-\s\:\.]+)+(\d+)\w+", str1) # Want to match something like 'Moto 360x'
print m # None is expected.
print 'Done'

完成需要49秒,模式有什么问题吗？

Answer 1

请参阅失控正则表达式:灾难性回溯.

简而言之,如果有很多组合,子字符串可以拆分为正则表达式的各个部分,则正则表达式匹配器最终可能会尝试全部.

构造类似(x+)+并且x+x+实际上保证了这种行为.

要检测并修复有问题的构造,可以使用以下概念:

• 在概念层面,有问题的构建体的存在意味着你的正则表达式是不明确的 -也就是说,如果你忽略贪婪/懒惰的行为,有一些文字没有单一的"正确"分裂成正则表达式的部分(或等价地,其子表达式).因此,为了避免/解决问题,您需要查看并消除所有歧义.

  • 一种方法是

    • 总是将文本分成有意义的部分(=对手头任务有不同含义的部分),和
    • 以这样的方式定义部件,使它们不会混淆(=使用你自己用来判断哪个特性,如果你手工解析它)