正则表达式永远在短字符串上。

Question

我在看一堆字符串，试图用下面的模式匹配一些。你知道吗

location_pattern = re.compile( r"""
                                \b
                                (?P<location>
                                    ([A-Z]\w*[ -]*)+[, ]+
                                    (
                                      [A-Z]{2}
                                        |
                                      [A-Z]\w+\ *\d  ##
                                    )
                                )
                                \b 
                                """, flags=re.VERBOSE)

现在，这个regex在我的几乎所有数据集上都可以运行，但是在这个特定字符串上需要永远（好的，5秒）：

' JAVASCRIPT   SOFTWARE   ARCHITECT,   SUCCESSFUL   SERIAL'

在我的输入数据的某个点上有一堆这样的字符串（所有的大写字母，很多空格字符），程序在点击它时会大大减慢速度。我试着取出正则表达式的不同部分，结果发现罪魁祸首是
\*\d在注释行的末尾。你知道吗

我想了解这是如何导致regex验证花费这么长时间的。你知道吗

有人能帮忙吗？你知道吗

Answer 1

除了格雷格的回答，你还有一个模式：

([A-Z]\w*[ -]*)+
        ^  ^-^   Note embedded quantifiers!

在重复的组中使用量词（更糟糕的是你有两个量词）通常会产生灾难性的回溯问题。因此，我会重新考虑正则表达式。你知道吗

注释：如果您稍后通过更新我的答案添加更多示例数据和预期输出，我可以为您提供另一个regex。你知道吗

Answer 2

删除\ *\d之所以有效，是因为您只是将问题中的示例从一个不匹配的案例转换为一个匹配的案例。在回溯引擎中，匹配的案例通常比不匹配的案例花费更少的时间，因为在不匹配的案例中，引擎必须用尽搜索空间才能得出这个结论。你知道吗

联邦快递（Fede）正确地指出了问题所在（不过，这种解释相当不准确）。你知道吗

([A-Z]\w*[ -]*)+

由于[ -]*是可选的，\w可以匹配[A-Z]，因此上面的正则表达式退化为([A-Z][A-Z]*)+，这与灾难性回溯(A*)*的经典示例相匹配。退化形式还表明，问题表现在大写字母的长字符串上。你知道吗

碎片本身不会造成多大伤害。但是，只要续集（上面片段后面的内容）失败，就会导致灾难性的回溯。你知道吗

这里有一种重写它的方法（不知道您的确切要求）：

[A-Z]\w*(?:[ -]+[A-Z]\w*)*[ -]*

通过强制[ -]+至少为一次，模式就不能再以多种方式匹配大写字母字符串。你知道吗