Python - бесконечное выполнение

Я пытаюсь выполнить этот код:

import re
pattern = r"(\w+)\*([\w\s]+)*/$"
re_compiled = re.compile(pattern)
results = re_compiled.search('COPRO*HORIZON 2000                 HOR')
print(results.groups())

Но Python не отвечает. Процесс занимает 100% от ЦП и не останавливается. Я пробовал это как на Python 2.7.1, так и на Python 3.2 с одинаковыми результатами.

Ответы

Ответ 1

Ваше регулярное выражение работает в катастрофическом обратном отслеживании, потому что у вас есть вложенные кванторы (([...]+)*). Поскольку вашему регулярному выражению требуется, чтобы строка заканчивалась на / (что не удается на вашем примере), механизм regex пытается перестановок строки в тщетной надежде найти соответствующую комбинацию. То, где он застревает.

Чтобы проиллюстрировать, допустим "A*BCD" как вход в ваше регулярное выражение и посмотреть, что произойдет:

  • (\w+) соответствует A. Хорошо.
  • \* соответствует *. Yay.
  • [\w\s]+ соответствует BCD. OK.
  • / не соответствует (никаких символов не осталось). ОК, пусть резервное копирование одного символа.
  • / не соответствует D. Hum. Вернемся еще немного.
  • [\w\s]+ соответствует BC, а повторение [\w\s]+ соответствует D.
  • / не соответствует. Резервное копирование.
  • / не соответствует D. Создайте резервную копию еще.
  • [\w\s]+ соответствует B, а повторение [\w\s]+ соответствует CD.
  • / не соответствует. Создайте резервную копию снова.
  • / не соответствует D. Еще раз создайте резервную копию.
  • Как насчет [\w\s]+ соответствует B, повторяется [\w\s]+ соответствует C, повторяется [\w\s]+ соответствует D? Нет? Попробуйте что-то еще.
  • [\w\s]+ соответствует BC. Позвольте остановиться здесь и посмотреть, что произойдет.
  • Darn, / по-прежнему не соответствует D.
  • [\w\s]+ соответствует B.
  • По-прежнему не повезло. / не соответствует C.
  • Эй, вся группа необязательна (...)*.
  • Нет, / по-прежнему не соответствует B.
  • Хорошо, я сдаюсь.

Теперь это была строка из трех букв. У вас было около 30, пытаясь все перестановки, которые заставили бы ваш компьютер заняты до конца дней.

Я предполагаю, что вы пытаетесь получить строки до/после *, и в этом случае используйте

pattern = r"(\w+)\*([\w\s]+)$"

Ответ 2

Интересно, что Perl работает очень быстро

-> perl -e 'print "Match\n" if "COPRO*HORIZON 2000                 HOR" =~ m|(\w+)\*([\w\s]+)*/$|'
-> perl -e 'print "Match\n" if "COPRO*HORIZON 2000                 HOR/" =~ m|(\w+)\*([\w\s]+)*/$|'
Match

Ответ 3

Попробуйте re2 или любую другую базу движений регулярных выражений в теории автоматов. Тот, который находится в текущем модуле python re, является простым и медленным механизмом обратного отслеживания (теперь все может измениться в будущем). Но автоматы, основанные на двигателях, имеют некоторые ограничения, но не позволят вам использовать обратные ссылки, например. Поделитесь с этой страницей синтаксиса re2, чтобы узнать, удовлетворит ли она ваши потребности или нет.

Ответ 4

Похоже, это может быть что-то в вашем шаблоне. Я не уверен, что вы пытаетесь сделать с последним "*" в своем выражении. Для меня работает следующий код:

import re

pattern = r"(\w+)\*([\w\s]+)$"

re_compiled = re.compile(pattern)

results = re_compiled.search('COPRO*HORIZON 2000                 HOR')

print(results.groups())