以下の文字列を正規表現の入力として使用すると、Java が 100% の CPU 使用率でハングします。
使用される正規表現:
これは、私のアプリケーションの説明フィールドに使用される正規表現です。
^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+
テストに使用する文字列:
Provider_One からの SaaS サービス VLAN
ディディエ SPT での 2 回目の試みは、彼が私にくれた最初のものが間違っていたためです :-(
同じ文字列を異なる組み合わせで分割すると、正しく機能します。「Provider_One からの SaaS サービス VLAN」のように、「彼が最初にくれたものは間違っていました :-(」など。Java は上記の文字列に対してのみハングしています。
また、以下のように正規表現を最適化しようとしました。
^([\\w\\-\\.\\&\\,]+[\\s]*)+
これでも動作しません。
壊滅的なバックトラックのもう1つの典型的なケース。
:ネストされた数量詞を使用すると、文字クラスの一部ではない入力文字列で正規表現がに到達したときに、膨大な数の順列がチェックされます（.matches()メソッドを使用していると仮定します）。
この正規表現の問題を単純化してみましょう。
^([^:]+)+$
そしてこの文字列：
1234:
正規表現エンジンはチェックする必要があります
1234 # no repetition of the capturing group
123 4 # first repetition of the group: 123; second repetition: 4
12 34 # etc.
12 3 4
1 234
1 23 4
1 2 34
1 2 3 4
...そしてそれは4文字だけです。サンプル文字列では、RegexBuddyは100万回の試行後に中止されます。Javaは喜んでチャグを続けます...これらの組み合わせのどれも以下:が一致することを許さないことを最終的に認める前に。
どうすればこれを解決できますか？
所有格の数量詞を使用して、正規表現のバックトラックを禁止できます。
^([A-Za-z0-9_.&,-]++\\s*+)+
正規表現がより速く失敗することを可能にします。ちなみに、不要な円記号はすべて削除しました。
編集：
いくつかの測定：
文字列"was wrong :-)"では、RegexBuddy862の手順で不一致を特定します。
の場合"me was wrong :-)"、1,742ステップです。
の場合"gave me was wrong :-)"、14,014ステップ。
の場合"he gave me was wrong :-)"、28,046ステップ。
の場合"one he gave me was wrong :-)"、112,222ステップ。
の場合"first one he gave me was wrong :-)"、>1,000,000ステップ。
まず、正規表現が指定された入力文字列と一致しないことを理解する必要があります。文字列には、 「単語」文字ではないいくつかの文字（'<' '>' '/' ':'および）が含まれています。')'
では、なぜそんなに時間がかかるのでしょうか。
基本的に「壊滅的なバックトラック」。より具体的には、正規表現の繰り返し構造は、正規表現のバックトラッキングアルゴリズムが試すための指数関数的な数の選択肢を提供します。
正規表現の内容は次のとおりです。
問題は「ゼロ以上のスペース文字」の部分にあります。初めて、マッチャーは最初の予期しない文字（つまり'<'）まですべてを照合します。次に、少し後退して、最後の文字の前に「ゼロスペース」を含む別の方法で再試行します。それが失敗すると、「ゼロスペース」を1つ戻します。
問題は、Nスペース以外の文字を含む文字列のN場合、「ゼロスペース」を一致させることができるさまざまな場所があり、それによって2^Nさまざまな組み合わせが作成されることです。それは成長するにつれて急速に巨大な数に変わりN、最終結果は無限ループと区別するのが困難です。
なぜ他の文字とは別に空白を一致させるのですか？そして、なぜあなたは試合を最初に固定しているのに、最後には固定していないのですか？文字列が空白で開始または終了しないようにする場合は、次のようにする必要があります。
^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$
これで、正規表現エンジンが文字列を通過できる「パス」は1つだけになります。[A-Za-z0-9_.&,-]最後に到達する前に一致する文字が不足し、次の文字が一致しない\s場合、すぐに失敗します。空白文字を一致させたまま最後に到達した場合、空白を実行するたびに少なくとも1つの非空白文字を一致させる必要があるため、失敗します。
非空白の実行を区切る空白文字が1つだけあることを確認したい場合は、以下から数量詞を削除して\s+ください。
^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$
空白が非空白との関係でどこにあるかを気にしない場合は、それらすべてを同じ文字クラスと一致させるだけです。
^[A-Za-z0-9_.&,\s-]+$
:とスマイリーが原因で正規表現が指定された入力と一致しないことを知っていると思いますが(、失敗するのになぜこれほど時間がかかるのかを知りたいだけです。
そしてもちろん、Java文字列リテラルの形式で正規表現を作成しているので、次のように記述します。
"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$"
また
"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$"
また
"^[A-Za-z0-9_.&,\\s-]+$"
（元の質問に二重の円記号があったことは知っていますが、SOの優れたコード書式設定機能を使用していなかったため、おそらくそれらを正しく表示するためだけでした。）