\ n

Question

を含む行が一致すると、Java Pattern.matcher（）がフリーズする問題が発生しました。私は主に正規表現によるテキストファイルのいくつかの基本的な解析をやっていると、例外がスローされていない

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01" 

この行を照合するときには、必ずフリーズします。プログラムはちょうどハングアップします。状況を再現するプログラムのスニペットを投稿しています。コメントされたものは可能な標準的な状況ですが、もう一つは問題があります。もしあなたが\ nを削除すると、うまく動作しますが、これらの解析されたファイルは "blackbox"システムのようになります。

私は確かに回避策を講じることができますが、実際には凍結し、誰かが何が起こっているのかを説明できることが興味深いことがわかりました。私は（最後のグループに\\\\を追加する）まあ、私はこれに正規表現を変更した場合ことを発見... 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*" 
); 

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

Answer 1

これはcatastrophic backtrackingのために発生します。テスト文字列には、文字クラス[\w\s\.\%\/\=]*と一致しないリテラル・バックスラッシュ（"...\\n..."）が含まれています。

これは、不一致を判定する前に正規表現エンジンが文字列"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*");