Java Reemplazar múltiples subcadenas diferentes en una cadena a la vez (o de la manera más eficiente)

Necesito reemplazar muchas subcadenas diferentes en una cadena de la manera más eficiente. ¿Hay alguna otra manera que no sea la fuerza bruta de reemplazar cada campo con string.replace?

Si la cadena en la que está operando es muy larga, o si está operando en muchas cadenas, entonces valdría la pena utilizar un java.util.regex.Matcher (esto requiere un tiempo inicial para comstackr, por lo que no será eficiente si su entrada es muy pequeña o su patrón de búsqueda cambia con frecuencia).

A continuación se muestra un ejemplo completo, basado en una lista de tokens tomados de un mapa. (Utiliza StringUtils de 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()); 

Una vez que se comstack la expresión regular, el escaneo de la cadena de entrada es generalmente muy rápido (aunque si su expresión regular es compleja o implica un retroceso, ¡aún tendría que realizar un benchmark para confirmar esto!)

Algoritmo

Una de las maneras más eficientes de reemplazar cadenas coincidentes (sin expresiones regulares) es usar el algoritmo Aho-Corasick con un Trie (“bash” pronunciado), algoritmo rápido de hash y una implementación eficiente de colecciones .

Código simple

Quizás el código más simple para escribir aprovecha Apache’s StringUtils.replaceEach siguiente manera:

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

Esto se ralentiza en textos grandes.

Código rápido

La implementación de Bor del algoritmo Aho-Corasick introduce un poco más de complejidad que se convierte en un detalle de implementación mediante el uso de una fachada con la misma firma de método:

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

Puntos de referencia

Para los puntos de referencia, el buffer fue creado usando randomNumeric de la siguiente manera:

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

Donde MATCHES_DIVISOR dicta la cantidad de variables para inyectar:

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

El código de referencia en sí mismo ( JMH parecía excesivo):

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

1,000,000: 1,000

Un micro-punto de referencia simple con 1,000,000 de caracteres y 1,000 cadenas colocadas al azar para reemplazar.

  • TestStringUtils: 25 segundos, 25533 millis
  • testBorAhoCorasick: 0 segundos, 68 millis

No contestar.

10,000: 1,000

Usando 10,000 caracteres y 1,000 cadenas coincidentes para reemplazar:

  • TestStringUtils: 1 segundo, 1402 millis
  • testBorAhoCorasick: 0 segundos, 37 millis

La división se cierra.

1,000: 10

Usando 1,000 caracteres y 10 cadenas correspondientes para reemplazar:

  • TestStringUtils: 0 segundos, 7 millis
  • testBorAhoCorasick: 0 segundos, 19 millis

Para cadenas cortas, la sobrecarga de la configuración de Aho-Corasick eclipsa el enfoque de fuerza bruta de StringUtils.replaceEach .

Es posible un enfoque híbrido basado en la longitud del texto para obtener lo mejor de ambas implementaciones.

Implementaciones

Considere la posibilidad de comparar otras implementaciones para textos de más de 1 MB, que incluyen:

Papeles

Papeles e información relacionada con el algoritmo:

Si va a cambiar un String muchas veces, generalmente es más eficiente usar un StringBuilder (pero mida su rendimiento para averiguarlo) :

 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(); 

Cada vez que realiza un reemplazo en una Cadena, se crea un nuevo objeto Cadena, porque las Cadenas son inmutables. StringBuilder es mutable, es decir, se puede cambiar tanto como lo desee.

StringBuilder realizará el reemplazo de manera más eficiente, ya que su búfer de matriz de caracteres se puede especificar a una longitud requerida. StringBuilder está diseñado para más que agregar!

Por supuesto, la verdadera pregunta es si esto es una optimización demasiado lejos. La JVM es muy buena para manejar la creación de múltiples objetos y la posterior recolección de basura, y como todas las preguntas de optimización, mi primera pregunta es si ha medido esto y ha determinado que es un problema.

¿Qué hay de usar el método replaceAll () ?

Mira esto:

String.format (str, STR [])

Por ejemplo:

String.format (“Pon tu% s donde tu% s es”, “dinero”, “boca”);

Rythm es un motor de plantillas java ahora lanzado con una nueva característica llamada modo de interpolación de cadenas que le permite hacer algo como:

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

El caso anterior muestra que puede pasar el argumento a la plantilla por posición. Rythm también le permite pasar argumentos por su nombre:

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

Nota Rythm es MUY RÁPIDO, de 2 a 3 veces más rápido que String.format y velocity, porque comstack la plantilla en código de byte java, el rendimiento en tiempo de ejecución está muy cerca de la concatenación con StringBuilder.

Campo de golf:

  • Verifique la demostración completa
  • lea una breve introducción a Rythm
  • descargar el último paquete o
  • tenedor
 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(); } 

El siguiente se basa en la respuesta de Todd Owen . Esa solución tiene el problema de que si los reemplazos contienen caracteres que tienen un significado especial en las expresiones regulares, puede obtener resultados inesperados. También quería poder realizar opcionalmente una búsqueda insensible a mayúsculas y minúsculas. Aquí es lo que se me ocurrió:

 /** * 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(); } 

Aquí están mis casos de prueba de unidad:

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

Esto funcionó para mí:

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

Ejemplo:

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

Salida: apple-banana-friui-