Ich muss viele verschiedene Teilzeichenfolgen in einer Zeichenfolge auf die effizienteste Weise ersetzen. Gibt es einen anderen Weg als den Brute-Force-Weg, um jedes Feld mit string.replace zu ersetzen?

Wenn die Zeichenfolge, mit der Sie arbeiten, sehr lang ist oder Sie mit vielen Zeichenfolgen arbeiten, kann es sich lohnen, einen java.util.regex.Matcher zu verwenden (dies erfordert im Voraus Zeit zum Kompilieren, daher ist es nicht effizient wenn Ihre Eingabe sehr gering ist oder sich Ihr Suchmuster häufig ändert).

Nachfolgend finden Sie ein vollständiges Beispiel, das auf einer Liste von Token basiert, die einer Karte entnommen wurden. (Verwendet StringUtils von Apache Commons Lang).

Map<String,String> tokens = new HashMap<String,String>();
tokens.put("cat", "Garfield");
tokens.put("beverage", "coffee");

String template = "%cat% really needs some %beverage%.";

// Create pattern of the format "%(cat|beverage)%"
String patternString = "%(" + StringUtils.join(tokens.keySet(), "|") + ")%";
Pattern pattern = Pattern.compile(patternString);
Matcher matcher = pattern.matcher(template);

StringBuffer sb = new StringBuffer();
while(matcher.find()) {
    matcher.appendReplacement(sb, tokens.get(matcher.group(1)));
}
matcher.appendTail(sb);

System.out.println(sb.toString());

Sobald der reguläre Ausdruck kompiliert ist, ist das Scannen der Eingabezeichenfolge im Allgemeinen sehr schnell (wenn Ihr regulärer Ausdruck jedoch komplex ist oder ein Backtracking beinhaltet, müssten Sie immer noch einen Benchmark durchführen, um dies zu bestätigen!)

Algorithmus

Eine der effizientesten Möglichkeiten zum Ersetzen übereinstimmender Zeichenfolgen (ohne reguläre Ausdrücke) ist die Verwendung von Aho-Corasick-Algorithmus mit einem Darsteller Versuch (ausgesprochen “versuchen”), schnell hashen Algorithmus und effizient Sammlungen Implementierung.

Einfacher Code

Eine einfache Lösung nutzt Apache StringUtils.replaceEach folgendermaßen:

  private String testStringUtils(
    final String text, final Map<String, String> definitions ) {
    final String[] keys = keys( definitions );
    final String[] values = values( definitions );

    return StringUtils.replaceEach( text, keys, values );
  }

Dies verlangsamt bei großen Texten.

Schneller Code

Bors Implementierung des Aho-Corasick-Algorithmus führt etwas mehr Komplexität ein, die zu einem Implementierungsdetail wird, indem eine Fassade mit derselben Methodensignatur verwendet wird:

  private String testBorAhoCorasick(
    final String text, final Map<String, String> definitions ) {
    // Create a buffer sufficiently large that re-allocations are minimized.
    final StringBuilder sb = new StringBuilder( text.length() << 1 );

    final TrieBuilder builder = Trie.builder();
    builder.onlyWholeWords();
    builder.removeOverlaps();

    final String[] keys = keys( definitions );

    for( final String key : keys ) {
      builder.addKeyword( key );
    }

    final Trie trie = builder.build();
    final Collection<Emit> emits = trie.parseText( text );

    int prevIndex = 0;

    for( final Emit emit : emits ) {
      final int matchIndex = emit.getStart();

      sb.append( text.substring( prevIndex, matchIndex ) );
      sb.append( definitions.get( emit.getKeyword() ) );
      prevIndex = emit.getEnd() + 1;
    }

    // Add the remainder of the string (contains no more matches).
    sb.append( text.substring( prevIndex ) );

    return sb.toString();
  }

Benchmarks

Für die Benchmarks wurde der Puffer mit erstellt zufälligNumerisch folgendermaßen:

  private final static int TEXT_SIZE = 1000;
  private final static int MATCHES_DIVISOR = 10;

  private final static StringBuilder SOURCE
    = new StringBuilder( randomNumeric( TEXT_SIZE ) );

Wo MATCHES_DIVISOR bestimmt die Anzahl der zu injizierenden Variablen:

  private void injectVariables( final Map<String, String> definitions ) {
    for( int i = (SOURCE.length() / MATCHES_DIVISOR) + 1; i > 0; i-- ) {
      final int r = current().nextInt( 1, SOURCE.length() );
      SOURCE.insert( r, randomKey( definitions ) );
    }
  }

Der Benchmark-Code selbst (JMH schien übertrieben):

long duration = System.nanoTime();
final String result = testBorAhoCorasick( text, definitions );
duration = System.nanoTime() - duration;
System.out.println( elapsed( duration ) );

