re.findall regex зависает или очень медленно

Question

Мой входной файл - это большой файл txt с конкатенированными текстами, которые я получил из открытой текстовой библиотеки. Теперь я пытаюсь извлечь только содержимое самой книги и отфильтровывать другие материалы, такие как отказ от ответственности и т. Д. Таким образом, у меня есть около 100 документов в большом текстовом файле (около 50 мб).

Затем я определил маркеры начала и конца самого содержимого и решил использовать регулярное выражение Python, чтобы найти все, что находится между маркером начала и конца. Чтобы подвести итог, регулярное выражение должно искать маркер начала, затем сопоставлять все после него и прекращать просмотр после достижения конечного маркера, а затем повторять эти шаги до тех пор, пока не будет достигнут конец файла.

Следующий код работает безупречно, когда я кормлю небольшой файл 100Кб размера в него:

import codecs 
import re 

outfile = codecs.open("outfile.txt", "w", "utf-8-sig") 
inputfile = codecs.open("infile.txt", "r", "utf-8-sig") 
filecontents = inputfile.read() 
for result in re.findall(r'START\sOF\sTHE\sPROJECT\sGUTENBERG\sEBOOK.*?\n(.*?)END\sOF\THE\sPROJECT\sGUTENBERG\sEBOOK', filecontents, re.DOTALL): 
    outfile.write(result) 
outfile.close() 

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

Я очень уверен, что источником проблемы является (. *?) часть регулярного выражения, в сочетании с re.DOTALL. Когда я использую аналогичное регулярное выражение на меньших расстояниях, скрипт будет работать нормально и быстро. Теперь мой вопрос: почему это просто замерзает все? Я знаю, что текст между разделителями невелик, но файл размером 50 Мб не должен быть слишком большим, чтобы справиться, верно? Возможно, мне недостает более эффективного решения?

Заранее спасибо.

Answer 1

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

Обычное решение состоит в том, чтобы заменить . классом символов, который является более конкретным, обычно это производство, которое вы пытаетесь прервать первым .*. Что-то вроде:

`[^\n]*(.*)` 

так, чтобы группа захвата могла соответствовать только первой новой строке до конца. Другой вариант заключается в том, чтобы признать, что решение с регулярным выражением может не быть лучшим подходом и использовать либо контекстное свободное выражение (например, pyparsing), либо путем первого разбиения ввода на более мелкие, более простые для обработки фрагменты (например, с corpus.split('\n'))