Pregunta 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?


76
2017-08-25 07:52


origen


Respuestas:


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

Una vez que se compila 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!)


84
2017-08-25 08:55



Algoritmo

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

Código simple

Quizás el código más simple para escribir aprovecha el de Apache StringUtils.replaceEach como sigue:

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

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

Puntos de referencia

Para los puntos de referencia, el buffer fue creado usando randomNumeric como sigue:

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

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

Dónde MATCHES_DIVISOR dicta la cantidad de variables para inyectar:

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

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

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 cuerdas cortas, la sobrecarga de configurar Aho-Corasick eclipsa el enfoque de fuerza bruta 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:


33
2017-11-28 03:08



Si vas a cambiar un String muchas veces, suele ser 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.


7
2017-08-25 08:01



StringBuilder realizará el reemplazo de manera más eficiente, ya que su búfer de matriz de caracteres se puede especificar con la 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.


4
2017-08-25 08:02



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


3
2017-08-25 07:59



Mira esto:

String.format (str, STR [])

...

Por ejemplo:

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


2
2017-12-30 08:16



Rythm, un motor de plantillas java ahora lanzado con una nueva característica llamada Modo de interpolación de cadenas que te 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<String, Object> args = new HashMap<String, Object>();
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 compila 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:


2
2017-07-01 08:42



public String replace(String input, Map<String, String> 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<String, String> sorted = 
      new TreeMap<String, String>(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,
         * i.e. 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();
}

0
2017-08-03 08:35



El siguiente está basado 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<String, String> 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<String, String> 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<String, String> altReplacements = new HashMap<String, String>(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.<String, String>emptyMap()));
  assertEquals("", ExtStringUtils.replaceMultiple("", null));
  assertEquals("", ExtStringUtils.replaceMultiple("", Collections.<String, String>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<String, String> makeMap(String ... vals) {
  Map<String, String> map = new HashMap<String, String>(vals.length / 2);
  for(int i = 1; i < vals.length; i+= 2)
    map.put(vals[i-1], vals[i]);
  return map;
}

0
2017-10-05 15:42