1.000.000 : 1.000

Ein einfacher Mikro-Benchmark mit 1.000.000 Zeichen und 1.000 zufällig platzierten Zeichenfolgen zum Ersetzen.

• testStringUtils: 25 Sekunden, 25533 Millisekunden
• testBorAhoCorasick: 0 Sekunden, 68 Millisekunden

Kein Wettbewerb.

10.000 : 1.000

Verwenden von 10.000 Zeichen und 1.000 übereinstimmenden Zeichenfolgen zum Ersetzen von:

• testStringUtils: 1 Sekunde, 1402 Millisekunden
• testBorAhoCorasick: 0 Sekunden, 37 Millisekunden

Die Spaltung schließt sich.

1.000 : 10

Verwenden von 1.000 Zeichen und 10 übereinstimmenden Zeichenfolgen zum Ersetzen von:

• testStringUtils: 0 Sekunden, 7 Millisekunden
• testBorAhoCorasick: 0 Sekunden, 19 Millisekunden

Bei kurzen Saiten stellt der Aufwand für die Einrichtung von Aho-Corasick den Brute-Force-Ansatz in den Schatten StringUtils.replaceEach.

Ein hybrider Ansatz basierend auf der Textlänge ist möglich, um das Beste aus beiden Implementierungen herauszuholen.

Implementierungen

Erwägen Sie den Vergleich anderer Implementierungen für Text, der länger als 1 MB ist, einschließlich:

• https://github.com/RokLenarcic/AhoCorasick
• https://github.com/hankcs/AhoCorasickDoubleArrayTrie
• https://github.com/raymanrt/aho-corasick
• https://github.com/ssundaresan/Aho-Corasick
• https://github.com/jmhsieh/aho-corasick
• https://github.com/quest-oss/Mensa

Papiere

Papiere und Informationen zum Algorithmus:

• http://www.cs.uku.fi/research/publications/reports/A-2005-2.pdf
• https://pdfs.semanticscholar.org/3547/ac839d02f6efe3f6f76a8289738a22528442.pdf
• http://www.ece.ncsu.edu/asic/ece792A/2009/ECE792A/Readings_files/00989753.pdf
• http://blog.ivank.net/aho-corasick-algorithm-in-as3.html

Das hat bei mir funktioniert:

String result = input.replaceAll("string1|string2|string3","replacementString");

Beispiel:

String input = "applemangobananaarefruits";
String result = input.replaceAll("mango|are|ts","-");
System.out.println(result);

Ausgabe: Apfel-Bananen-Frucht-

Wenn Sie einen String viele Male ändern, ist es normalerweise effizienter, einen StringBuilder zu verwenden (aber messen Sie Ihre Leistung, um es herauszufinden):

String str = "The rain in Spain falls mainly on the plain";
StringBuilder sb = new StringBuilder(str);
// do your replacing in sb - although you'll find this trickier than simply using String
String newStr = sb.toString();

Jedes Mal, wenn Sie einen String ersetzen, wird ein neues String-Objekt erstellt, da Strings unveränderlich sind. StringBuilder ist änderbar, das heißt, er kann beliebig verändert werden.

StringBuilder führt das Ersetzen effizienter durch, da sein Zeichen-Array-Puffer auf eine erforderliche Länge angegeben werden kann.StringBuilder ist für mehr als nur Anhängen ausgelegt!

Die eigentliche Frage ist natürlich, ob dies eine zu weitreichende Optimierung ist? Die JVM ist sehr gut im Umgang mit der Erstellung mehrerer Objekte und der anschließenden Garbage Collection, und wie bei allen Optimierungsfragen lautet meine erste Frage, ob Sie dies gemessen und festgestellt haben, dass es sich um ein Problem handelt.

Überprüfen Sie dies:

String.format(str,STR[])

Zum Beispiel:

String.format( "Put your %s where your %s is", "money", "mouth" );

Rythm, eine Java-Template-Engine, die jetzt mit einer neuen Funktion namens ” String-Interpolationsmodus was es Ihnen ermöglicht, Folgendes zu tun:

String result = Rythm.render("@name is inviting you", "Diana");

Der obige Fall zeigt, dass Sie Argumente nach Position an die Vorlage übergeben können. Rythm erlaubt Ihnen auch, Argumente nach Namen zu übergeben:

Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);

Hinweis Rythm ist SEHR SCHNELL, etwa 2- bis 3-mal schneller als String.format und die Geschwindigkeit, da es die Vorlage in Java-Bytecode kompiliert, ist die Laufzeitleistung sehr nahe an der Verkettung mit StringBuilder.

Verbindungen:

• Überprüf den voll funktionsfähige Demonstration
• lesen eine kurze Einführung in Rythm
• laden Sie die herunter neustes Paket oder
• Gabel es