Regex Pattern Match-Leistung in Java für lange Zeichenfolge

Question

Ich habe eine Regex, die gut funktioniert (500 Nanosekunden), wenn eine Übereinstimmung gefunden wird, aber viel Zeit (über 3 Sekunden) dauert, wenn es keine Übereinstimmung gibt. Ich vermute, das könnte wegen Backtracking sein. Ich habe einige Optionen ausprobiert, wie die Umwandlung von .* in (.*)? basierend auf einer Dokumentation, aber es hat nicht geholfen.

Eingabe: eine sehr lange Zeichenfolge - 5k Zeichen in einigen Fällen.

Regex zum Spiel: .*substring1.*substring2.*

Ich bin das Muster vorge Kompilieren und Wiederverwendung der Matcher, was kann ich sonst noch versuchen?

Hier ist mein Code-Snippet - ich werde diese Methode mit Millionen von verschiedenen Eingabezeichenfolgen aufrufen, aber nur eine Handvoll Regex-Muster.

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

Hier ist meine Methode:

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

Ihre Regex unterliegt einem Problem, das als katastrophale Rückverfolgung bekannt ist, wie Sie angedeutet haben. Im Wesentlichen wird die erste .* die gesamte Zeichenfolge übereinstimmen und dann zurückverfolgen, bis substring1 übereinstimmt. Dies wird mit substring2 wiederholt. Da substring2 fehlschlägt, muss der zweite .* einen anderen Ort finden, an dem substring2 beginnt, zu übereinstimmen, und dann wird es erneut fehlschlagen. Jedes Mal, wenn substring1 übereinstimmt, müssen wir jeden einzelnen Ort überprüfen, der mit substring2 übereinstimmt.

Sie verwenden bereits pattern.find(), so dass Sie den Anfang und das Ende .* weglassen können. Dann könnte das Ändern der inneren .* zu einer .*? die Leistung verbessern, indem Sie den gierigen Matcher in einen faulen verwandeln.

Dies erzeugt: substring1.*?substring2

Answer 2

Mit String.indexOf() ist viel schneller als Regex, wenn der Fall ist einfach genug, können Sie es verwenden.

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; 
} 

Beachten Sie, dass meine Lösung nicht mit dem Fall befasst, wo string2 in string1 enthalten ist, wenn das der Fall ist, müssen Sie das mit der Logik hinzuzufügen: Sie könnten Ihr Problem als neu codieren.

Answer 3

können Sie überprüfen, ob das Muster, wenn Sie indexOf() verwenden entsprechen:

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

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

---

Wenn die Regex nicht übereinstimmt, werden Sie katastrophal Rückzieher bekommen. In der Tat macht Ihr Muster wahrscheinlich viel Rückverfolgung, selbst wenn es eine Übereinstimmung gibt. Die .* wird die gesamte Zeichenfolge auffressen und muss dann rückwärts gehen, widerwillig Zeichen zurückgeben.

Wenn Ihre Zeichenfolge wie folgt aussieht: substring1 substring2........50000 more characters......, dann erhalten Sie eine bessere Leistung mit der faulen .*?. Bitte beachten Sie, dass (.*)? NICHT dasselbe ist wie .*?.

Die Leistung des Regex hängt davon ab, was die Teilstrings sind und was mit ihnen verglichen wird. Wenn Ihre Zeichenfolge wie folgt aussieht: substring1........50000 more characters...... substring2, dann erhalten Sie eine bessere Leistung mit der .*, die Sie haben.

Answer 4

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

Sollte es tun, weil eine Zeichenfolge, die eine Teilkette mehrmals enthält, aber nicht beide, um nicht ad nauseam Rückzieher. Sie können die. *? \ Z am Ende ablegen, wenn Sie nicht möchten, dass der Matcher am Ende der Eingabe endet.