Предотвратить RegEx зависать на больших матчах

Question

Это отличное регулярное выражение для дат ... Тем не менее, оно бесконечно висит на этой странице, которую я пробовал ... Я хотел попробовать эту страницу (http://pleac.sourceforge.net/pleac_python/datesandtimes.html), потому что она имеет много даты на нем, и я хочу захватить их всех. Я не понимаю, почему он зависает, а не на других страницах ... Почему мое регулярное выражение зависает и / или как я могу очистить его, чтобы сделать его лучше / эффективнее?

Код Python:

monthnames = "(?:Jan\w*|Feb\w*|Mar\w*|Apr\w*|May|Jun\w?|Jul\w?|Aug\w*|Sep\w*|Oct\w*|Nov(?:ember)?|Dec\w*)"

pattern1 = re.compile(r"(\d{1,4}[\/\\\-]+\d{1,2}[\/\\\-]+\d{2,4})")

pattern4 = re.compile(r"(?:[\d]*[\,\.\ \-]+)*%s(?:[\,\.\ \-]+[\d]+[stndrh]*)+[:\d]*[\ ]?(PM)?(AM)?([\ \-\+\d]{4,7}|[UTCESTGMT\ ]{2,4})*"%monthnames, re.I)

patterns = [pattern4, pattern1]

for pattern in patterns:
    print re.findall(pattern, s)

кстати ... когда я говорю, что я пытаюсь сделать это на этом сайте ... Я пытаюсь сделать это на источнике веб-страницы.

Answer 1

Вы должны прочитать Освоение регулярных выражений . Проблема:

(?:[\d]*[\,\.\ \-]+)*

, что занимает экспоненциальное время. Попробуйте использовать:

(?:[\d,. \-]*[,. \-])?

, который должен соответствовать тем же вещам, но занимать линейное время. После проверки вашего примера это действительно ускоряет процесс.

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

[' Aug  6 20:43:20 2003', ' Mar 14 06:02:55 1973', ' March 14 06:02:55 AM 1973', ' Jun 16 20:18:03 1981']
['2003-08-06', '2003-08-07', '2003-07-23', '1973-01-18', '3/14/1973', '16/6/1981', '16/6/1981', '16/6/1981', '16/6/1981', '08/08/2003']

Чтобы разобраться в деталях (книга, на которую я ссылаюсь, очень хороша), * и + работают (в NFA, таких как python re), скорее как цикл. Внутренний цикл исходного шаблона будет сопоставляться с длинной цепью цифр, но если последующий шаблон не будет соответствовать, он будет «отказываться от них» по одному за раз. Затем внешний цикл перезапустит внутренний цикл на оставшемся паттерне и, конечно, сразу же снова возьмет цифры. Каждый раз, когда один экземпляр внутреннего цикла освобождает цифру, будет вызвана новая копия, чтобы получить ее снова. В конце концов, после того, как механизм прошел все возможные пути разбиения этой строки цифр (экспоненциальное число возможностей), он переместит начальную точку вперед на один символ ... и попытается снова.

С другой стороны, ваш паттерн выглядит немного помешанным;)

Answer 2

То, как написано регулярное выражение, вызовет лот возврата. В дополнение к совету о запуске его на небольших кусках текста, вы также можете использовать более простое (и, следовательно, более быстрое) регулярное выражение, отфильтровывающее текст, который не может соответствовать.

Answer 3

Во-первых, вы должны прочитать о том, что означает строка r"": вам нужно помещать обратную косую черту там, где вы действительно хотите обратную косую черту, поэтому ваше регулярное выражение должно быть просто:

monthnames = "(?:Jan\w*|Feb\w*|Mar\w*|Apr\w*|May|Jun\w?|Jul\w?|Aug\w*|Sep\w*|Oct\w*|Nov(?:ember)?|Dec\w*)"

pattern1 = re.compile(r"(\d{1,4}[-/]+\d{1,2}[-/]+\d{2,4})")

pattern4 = re.compile(r"(?:\d*[,. -]+)*%s(?:[,. -]+\d+[stndrh]*)+[:\d]*[ ]?(PM)?(AM)?([ -+\d]{4,7}|[UTCESTGMT ]{2,4})*"%monthnames, re.I)

Что касается вашей реальной проблемы, Python не очень хорошо работает с *, вложенным в *. Измените pattern4 на это (первое \d* становится \d+):

pattern4 = re.compile(r"(?:\d+[,. -]+)*%s(?:[,. -]+\d+[stndrh]*)+[:\d]*[ ]?(PM)?(AM)?([ -+\d]{4,7}|[UTCESTGMT ]{2,4})*"%monthnames, re.I)

и регулярное выражение возвращается быстро, печатая это:

[('', '', '2003'), ('', '', '1973'), ('', 'AM', ' 1973'), ('', '', '1981"')]
['2003-08-06', '2003-08-07', '2003-07-23', '1973-01-18', '3/14/1973', '16/6/1981', '16/6/1981', '16/6/1981', '16/6/1981'
, '08/08/2003']

хотя я не знаю, хотел ли ты этого.

Answer 4

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

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