長い文字列のJavaでの正規表現パターンの一致処理

Question

一致が見つかると素晴らしい（500ナノ秒）正規表現がありますが、一致しない場合は（3秒以上）多くの時間がかかります。私はこれがバックトラッキングのためであると思われる。いくつかのオプションを試しましたが、を(.*)?に変換するのと同じようにいくつかのドキュメントに基づいていますが、それは役に立ちませんでした。

入力：非常に長い文字列 - 場合によっては5k文字。

正規表現が一致します.*substring1.*substring2.*

私は、私は他に何を試すことができ、パターンを事前にコンパイルして再使用して、整合していますか？

ここに私のコードスニペットがあります。私はこのメソッドを何百万もの異なる入力文字列で呼びますが、ほんの一握りの正規表現パターンを使用します。ケースは、あなたがそれを使用することができます十分に単純である場合

public static Boolean regex_match(String line, String regex) { 
    if (regex == null || line == null) { 
     return null; 
    } 
    if (!patternMap.containsKey(regex)) { 
     patternMap.put(regex, Pattern.compile(regex)); 
     matcherMap.put(regex,patternMap.get(regex).matcher("")); 
    } 
    return matcherMap.get(regex).reset(line).find(0); 
} 

Answer 1

あなたの正規表現は、あなたが暗示したように、壊滅的なバックトラッキングと呼ばれる問題の影響を受けます。基本的に、最初の.*は文字列全体と一致し、substring1が一致するまでバックトラックします。これはsubstring2で繰り返されます。 substring2が失敗するため、2番目の.*は、substring2が一致し始める別の場所を見つける必要があります。その後、再び失敗します。 substring1が一致するたびに、substring2が一致する可能性のあるすべての場所を確認する必要があります。

すでにpattern.find()を使用しているため、開始と終了の省略は.*です。その後、.*を.*?に変更すると、欲張りマッチャーを怠け者にすることでパフォーマンスが向上する可能性があります。

これが生成します。順番に両方の1のサブストリングを複数回含まれているではなく、文字列はうんざりを後戻りしないのでsubstring1.*?substring2

Answer 2

使用String.indexOf()が正規表現よりもはるかに高速です：

private static HashMap<String, Pattern> patternMap = new HashMap<String, Pattern>(); 
private static HashMap<String, Matcher> matcherMap = new HashMap<String, Matcher>(); 

は、ここに私の方法です。それはあなたがロジックにそれを追加する必要があります場合であれば、私の解決策は、string2がstring1に含まれている場合に対処していないこと

public static boolean containsStrings(String source, String string1, String string2) { 
    long pos1, pos2; 
    pos1 = source.indexOf(string1); 
    if(pos1 > -1) { 
    pos2 = source.indexOf(string2,pos1 + string1.length); 
    if(pos2 > pos1 && source.indexOf(string1,pos2 + string2.length) < -1) { 
     return true; 
    } 
    } 
    return false; 
} 

注：あなたは、あなたのような問題を再コーディングができます。

Answer 3

あなたがindexOf()を使用する場合、パターンが一致することを確認することができます

int pos1 = str.indexOf("substring1"); 
int pos2 = str.indexOf("substring2", pos1); 

if(pos1 != -1 && pos2 != -1){ 
    // regex 
} 

---

を正規表現が一致しない場合、あなたは壊滅的なバックトラックを取得します。実際には、あなたのパターンは、マッチがあっても多くのバックトラックを行う可能性が高いです。 .*は文字列全体を食べてしまい、逆に戻ってくる必要があります。

文字列がsubstring1 substring2........50000 more characters......の場合は、遅延文字数が.*?になります。 (.*)?は.*?と同じではありません。

正規表現のパフォーマンスは、部分文字列の内容と一致するものによって異なります。文字列がsubstring1........50000 more characters...... substring2の場合は、.*の方がパフォーマンスが向上します。

Answer 4

^((?!substring1).)*substring1((?!substring2).)*substring2.*?\Z

はそれを行う必要があります。 Matcherが入力の最後に終了する必要がない場合は、最後に*？\ Zをドロップすることができます。