Pattern.matches（）はStackOverflowErrorを返します

Question

私はjavaのPattern.matchesを使ってデータブロックを正規表現にマッチさせています。データのブロックは、単一行または複数行にすることができます。問題は、私のデータが15行以上（通常は17-18行以上）になると、私はstackoverflowerrorを取得し始めるということです。 15行未満のデータの場合、正規表現は正常に動作します。

正規表現は、この形式のものである：
ドメイン名 - >空間 - > - >空間 - >数 - >空間 - > - >空間 - >数 - >改行

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 

データ私はこの正規表現に対してテストするために使用するブロックは、この

abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 

ですこれはコードです：

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
boolean valid = Pattern.matches(regex, data); //fails here 

Answer 1

このエラーの原因はわかりません。正規表現自体は問題なく、壊滅的なバックトラックや他の明白なエラーの対象にはなりません。

おそらくあなたは、正規表現エンジンがpossessive quantifiers（++代わりの+、*+代わりの*、{2,}+代わりの{2,}など）を使用して保存し、バックトラック位置の数を減らすことができます。また、あなたは、キャプチャグループ（感謝トーマス）を必要としないので、私は非キャプチャのものにそれらを変更しました：

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++" 

これは正規表現の動作を変更しません（の除去を除い不要なアンカーはPattern.matches()を使用しているため）、おそらくStackOverflowsを回避するのに役立ちます。 Java SDKがインストールされていないので、自分でテストすることはできません。

Answer 2

私はこの問題を再現しましたが、はるかに大きな文字列に対してのみ再現しました。

$ java -version 
java version "1.6.0_22" 
OpenJDK Runtime Environment (IcedTea6 1.10.2) (6b22-1.10.2-0ubuntu1~11.04.1) 
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode) 

私のテストコード：ループのためのもので224よりも小さいものについては

public class Testje 
{ 
    public static void main(String... args) 
    { 
     String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
     String data = ""; 
     for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n"; 
     System.out.println(data.matches(regex)); 
    } 
} 

、コードが細かい実行されます。その行の224以上のコピーに対して、私は巨大なスタックトレースを取得します。

ああ、（使用していることに注意してください：？グループはまだ動作し、文字列のサイズを変更しません

Answer 3

あなたがしようとするとバックトラックを防止するために）（(?>expression)を原子団を使用することがあります：。ここで

はテストですそれはあなたの正規表現を使用して1000行のブロックで失敗しましたが、現在は成功した（ので、私は唯一の 20000 :)でテスト、時間がかかります）：

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+"; 

StringBuilder input = new StringBuilder(); 

for(int i = 0; i < 1000000; ++i) { 
    input.append("abc.com, 123, 456\n"); 
} 

Pattern p = Pattern.compile(regex); 
Matcher m = p.matcher(input); 

System.out.println(m.matches()); 

だから、結局、それはまだバックトラックであるかもしれません問題があります。

更新：このテストを20000行で実行しても失敗しないようにしてください。それはこれまでの20倍以上です。 :)

更新2：私のテストをもう一度見て、私は遅い部分、文字列の連結を発見しました。 （o..O）。私はテストを更新し、まだ失敗していない100万行を使用しました。 :)

Answer 4

問題は正規表現が複雑すぎるということです。あなたが処理する入力の各行は、10のバックトラックポイントをもたらします（少なくとも私は思います）。そして、これらのうちの少なくともいくつかは、正規表現エンジンによって再帰的に処理されるようです。それはあなたにStackOverflowErrorを与えるのに十分な数百のスタックフレームになります。

IMOの場合、1つのグループ/データ行に一致するようにパターンを変更する必要があります。次に、Matcher.findを繰り返し呼び出して各行を解析します。私はあなたがこれがより速いことに気付くでしょう。

---

正規表現を他の方法で最適化しても、ブロック全体を1つに一致させようとすると、おそらく動作しません。 N倍以上のデータ行に一致させることができるかもしれませんが、入力内の行数を増やすと同じ問題に再び遭遇する可能性があります。

また、マルチライン正規表現として動作させる場合でも、Java正規表現ライブラリの他の実装では動作しない可能性があります。例えば古いOracle JREまたはOracle以外の実装では、

---

これは、「大惨事のバックトラッキング」の例ではないことに他の回答で同意します。むしろ正規表現エンジンがバックトラックポイントを扱う方法と、複数行の入力を与えたときにそれらが多すぎるという事実との間の相互作用です。