Finditer зависает при сопоставлении с длинной строкой

Question

У меня есть несколько сложное регулярное выражение, которое я пытаюсь сопоставить с длинной строкой (65 535 символов). Я ищу несколько вхождений re в строке, и поэтому я использую finditer. Это работает, но по какой-то причине зависает после определения первых нескольких случаев. Кто-нибудь знает, почему это может быть? Вот фрагмент кода:

pattern = "(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)"

matches = re.finditer(pattern, string)
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

Распечатывает первые четыре вхождения, но затем зависает. Когда я убиваю его с помощью Ctrl-C, он говорит мне, что он был убит в итераторе:

Traceback (most recent call last):
  File "code.py", line 133, in <module>
    main(sys.argv[1:])
  File "code.py", line 106, in main
    for match in matches:
KeyboardInterrupt

Если я попробую его с более простой ре, он отлично работает.

Я запускаю это на python 2.5.4, работающем на Cygwin под Windows XP.

Мне удалось заставить его висеть на очень короткой струне. С этой строкой из 50 символов она не возвращается через 5 минут:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

Для этой 39-символьной строки потребовалось около 15 секунд, чтобы вернуться (и не отобразить совпадений):

ddddddeddbedddbdddddddddddddddddddddddd

И с этой строкой она мгновенно возвращается:

ddddddeddbedddbdddddddddddddd

Answer 1

Определенно экспоненциальное поведение. У вас так много d* частей в вашем регулярном выражении, что он будет возвращаться назад, как сумасшедший, когда он доберется до длинной строки d, но не сможет что-то сопоставить ранее. Вам нужно переосмыслить регулярное выражение, чтобы у него было меньше возможных путей.

В частности, я думаю:

<code>([ef]d\*b|d\*)*

и <pre>([ef]|([gh]d\*(ad\*[gh]d)\*b))d\*b

Возможно, нужно переосмыслить, так как они заставят повторить альтернативный матч. Плюс они также пересекаются с точки зрения того, что они соответствуют. Например, они оба сопоставили бы edb, но если один не удастся и попытается вернуться назад, другая часть, вероятно, будет иметь такое же поведение.

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

Answer 2

Может ли быть, что ваше выражение вызывает экспоненциальное поведение в движке Python RE?

Эта статья посвящена проблеме. Если у вас есть время, вы можете попробовать запустить выражение в механизме RE, разработанном с использованием этих идей.

Answer 3

Спасибо за все ответы, которые были очень полезны. В конце концов, на удивление, было легко ускорить его. Вот оригинальное регулярное выражение:

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)

Я заметил, что | d * ближе к концу не то, что мне нужно, поэтому я изменил его следующим образом:

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*bd*)*c)

Теперь он работает почти мгновенно на строке 65,536 символов. Полагаю, теперь мне просто нужно убедиться, что регулярное выражение действительно соответствует строкам, которые мне нужны, чтобы соответствовать ...

Answer 4

катастрофический возврат!

Регулярные выражения могут быть очень дорогими. Определенные (непреднамеренные и предполагаемые) строки могут вызывать экспоненциальное поведение RegExes Мы взяли несколько исправлений для этого. RegEx очень удобны, но разработчики действительно должны понимать, как они работают; мы их укусили.

пример и отладчик:

http://www.codinghorror.com/blog/archives/000488.html

Answer 5

Я думаю, что вы испытываете то, что известно как "катастрофический возврат".

В вашем регулярном выражении есть много необязательных / альтернативных частей, которые все еще пытаются найти совпадение, поэтому предыдущие подвыражения возвращают символы следующему выражению при локальном сбое. Это приводит к обратному и четвертому поведению в регулярном выражении и экспоненциальному увеличению времени выполнения.

Python (2.7+ ?, я не уверен) поддерживает атомарную группировку и собственнические квантификаторы, вы можете проверить свое регулярное выражение, чтобы определить части, которые должны совпадать или не работать в целом. С помощью этого можно взять под контроль ненужный возврат.

Answer 6

Вы уже дали себе ответ: регулярное выражение сложное и неоднозначное.

Вы должны попытаться найти менее сложное и более четкое выражение, которое легче обрабатывать. Или скажите нам, чего вы хотите достичь, и мы можем попытаться помочь вам найти его.

---

Редактировать Если вы просто хотите разрешить d с в каждой позиции, как вы сказали в комментарии к ответ Джона Монтгомери , вы должны удалить их перед тестированием шаблона: 1011 *

import re

string = "ddddddeddbedddbddddddddddddddddddddddddddddddddddd"
pattern = "(([ef]|([gh](a[gh])*b))b([ef]b)*c)"
matches = re.finditer(pattern, re.sub("d+", "", string))
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())