Почему это так долго подходит? Это ошибка?

Question

мне нужно, чтобы соответствовать определенным URL-адреса в веб-приложения, то есть /123,456,789, и написал это регулярное выражение, чтобы соответствовать шаблону:

r'(\d+(,)?)+/$' 

Я заметил, что это, кажется, не оценивать, даже после нескольких минут при тестировании шаблона:

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523') 

Ожидаемый результат: совпадений не было.

Это выражение, однако, выполняется почти сразу (обратите внимание на слэш):

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523/') 

Является ли это ошибка?

Answer 1

Происходит некоторое число catastrophic backtracking, что приведет к экспоненциальному количеству обработки в зависимости от продолжительности строки несоответствия. Это связано с вашими вложенными повторениями и дополнительной запятой (хотя некоторые механизмы регулярных выражений могут определить, что это не будет соответствовать попытке выполнить все посторонние повторения). Это решается путем оптимизации выражения.

---

Самый простой способ сделать это, чтобы просто посмотреть на 1+ цифр или запятые через слэш и конец строки: [\d,]+/$. Тем не менее, это не идеально, так как это позволит что-то вроде ,123,,4,5/.

Для этого вы можете использовать слегка оптимизированную версию своей первоначальной попытки: (?:\d,?)+/$. Во-первых, я сделал вашу повторяющуюся группу non-capturing ((?:...)), которая не нужна, но она обеспечивает «более чистое совпадение». Далее, и единственный решающий шаг, я прекратил повторять \d внутри группы, так как группа уже повторяет. Наконец, я удалил ненужную группу вокруг необязательного ,, так как ? влияет только на последний символ. В значительной степени это будет выглядеть одна цифра, может быть, запятая, а затем повторить и, наконец, следовать за конечным /.

---

Это все еще может соответствовать нечетной строке 1,2,3,/, поэтому для щеколды это я улучшил свое оригинальное регулярное выражение с negative lookbehind: (?:\d,?)+(?<!,)/$. Это будет утверждать, что перед конечным / нет запятой.

Answer 2

Прежде всего, я должен сказать, что это не БУГ. из-за этого он пробует все возможности, требуется время и вычислительные ресурсы. Иногда он может сожрать много времени. Когда становится очень плохо, это называется катастрофическим обратным отсчетом.

Это код findall функции в python source код:

def findall(pattern, string, flags=0): 
    """Return a list of all non-overlapping matches in the string. 
    If one or more groups are present in the pattern, return a 
    list of groups; this will be a list of tuples if the pattern 
    has more than one group. 
    Empty matches are included in the result.""" 
    return _compile(pattern, flags).findall(string) 

Как вы видите, это просто использовать функцию compile(), поэтому, основываясь на _compile() функции, которые на самом деле использовать Traditional NFA, что использование питона для его соответствия регулярных выражений и base на это короткое объяснение о возврате в регулярном выражении в Освоение регулярных выражений, третье издание, Jeffrey EF Friedl!

Суть в NFA двигателя заключается в следующем: он рассматривает каждый подвыражению или компонент, в свою очередь, и всякий раз, когда он должен выбирать между двумя одинаково жизнеспособными вариантами, он выбирает один и запоминает другие, чтобы вернуться позже, если необходимость быть. Ситуации, в которых он должен принять решение среди курсов действий, включают в себя что-либо с квантором (решить, следует ли попробовать другое совпадение) и чередование (решить, какой из изменить родной, чтобы попробовать, и который оставить на потом). Какое бы действие не было предпринято, если оно выполнено успешно, а остальное регулярное выражение также успешное, матч завершен. Если что-либо в остальной части регулярного выражения в конечном итоге вызывает сбой, механизм регулярных выражений знает, что он может вернуться к тому, где он выбрал первый вариант , и может продолжить матч, попробовав другой вариант. Таким образом, в конечном итоге пытается все возможные перестановки регулярного выражения (или, по крайней мере, столько, сколько необходимо до тех пор, пока не будет найдено совпадение).

Пойдемте внутри шаблона: Так что у вас есть r'(\d+(,)?)+/$' с этой строкой '12345121,223456,123123,3234,4523,523523' мы это шаги:

• Во-первых, первая часть вашей строки (12345121) сопоставляется с \d+, затем , соответствует (,)?.
• Тогда на основе первого шага, то вся строка матч из-за + после группировки ((\d+(,)?)+)
• Тогда в конце концов, нет ничего для /$ быть согласованы. Поэтому (\d+(,)?)+ должен «отступить» до одного символа перед последним для проверки на /$. Опять же, он не находит правильного совпадения, поэтому после этого он (,) переходит к отступлению, тогда \d+ будет возвращаться, и этот откат будет продолжаться до тех пор, пока он не вернется None. Так что на основе длины вашей строки требуется время, которое в этом случае очень велико, и оно создает полностью вложенные кванторы !

Как приблизительно бенчмаркинга, в этом случае, у вас есть характер, так что вам нужно 3^39 возвратов попытки (мы имеем методы BackTrack).

Теперь для лучшего понимания, я измеряю время выполнения программы при изменении длины строки:

'12345121,223456,123123,3234,4523,' 3^33 = 5.559060567×10¹⁵ 
~/Desktop $ time python ex.py 

real 0m3.814s 
user 0m3.818s 
sys  0m0.000s 

'12345121,223456,123123,3234,4523,5' 3^24 = 1.66771817×10¹⁶ #X2 before 
~/Desktop $ time python ex.py 

real 0m5.846s 
user 0m5.837s 
sys  0m0.015s 

'12345121,223456,123123,3234,4523,523' 3^36= 1.500946353×10¹⁷ #~10X before 
~/Desktop $ time python ex.py 

real 0m15.796s 
user 0m15.803s 
sys  0m0.008s 

Таким образом, чтобы избежать этой проблемы, вы можете использовать один из перечисленных ниже способов:

• Atomic grouping (в настоящее время не поддерживает в Python, A RFE был создан, чтобы добавить его в Python 3)
• Reduction возможность ДКС ktracking, разбирая вложенные группы для разделения регулярных выражений.

Answer 3

Чтобы избежать катастрофического откаты я предлагаю

r'\d+(,\d+)*/$'