жадный и жадный в модуле

Question

В чем разница между/(a ​​+) + c/и/(a ​​+) c/in re модулем? Я проверил, сколько времени потребуется для выполнения. Была большая разница. Я хочу знать, почему существует большая разница. Я ввел этот образец в форму онлайн-тестера регулярных выражений, но я не понял, что происходит. Пожалуйста, скажите мне слова.

import re 
from time import clock  
def test(f, *args, *kargs): 
    start = now() 
    f(*args, *kargs) 
    print("The function %s lasted: %f" % (f.__name__, now() - start)) 

def catastrophic1(n): 
    print("Testing with %d characters" % n) 
    pat = re.compile("(a+)+c") 
    text = "%s" % 'a' * n 
    pat.search(text) 

def catastrophic2(n): 
    print("Testing with %d characters" % n) 
    pat = re.compile("(a+)c") 
    text = "%s" % 'a' * n 
    pat.search(text) 

for n in range(13, 20): 
    test(catastrophic1, n) 
for n in range(13, 20): 
    test(catastrophic2, n) 

Answer 1

оба выражения совпадают то же самое, а именно один или несколько a с последующим одним c.

Выражение (a+)+c занимает больше времени для обработки движка регулярного выражения, поскольку существует больше способов, чтобы строка из a s соответствовала этому выражению.

Например, используя второе выражение, строка aaaaaa может быть разбита на следующие группы

(a)(a)(a)(a)(a)(a) # here (a+) matches a single 'a' 
(aa)(aa)   # here (a+) matches 'aa' 
(aaa)(aaa)   # here (a+) matches 'aaa' 

Answer 2

Ответ этой проблемы зависит от вас, что можно понять, как интерпретировать питон регулярное выражение двигатель внутреннего + и что он делает для соответствия шаблону.

На самом деле питон движок регулярных выражений использует Traditional NFA для своих регулярных выражений спичек и на основе сущности двигателя NFA, что:

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

И помимо предыдущих процессов для + регулярных выражений будет пытаться все комбинации предыдущего шаблона с длиной 1 или более для шаблона, такого как (a+)+c, мы имеем экспоненциальное число попыток! и он будет сожрать много времени!

---

_{* Регулярные выражения, Третье издание, Джеффри Е. Ф. Фридль!}