なぜ私のPythonの正規表現が複数のグループをチェックしているのですか？

Question

この質問はDjango URLリゾルバに由来しますが、問題は一般的な問題のようです。

私はこのように構築されたURLを一致させたい：

1,2,3,4,5,6/10,11,12/ 

私が使用している正規表現は次のとおりです。

^(?P<apples>([]+,?)+)/(?P<oranges>([]+,?)+)/$ 

私が「有効」URL（すなわちに対してそれと一致するようにしようとすると

In [11]: print datetime.datetime.now(); re.compile(r"^(?P<apples>([]+,?)+)/(?P<oranges>([]+,?)+)/$").search("114,414,415,416,417,418,419,420,113,410,411,412,413/1/"); print datetime.datetime.now() 
2011-10-18 14:27:42.087883 
Out[11]: <_sre.SRE_Match object at 0x2ab0960> 
2011-10-18 14:27:42.088145 

ただし、「無効な」URL（一致しないもの）と一致させようとすると、 、全体の正規表現は何も返さないために、時間の大きさを取る：

In [12]: print datetime.datetime.now(); re.compile(r"^(?P<apples>([]+,?)+)/(?P<oranges>([]+,?)+)/").search("114,414,415,416,417,418,419,420,113,410,411,412,413/"); print datetime.datetime.now() 
2011-10-18 14:29:21.011342 
2011-10-18 14:30:00.573270 

私はいくつかのグループが一致する必要がある場合に非常に遅くなる正規表現エンジンで何かがあると仮定します。このための回避策はありますか？たぶん私の正規表現を修正する必要がありますか？

Answer 1

これは、PythonやPerlを含む多くの正規表現エンジンでよく知られている欠点です。何が起こっているのは、エンジンがバックトラックして、可能な試合の指数関数的な爆発を試してみることです。より良い正規表現エンジンは、そのような単純な正規表現のためにバックトラッキングを使用しません。

オプションのカンマを削除することで修正できます。これは、エンジンが123のような文字列を見て、それを(123)または(12)(3)または(1)(23)または(1)(2)(3)として解析するかどうかを決定できるようにするものです。これは3桁の数字だけを試してみるためにたくさんの試合が行われているので、どのようにして数十桁の速さでかなり急速に爆発するか見ることができます。

^(?P<apples>[0-9]+(,[0-9]+)*)/(?P<oranges>[0-9]+(,[0-9]+)*)/$ 

この

は常にグループ 123,456 (123),(456)として、決して (12)(3),(4)(56)または何か他のもののように正規表現エンジンを行います。その方法でのみ一致するので、バックトラックエンジンは、可能な解析のコンビナトリアル爆発を打つことはありません。ここでも、より良い正規表現エンジンはこの欠陥に悩まされません。

アップデート：私はそれを書いていた場合、私はそれをこのようにします：

^(?P<apples>[0-9,]+)/(?P<oranges>[0-9,]+)$ 

「これは（,/,のような）いくつかの偽のURLを一致しますが、あなたはいつもあなたの後に404を返すことができますそれを解析してそれをルーティングしました。

try: 
    apples = [int(x) for x in apples.split(',')] 
except ValueError: 
    # return 404 error 

Answer 2

あなたはこの正規表現を使用できます。d \

^(?P<apples>(?:\d+,)*\d+)/(?P<oranges>(?:\d+,)*\d+)/$ 

は、この問題を持っていない桁