为什么我的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

见Runaway Regular Expressions: Catastrophic Backtracking。你知道吗

简言之，如果有非常多的组合，一个子串可以被分割成正则表达式的各个部分，正则表达式匹配器可能最终会尝试所有这些组合。你知道吗

像(x+)+和x+x+这样的结构实际上保证了这种行为。你知道吗

要检测和修复有问题的构造，可以使用以下概念：

• 在概念层面上，有问题的构造意味着正则表达式是不明确的，也就是说，如果忽略贪婪/懒惰的行为，就不会有一个“正确”的将某些文本分割成正则表达式的部分（或者，等价地，它的子表达式）。因此，为了避免/解决问题，您需要看到并消除所有的歧义。你知道吗

  • 一种方法是

    • 始终将文本分成有意义的部分（=对手头的任务有不同意义的部分），并且
    • 以一种不会混淆的方式定义这些部分（=使用相同的特征，如果你是手工解析的话，你自己会用这些特征来判断哪个是哪个）