Python正则表达式在创建组和后跟数字的某些字符时挂起

Question

我在Python 3中遇到了一个奇怪的情况。正在尝试查找某些字符（a-z），这些字符之间有一个句点和空格，后跟一个节号（0-2次），后跟一个空格，后跟数字（1次或多次）

在Python中运行时，我不会得到结果。它只是挂断了

import re
string = "Guidelines on International Protection: Membership in a “Particular Social Group” Within the Context of Article 1A(2) of the 1951 Convention and/or its 1967 Protocol Relating to the Status 
    ...: of Refugees (UNHCR Guidelines), U.N. Doc. HCR/GIP/02/02 (May 7, 2002)"
regex = r'((?:[a-z]+\.{0,1}\s*)+)(§{0,2})\s+(\d+)'
compile = re.compile(regex, flags=re.IGNORECASE)  
re.findall(compile,string)

在https://regexr.com/中，它实际上给了我正确的匹配：https://regexr.com/53394

发生了什么事

Answer 1

如果您在与Python兼容的正则表达式测试仪中测试您的正则表达式，您需要will see完成匹配需要大量的步骤，并以灾难性的回溯结束。这是由不在模式末尾的(?:[a-z]+\.{0,1}\s*)+模式引起的。当没有找到结果(§{0,2})\s+(\d+)时，它会强制正则表达式引擎严重回溯

修复方法是使模式匹配，使每个后续模式无法在同一位置匹配相同的文本

([a-z]+(?:(?:\s*\.\s*|\s+)[a-z]+)*)(§{0,2})\s+(\d+)
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

见regex demo

这里，(?:[a-z]+\.{0,1}\s*)+被替换为[a-z]+(?:(?:\s*\.\s*|\s+)[a-z]+)*：

• [a-z]+-1+ASCII字母（注意使用的re.IGNORECASE修饰符）
• (?:(?:\s*\.\s*|\s+)[a-z]+)*-0次或多次出现
  • (?:\s*\.\s*|\s+)-a.包含0+空格或1+空格
  • [a-z]+-1+ASCII字母

Answer 2

灾难性回溯问题的一个有效解决方案是，通过对捕获组使用正向前瞻来模拟atomic group（Python的re模块不支持）：

(?=((?:[a-z]+\.?\s*)+))\1§{0,2}\s*\d+

设置了多行和大小写无关标志。这避免了灾难性的回溯，因为前瞻不会放弃角色

Demo

更简洁的方法是在匹配一个或多个字母时使用possessive quantifier。可以使用正则表达式

(?:[a-z]++\.?\s*)+§{0,2}\s*\d+

设置了多行和大小写无关标志。这里所有格修饰语由++表示

Demo

不幸的是，Python的re模块不支持所有格修饰符，但它的替代PyPi module支持所有格修饰符

假设我们使用了regex(?:[a-z]+\.?\s*)+§{0,2}\s*\d+，它没有所有格修饰语

对于字符串

Within the Context. of Article 1A(2)

[a-z]+匹配Within the Context，然后\.?\s*匹配.。然后，正则表达式引擎继续尝试查找整个正则表达式的匹配项。如果失败，它将回溯考虑替代方案，并可能返回到{{CD5}}的匹配，此时它将返回“EEM>字符{{CD10}}（使匹配^ {CD11}}），在R{CD10}}之前重置ReGEX引擎的内部指针，并再次继续前进。

中的所有格修饰符++防止正则表达式引擎放弃其原始匹配Within the Context中的任何字符，从而避免灾难性的回溯问题。即使在灾难性回溯不是问题的地方，所有格修饰语也可以大大提高效率