Java Ersetzen mehrerer untergeordneter Teilzeichenfolgen in einer Zeichenfolge gleichzeitig (oder auf effizienteste Weise)

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

   

Wenn die Zeichenkette, auf der Sie arbeiten, sehr lang ist oder Sie mit vielen Zeichenketten arbeiten, könnte es sich lohnen, einen java.util.regex.Matcher zu verwenden (das erfordert Zeitaufwand für die Kompilierung, daher ist es nicht effizient Wenn Ihre Eingabe sehr klein ist oder Ihr Suchmuster häufig wechselt.

Im Folgenden finden Sie ein vollständiges Beispiel basierend auf einer Liste von Token, die aus einer Karte entnommen wurden. (Verwendet StringUtils von Apache Commons Lang).

Map tokens = new HashMap(); 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 wurde, ist das Scannen der Eingabe-Zeichenfolge im Allgemeinen sehr schnell (obwohl, wenn Ihr regulärer Ausdruck komplex ist oder ein Backtracking beinhaltet, Sie noch einen Benchmark benötigen würden, um dies zu bestätigen!)

Algorithmus

Eine der effizientesten Methoden zum Ersetzen übereinstimmender Zeichenfolgen (ohne reguläre Ausdrücke) ist die Verwendung des Aho-Corasick-Algorithmus mit einem performanten Trie (sprich “try”), einem schnellen Hashing- Algorithmus und einer effizienten Collections- Implementierung.

Einfacher Code

Der einfachste zu schreibende Code nutzt Apache’s StringUtils.replaceEach wie folgt:

  private String testStringUtils( final String text, final Map definitions ) { final String[] keys = keys( definitions ); final String[] values = values( definitions ); return StringUtils.replaceEach( text, keys, values ); } 

Das verlangsamt sich bei großen Texten.

Schneller Code

Bors Implementierung des Aho-Corasick-Algorithmus bringt etwas mehr Komplexität mit sich, die durch die Verwendung einer Fassade mit der gleichen Methodensignatur zu einem Implementierungsdetail wird:

  private String testBorAhoCorasick( final String text, final Map 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 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 wie folgt mit randomNumeric erstellt:

  private final static int TEXT_SIZE = 1000; private final static int MATCHES_DIVISOR = 10; private final static StringBuilder SOURCE = new StringBuilder( randomNumeric( TEXT_SIZE ) ); 

Wobei MATCHES_DIVISOR die Anzahl der zu injizierenden Variablen angibt:

  private void injectVariables( final Map 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 Strings zum Ersetzen.

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

Kein Wettbewerb.

10.000: 1.000

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

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

Die Kluft schließt sich.

1.000: 10

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

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

Bei kurzen Strings StringUtils.replaceEach der Overhead von Aho-Corasick den Brute-Force-Ansatz von StringUtils.replaceEach .

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

Implementierungen

Erwägen Sie, andere Implementierungen für Text mit mehr als 1 MB zu vergleichen, einschließlich:

Papiere

Papiere und Informationen zum Algorithmus:

Wenn Sie eine Zeichenfolge mehrmals ändern, ist es normalerweise effizienter, einen StringBuilder zu verwenden (aber messen Sie Ihre performance, um dies 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, dh es kann beliebig oft geändert werden.

StringBuilder wird die Ersetzung effizienter durchführen, da der Zeichen-Array-Puffer auf die erforderliche Länge festgelegt werden kann. StringBuilder wurde für mehr als nur zum Anhängen entwickelt!

Die eigentliche Frage ist natürlich, ob das eine Optimierung zu weit ist? Die JVM ist sehr gut im Umgang mit der Erstellung mehrerer Objekte und der nachfolgenden Garbage Collection. Wie bei allen Optimierungsfragen lautet meine erste Frage, ob Sie dies gemessen haben und festgestellt haben, dass dies ein Problem ist.

Wie wäre es mit der replaceAll () Methode?

Überprüfen Sie dies:

Zeichenfolge.format (str, STR [])

Beispielsweise:

String.format (“Setze dein% s dahin, wo dein% s ist”, “Geld”, “Mund”);

Rythm eine Java-Template-Engine, die jetzt mit einer neuen function namens String interpolation mode veröffentlicht wurde.

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

Der obige Fall zeigt, dass Sie das Argument der Vorlage nach Position übergeben können. Mit Rythm können Sie Argumente auch nach Namen übergeben:

 Map args = new HashMap(); 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 Velocity, weil es die Vorlage in Java-Byte-Code kompiliert, die Laufzeitleistung ist sehr nahe an Concatentation mit StringBuilder.

Links:

  • Überprüfen Sie die vollständige Demonstration
  • Lies eine kurze Einführung in Rythm
  • Laden Sie das neueste Paket herunter oder
  • Gabel es
 public String replace(String input, Map pairs) { // Reverse lexic-order of keys is good enough for most cases, // as it puts longer words before their prefixes ("tool" before "too"). // However, there are corner cases, which this algorithm doesn't handle // no matter what order of keys you choose, eg. it fails to match "edit" // before "bed" in "..bedit.." because "bed" appears first in the input, // but "edit" may be the desired longer match. Depends which you prefer. final Map sorted = new TreeMap(Collections.reverseOrder()); sorted.putAll(pairs); final String[] keys = sorted.keySet().toArray(new String[sorted.size()]); final String[] vals = sorted.values().toArray(new String[sorted.size()]); final int lo = 0, hi = input.length(); final StringBuilder result = new StringBuilder(); int s = lo; for (int i = s; i < hi; i++) { for (int p = 0; p < keys.length; p++) { if (input.regionMatches(i, keys[p], 0, keys[p].length())) { /* TODO: check for "edit", if this is "bed" in "..bedit.." case, * ie look ahead for all prioritized/longer keys starting within * the current match region; iff found, then ignore match ("bed") * and continue search (find "edit" later), else handle match. */ // if (better-match-overlaps-right-ahead) // continue; result.append(input, s, i).append(vals[p]); i += keys[p].length(); s = i--; } } } if (s == lo) // no matches? no changes! return input; return result.append(input, s, hi).toString(); } 

Das Folgende basiert auf Todd Owens Antwort . Diese Lösung hat das Problem, dass wenn die Ersetzungen Zeichen enthalten, die in regulären Ausdrücken eine besondere Bedeutung haben, Sie unerwartete Ergebnisse erhalten können. Ich wollte auch in der Lage sein, optional eine Suche ohne Berücksichtigung der Groß- / Kleinschreibung durchzuführen. Hier ist, was ich mir ausgedacht habe:

 /** * Performs simultaneous search/replace of multiple strings. Case Sensitive! */ public String replaceMultiple(String target, Map replacements) { return replaceMultiple(target, replacements, true); } /** * Performs simultaneous search/replace of multiple strings. * * @param target string to perform replacements on. * @param replacements map where key represents value to search for, and value represents replacem * @param caseSensitive whether or not the search is case-sensitive. * @return replaced string */ public String replaceMultiple(String target, Map replacements, boolean caseSensitive) { if(target == null || "".equals(target) || replacements == null || replacements.size() == 0) return target; //if we are doing case-insensitive replacements, we need to make the map case-insensitive--make a new map with all-lower-case keys if(!caseSensitive) { Map altReplacements = new HashMap(replacements.size()); for(String key : replacements.keySet()) altReplacements.put(key.toLowerCase(), replacements.get(key)); replacements = altReplacements; } StringBuilder patternString = new StringBuilder(); if(!caseSensitive) patternString.append("(?i)"); patternString.append('('); boolean first = true; for(String key : replacements.keySet()) { if(first) first = false; else patternString.append('|'); patternString.append(Pattern.quote(key)); } patternString.append(')'); Pattern pattern = Pattern.compile(patternString.toString()); Matcher matcher = pattern.matcher(target); StringBuffer res = new StringBuffer(); while(matcher.find()) { String match = matcher.group(1); if(!caseSensitive) match = match.toLowerCase(); matcher.appendReplacement(res, replacements.get(match)); } matcher.appendTail(res); return res.toString(); } 

Hier sind meine Unit-Testfälle:

 @Test public void replaceMultipleTest() { assertNull(ExtStringUtils.replaceMultiple(null, null)); assertNull(ExtStringUtils.replaceMultiple(null, Collections.emptyMap())); assertEquals("", ExtStringUtils.replaceMultiple("", null)); assertEquals("", ExtStringUtils.replaceMultiple("", Collections.emptyMap())); assertEquals("folks, we are not sane anymore. with me, i promise you, we will burn in flames", ExtStringUtils.replaceMultiple("folks, we are not winning anymore. with me, i promise you, we will win big league", makeMap("win big league", "burn in flames", "winning", "sane"))); assertEquals("bcaacbbcaacb", ExtStringUtils.replaceMultiple("abccbaabccba", makeMap("a", "b", "b", "c", "c", "a"))); assertEquals("bcaCBAbcCCBb", ExtStringUtils.replaceMultiple("abcCBAabCCBa", makeMap("a", "b", "b", "c", "c", "a"))); assertEquals("bcaacbbcaacb", ExtStringUtils.replaceMultiple("abcCBAabCCBa", makeMap("a", "b", "b", "c", "c", "a"), false)); assertEquals("c colon backslash temp backslash star dot star ", ExtStringUtils.replaceMultiple("c:\\temp\\*.*", makeMap(".", " dot ", ":", " colon ", "\\", " backslash ", "*", " star "), false)); } private Map makeMap(String ... vals) { Map map = new HashMap(vals.length / 2); for(int i = 1; i < vals.length; i+= 2) map.put(vals[i-1], vals[i]); return map; } 

Das hat für mich funktioniert:

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

Beispiel:

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

Ausgabe: Apfel-Bananen-Fruch