Pertanyaan Java Mengganti beberapa substring yang berbeda dalam satu string sekaligus (atau dengan cara yang paling efisien)


Saya perlu mengganti banyak sub-string dalam string dengan cara yang paling efisien. apakah ada cara lain selain kekuatan kasar menggantikan setiap bidang menggunakan string.replace?


76
2017-08-25 07:52


asal


Jawaban:


Jika string yang Anda operasikan sangat panjang, atau Anda beroperasi pada banyak string, maka itu bisa bermanfaat menggunakan java.util.regex.Matcher (ini membutuhkan waktu di depan untuk mengkompilasi, sehingga tidak akan efisien jika masukan Anda sangat kecil atau pola pencarian Anda sering berubah).

Di bawah ini adalah contoh lengkap, berdasarkan daftar token yang diambil dari peta. (Menggunakan StringUtils dari 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());

Setelah ekspresi reguler dikompilasi, pemindaian string input umumnya sangat cepat (meskipun jika ekspresi reguler Anda kompleks atau melibatkan backtracking maka Anda masih perlu melakukan benchmark untuk mengonfirmasi ini!)


84
2017-08-25 08:55



Algoritma

Salah satu cara paling efisien untuk mengganti string yang cocok (tanpa ekspresi reguler) adalah dengan menggunakan Algoritma Aho-Corasick dengan performan Trie (diucapkan "coba"), cepat hashing algoritma, dan efisien koleksi pelaksanaan.

Kode Sederhana

Mungkin kode paling sederhana untuk menulis memanfaatkan Apache StringUtils.replaceEach sebagai berikut:

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

Ini melambat pada teks-teks besar.

Kode Cepat

Implementasi Bor Algoritma Aho-Corasick memperkenalkan sedikit lebih banyak kerumitan yang menjadi detail implementasi dengan menggunakan façade dengan tanda tangan metode yang sama:

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

Benchmark

Untuk tolok ukur, buffer dibuat menggunakan acakNumerik sebagai berikut:

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

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

Dimana MATCHES_DIVISOR menentukan jumlah variabel yang akan disuntikkan:

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

Kode patokan itu sendiri (JMH tampak berlebihan):

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

1.000.000: 1.000

Sebuah benchmark mikro sederhana dengan 1.000.000 karakter dan 1.000 string yang ditempatkan secara acak untuk menggantikan.

  • testStringUtils: 25 detik, 25533 milis
  • testBorAhoCorasick: 0 detik, 68 milis

Tidak ada kontes.

10.000: 1.000

Menggunakan 10.000 karakter dan 1.000 string yang cocok untuk menggantikan:

  • testStringUtils: 1 detik, 1402 milis
  • testBorAhoCorasick: 0 detik, 37 milis

Pembagian tertutup.

1.000: 10

Menggunakan 1.000 karakter dan 10 string yang cocok untuk menggantikan:

  • testStringUtils: 0 detik, 7 milis
  • testBorAhoCorasick: 0 detik, 19 milis

Untuk string pendek, overhead pengaturan Aho-Corasick gerhana pendekatan brute-force oleh StringUtils.replaceEach.

Pendekatan hibrida berdasarkan panjang teks dimungkinkan, untuk mendapatkan yang terbaik dari kedua implementasi.

Implementasi

Pertimbangkan untuk membandingkan penerapan lain untuk teks yang lebih panjang dari 1 MB, termasuk:

Dokumen

Makalah dan informasi yang berkaitan dengan algoritma:


33
2017-11-28 03:08



Jika Anda akan mengubah String berkali-kali, maka biasanya lebih efisien untuk menggunakan StringBuilder (tetapi ukur kinerja Anda untuk mencari tahu):

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

Setiap kali Anda melakukan penggantian pada String, objek String baru dibuat, karena String tidak dapat diubah. StringBuilder bisa berubah, artinya, dapat diubah sebanyak yang Anda mau.


7
2017-08-25 08:01



StringBuilder akan melakukan penggantian lebih efisien, karena buffer array karakternya dapat ditentukan ke panjang yang diperlukan.StringBuilder dirancang untuk lebih dari menambahkan!

Tentu saja pertanyaan sebenarnya adalah apakah ini merupakan optimasi terlalu jauh? JVM sangat baik dalam menangani pembuatan beberapa objek dan pengumpulan sampah berikutnya, dan seperti semua pertanyaan pengoptimalan, pertanyaan pertama saya adalah apakah Anda telah mengukur ini dan memutuskan bahwa itu adalah masalah.


4
2017-08-25 08:02



Bagaimana kalau menggunakan menggantikan semua() metode?


3
2017-08-25 07:59



Periksa ini:

String.format (str, STR [])

...

Sebagai contoh:

String.format ("Masukkan% s Anda di mana% s Anda adalah", "uang", "mulut");


2
2017-12-30 08:16



Rythm sebuah mesin template java sekarang dirilis dengan fitur baru yang disebut Modus interpolasi string yang memungkinkan Anda melakukan sesuatu seperti:

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

Kasus di atas menunjukkan Anda dapat meneruskan argumen ke templat menurut posisi. Rythm juga memungkinkan Anda untuk menyampaikan argumen berdasarkan nama:

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

Catatan Rythm adalah SANGAT CEPAT, sekitar 2 hingga 3 kali lebih cepat daripada String.format dan kecepatan, karena mengkompilasi template ke dalam kode byte java, kinerja runtime sangat dekat dengan concatentation dengan StringBuilder.

Tautan:


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



Di bawah ini didasarkan pada Jawaban Todd Owen. Solusi itu memiliki masalah bahwa jika penggantian mengandung karakter yang memiliki arti khusus dalam ekspresi reguler, Anda bisa mendapatkan hasil yang tidak diharapkan. Saya juga ingin dapat secara opsional melakukan pencarian case-sensitive. Inilah yang saya temukan:

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

Berikut adalah kasus pengujian unit saya:

@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