Python регулярное выражение повешено при создании группы и определенных символов, за которыми следуют цифры

Question

Я получаю странную ситуацию в Python 3. Попытка найти некоторые символы (az), которые имеют один период и пробел (ы) между ними, за которыми следует знак раздела (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 -совместимом тестере регулярных выражений, вы увидите , для завершения сопоставления требуется огромное количество шагов и заканчивается катастрофический c обратный поиск . Это вызвано шаблоном (?:[a-z]+\.{0,1}\s*)+, который не находится в конце шаблона. Это вынуждает механизм регулярных выражений сильно откатываться назад, когда не найден последующий (§{0,2})\s+(\d+).

Исправлено , позволяющее сопоставить шаблон так, чтобы каждый последующий шаблон не мог соответствовать одному и тому же тексту в том же месте. :

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

См. Демонстрационную версию regex

Здесь (?:[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+) - ., заключенных в 0+ пробелов или 1+ пробелов
  • [a-z]+ - 1+ букв ASCII.

Answer 2

Эффективное решение вашей проблемы катастрофы c возврата заключается в моделировании атома c группы (не поддерживается Python re модулем) используя положительный прогноз с группой захвата:

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

с установленными многострочными и регистрозависимыми флагами. Это позволяет избежать катастрофического возврата c, поскольку предвидение не подвержено отказу от символов.

Демо

Более понятный способ - использовать собственнический квантификатор при сопоставлении одного или нескольких вхождений буквы. Можно использовать регулярное выражение

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

с установленными многострочными и безразличными флагами. Здесь модификатор притяжения обозначается ++.

Демо

К сожалению, модуль re Python не поддерживает притяжательные модификаторы, но его альтернатива PyPi модуль делает.

Предположим, мы использовали регулярное выражение (?:[a-z]+\.?\s*)+§{0,2}\s*\d+, которое не имеет притяжательного модификатора.

Для строки

Within the Context. of Article 1A(2)

[a-z]+ соответствует Within the Context, затем \.?\s* соответствует .. Затем механизм регулярных выражений продолжает пытаться найти соответствие для всего регулярного выражения. Если это не удастся, он вернется к рассмотрению альтернатив и может вернуться к совпадению [a-z]+, после чего он вернет символ t (делая это совпадение Within the Contex), сбросит регулярное выражение внутренний указатель движка прямо перед t и еще раз продолжаем движение вперед.

притяжательный модификатор ++ in не позволяет движку regex отказаться от любых символов в исходном совпадении Within the Context, тем самым избегая catastrophi c проблема с возвратом. Даже там, где возвращение catastrophi c не является проблемой, притяжательные модификаторы, где их можно использовать, могут значительно повысить эффективность.