8

かっこ内のテキストを見つけることになっている、小さくて素朴な正規表現を書きました。

re.search(r'\((.|\s)*\)', name)

いくつかの理由でこれが最善の方法ではないことはわかっていますが、問題なく機能していました。私が探しているのは、一部の文字列でこの式が指数関数的に長くかかり始め、その後終了しない理由についての説明です。昨夜、このコードを数か月実行した後、サーバーの1つが突然、次のような文字列と一致してスタックしました。

x (y)                                            z

私はそれを実験して、「y」と「z」の間のすべてのスペースで所要時間が2倍になることを確認しました。

In [62]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (22 * ' ') + 'z')
1 loops, best of 3: 1.23 s per loop

In [63]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (23 * ' ') + 'z')
1 loops, best of 3: 2.46 s per loop

In [64]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (24 * ' ') + 'z')
1 loops, best of 3: 4.91 s per loop

ただし、スペース以外の文字には同じ効果はありません。

In [65]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (24 * 'a') + 'z')
100000 loops, best of 3: 5.23 us per loop

注：私は、この問題に対するより良い正規表現や別の解決策を探していません。私たちはもうそれを使用していません。

4

2 に答える 2

6

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

CaffGeekの答えが正しく示唆しているように、問題は1つの形式の壊滅的なバックトラックによるものです。。2つの選択肢は両方ともスペース（またはタブ）に一致し、これは無制限に貪欲に適用されます。さらに、ドットは閉じ括弧と一致するため、開始括弧が一致すると、この式は常に文字列の最後に一致してから、最後の括弧を見つけるために丹念にバックトラックする必要があります。そして、このバックトラッキングプロセス中に、他の代替手段がの各場所で試行されます（これはスペースまたはタブでも成功します）。したがって、エンジンが1つの位置をバックトラックする前に、可能なすべての一致する組み合わせシーケンスを試行する必要があります。クロージングパレンの後にたくさんのスペースがあるので、これはすぐに合計されます。一致する閉じ括弧がある場合の特定の問題は、星の数量詞を怠惰にするだけで解決できます（つまり、r'\((.|\s)*?\)'）が、サブジェクト文字列に一致するクローズパレンがないオープニングパレンがある不一致の場合には、暴走正規表現の問題が依然として存在します。

元の正規表現は本当に、本当に悪いです！（また、複数のペアがある場合は、閉じている親と正しく一致しません）。

もちろん、最も内側の括弧に一致する正しい式（一致する場合と一致しない場合の両方で非常に高速です）は次のとおりです。

re_innermostparens = re.compile(r"""
    \(        # Literal open paren.
    [^()]*    # Zero or more non-parens.
    \)        # Literal close paren.
    """, re.VERBOSE)

すべての正規表現の作成者はMRE3を読む必要があります！

これはすべて、Jeffrey Friedlの必読の正規表現：Mastering Regular Expressions（3rd Edition）で、非常に詳細に説明されています（完全な例と推奨されるベストプラクティスを使用） 。これは私が今まで読んだ中で最も有用な本であると正直に言うことができます。正規表現は非常に強力なツールですが、ロードされた武器のように、細心の注意と精度で適用する必要があります（または、足で自分を撃ちます！）

于 2012-10-05T16:41:03.223 に答える
5

おそらくReDosの問題です。

参照： http： //en.wikipedia.org/wiki/ReDoS

正しく構築されていない正規表現に対して、正規表現のサービス拒否を作成することができます。

たとえば、ここから：https ://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

この正規表現^(a+)+$

ここに画像の説明を入力してください

入力aaaaXの場合、上のグラフには16の可能なパスがあります。ただし、aaaaaaaaaaaaaaaaXの場合、65536の可能なパスがあり、追加のaごとにその数は2倍になります。これは、ナイーブアルゴリズムが問題となる極端なケースです。これは、多くのパスを通過して失敗する必要があるためです。

すでに含まれているように、正規表現の問題の大部分は(.|\s)これがやや混乱していることだと思います。ただし、オプションポイントを作成します。\s.

編集：これは私が読んだ問題のより良い説明の1つだったと思います。

http://msdn.microsoft.com/en-us/magazine/ff646973.aspx

于 2012-10-05T15:18:19.493 に答える