re.findall regexがハングアップまたは非常に遅い

Question

私の入力ファイルは、開いたテキストライブラリから得た連結テキストを含む大きなtxtファイルです。私は今、本自体の内容だけを抽出し、免責事項などの他のものを除外しようとしています。私は大きなテキストファイル（約50MB）に約100の文書を持っています。

次に、コンテンツ自体の開始マーカーと終了マーカーを特定し、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と組み合わせて、正規表現の一部である （。*？） の部分であることを確信しています。 類似の正規表現を使用すると、スクリプトはすばやく高速に実行されます。 私の質問は今です：なぜこれがすべてを凍結しているのですか？区切り文字の間のテキストは小さいわけではないが、50MBのファイルはあまり扱うべきではないはずです。 もっと効率的なソリューションが見つからないのでしょうか？

ありがとうございます。

Answer 1

複数回表示されるシーケンス.*を使用すると問題が発生すると考えても問題ありません。問題は、ソルバーが.*の多くの可能な組み合わせを試みており、結果はcatastrophic backtrackingとなります。

普通の解決策は、.を、より具体的な文字クラス、通常は最初に.*を終了しようとするプロダクションに置き換えることです。以下のような何か：

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

キャプチャグループのみが最後まで最初の改行から一致させることができるように

。もう1つの選択肢は、正規表現の解法が最良のアプローチではないことを認識し、文脈自由表現（例えば pyparsing）を使用するか、入力をより小さく分かりやすいチャンクに分割することです（例えば corpus.split('\n')）