6

http://daringfireball.net/2010/07/improved_regex_for_matching_urlsから取得した URL マッチング正規表現を使用しようとしています。

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

別の質問への回答に基づいて、この正規表現が壊滅的にバックトラックする場合があるようです。例えば：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)")

...実行に非常に長い時間がかかる場合があります（Chromeなど）

問題はコードのこの部分にあるように私には思えます:

(?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+

... とほぼ同等(.+|\((.+|(\(.+\)))*\))+のように見えますが、含まれているように見えます(.+)+

それを回避するために私ができる変更はありますか？

4

1 に答える 1

9

次のように変更すると、壊滅的なバックトラックが防止されます。

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

行われた唯一の変更は、正規表現の「バランスのとれた括弧」部分のそれぞれの+最初の後を削除することでした。[^\s()<>]

JS でテストするための 1 行バージョンを次に示します。

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

元の正規表現の問題部分は、バランスの取れた括弧セクションです。バックトラッキングが発生する理由の説明を簡単にするために、ここでは関係ないため、ネストされた括弧部分を完全に削除します。

\(([^\s()<>]+|(\([^\s()<>]+\)))*\)    # original
\(([^\s()<>]+)*\)                     # expanded below

\(                # literal '('
(                 # start group, repeat zero or more times
    [^\s()<>]+        # one or more non-special characters
)*                # end group
\)                # literal ')'

ここで string'(AAAAA'で何が起こるかを考えてみましょう。リテラル(は一致AAAAAしてからグループによって消費され、 は)一致しません。この時点で、グループは 1 つAのAAAA. *グループにはそれに続くグループがあるため、グループは複数回一致する可能性があるため、([^\s()<>]+)*一致するAAAAがあり、次にA2 番目のパスで一致します。これが失敗するAと、元のキャプチャによって追加が放棄され、2 番目のキャプチャによって消費されます。

これが長時間続くと、次のように照合が試行されます。カンマで区切られた各グループは、グループが照合された異なる時刻と、インスタンスが照合された文字数を示します。

AAAAA
AAAA, A
AAA, AA
AAA, A, A
AA, AAA
AA, AA, A
AA, A, AA
AA, A, A, A
....

カウントが間違っている可能性がありますが、正規表現が一致しないと判断されるまでに最大 16 のステップが追加されると確信しています。文字列に文字を追加し続けると、これを理解するためのステップ数が指数関数的に増加します。

を削除して+に変更すると\(([^\s()<>])*\)、この後戻りのシナリオを回避できます。

ネストされた括弧をチェックするために代替を再度追加しても、問題は発生しません。

文字列の最後にある種のアンカーを追加したい場合があることに"http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"注意し(てください.re.test(...)truehttp://google.com/?q=

于 2012-04-18T22:20:03.893 に答える