長い文字列と照合するときに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()) 

これは、最初の4つの発生を出力しますが、それがハングアップします。私は、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 

私は単純に再でそれをしようとすると、それが正常に動作します。

私はこれをWindows XPのCygwin上で動作するPython 2.5.4で実行しています。

私は非常に短い文字列でハングすることができました。

ddddddeddbedddbdddddddddddddddddddddddd 

そして、これと：それは返す（そしてマッチを表示しない）のに約15秒かかった。この39文字の文字列で

ddddddeddbedddbddddddddddddddddddddddddddddddddddd 

：この50文字の文字列で、それは、約5分後に返さ​​れることはありませんそれはすぐに返す文字列：

ddddddeddbedddbdddddddddddddd 

Answer 1

確かに指数関数的振る舞い。あなたはregexpに非常に多くの部分を持っています。それは、長い文字列になったときに狂ったように戻ってくるでしょうが、それ以前のものにはマッチしません。あなたはregexpを再考する必要があるので、試してみる可能性の低いパスがあります。特に

私は思う：彼らは別の試合の再試行を強制するだろうと

([ef]d\*b|d\*)*</pre></code> and <code><pre>([ef]|([gh]d\*(ad\*[gh]d)\*b))d\*b 

は、再考が必要な場合があります。また、それらは一致するものに関しても重複します。彼らは両方ともedbとマッチしますが、失敗して逆戻りしようとすると、おそらく他の部分と同じ動作になります。

できるだけ|を使用しないようにして、できればパターンが重複しないようにしてください。

Answer 2

が、それはあなたの表現は、Python REエンジンで指数関数的行動をトリガーすることだろうか？

This articleは問題を扱います。時間があれば、それらのアイディアを使って開発されたREエンジンで表現を実行してみてください。

Answer 3

あなたはすでに答えを出しました。正規表現は複雑で曖昧です。

処理が簡単で、あまり複雑ではなく、より明確な表現を見つけようとする必要があります。または、あなたが達成したいことを教えてください。私たちはあなたが何かを見つけるのを手伝うことができます。

---

編集あなたはちょうどあなたがJohn Montgomery’s answerにコメントで言ったように、すべての位置にdのを許可したい場合は、パターンをテストする前にそれらを削除する必要があります

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()) 

Answer 4

私はあなたが経験だと思います"壊滅的なバックトラッキング"として知られているもの。

あなたのregexには多くのオプション/代替パーツがありますが、それらのすべてがまだ一致しようとしています。したがって、前のサブ式はローカル失敗時に次の式に戻る文字を返します。これにより、正規表現内でのバックワード・アンド・アット・ビヘイビアが発生し、指数関数的に実行時間が増加します。

Python（2.7 +？、わからない）は、アトミックグループ化と所有量限定子をサポートしています。正規表現を調べて、一致するかどうかを判断することができます。不必要なバックトラッキングは、それを制御することができます。

Answer 5

壊滅的なバックトラッキング！

正規表現は非常に高価です。特定の（意図しない意図された）文字列は、RegExesに指数関数的な振る舞いを示す可能性があります。これに対していくつかの修正が行われました。 RegExesはとても便利ですが、開発者は実際にどのように動作するかを理解する必要があります。私たちは彼らに噛まれました。

例およびデバッガ：

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

Answer 6

非常に参考になったすべての回答に感謝します。結局のところ、驚くべきことに、それをスピードアップするのは簡単でした。

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

は、今では上のほぼ瞬時に動作します：|：ここでは、元の正規表現だ終わり近くに、私は必要なものは本当にありませんでしたD *ので、次のように私はそれを修正

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

私は気づい65,536文字列。私は今、私は正規表現が実際に一致するために必要な文字列と一致していることを確認する必要があると思います...