8

私は非常に興味深いと思う問題に出くわしました。私は主に正規表現によってテキストファイルの基本的な解析を行っていますが、この行に一致すると常にフリーズします

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01"

例外はスローされません。プログラムがハングするだけです。状況を再現するプログラムのスニペットを投稿しています。コメントされたものは可能な標準的な状況ですが、もう1つは問題があります。\n を削除すると機能しますが、これらの解析済みファイルは「ブラックボックス」システムからこのように取得されます。

私は確かに回避策を講じることができます.実際にフリーズすることだけが興味深いと思い、誰かが何が起こっているのか説明できることを望んでいました. JDK6u22 と JDK7u21 で試してみました...

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\s\\.\\%\\/\\=]*)?\"?\\s*"
);

public static void main(String[] args) {

//  Matcher m = FTRECT_PATTERN.matcher( "FOX_BACKGROUND: ftrect 46.1719 18.0556 54.8633 16.5556 \"Schicht\" " );
    Matcher m = FTRECT_PATTERN.matcher( "ftrect 0.7031 57.0313 9.8561 55.5313 \"FREIGABE \\nQ09_SV01\"" );
    System.out.println( m.matches() );

    for (int i = 0; i <= m.groupCount(); i++) {
        String string = m.group( i );
        System.out.println( string );
    }
}

\\\\さて、正規表現をこれに変更すると（最後のグループに追加すると）、次のことがわかりました。

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\\\\\s\\.\\%\\/\\=]*)?\"?\\s*"
);

例外がスローされない理由はまだわかりません。

4

1 に答える 1

10

これは、壊滅的なバックトラッキングが原因で発生します。テスト文字列には"...\\n..."、文字クラス と一致しないリテラル バックスラッシュ ( 内 ) が含まれてい[\w\s\.\%\/\=]*ます。

これは、正規表現エンジンが、 "FREIGABE不一致を決定する前に、問題のある文字の前にある文字列のすべての可能な順列を試行する必要があることを意味します。

これは非常に高い数値で、おそらく数時間エンジンをビジー状態に保ちます。バックスラッシュを文字クラスに追加すると、正規表現が一致します。

防止: 所有量指定子 (*+および++) を使用して、役に立たないバックトラックを回避します。

public static Pattern FTRECT_PATTERN = Pattern.compile( "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)++)\\s*\"?([\\w\\s\\.\\%\\/\\=]*+)?\"?\\s*" );

より良い、クリーンアップされたソリューションは次のようになります。

public static Pattern FTRECT_PATTERN = Pattern.compile("\\s*(\\w*):?\\s*ftrect\\s+((\\b\\d*(?:\\.\\d+)?\\b\\s?)+)\\s*\"?([\\\\\\w\\s.%/=]*+)?\"?\\s*");
于 2013-05-23T15:52:11.707 に答える