Java一次(或以最有效的方式)替换字符串中的多个不同子字符串

Question

我需要以最有效的方式替换字符串中的许多不同的子字符串.除了使用string.replace替换每个字段的蛮力方式之外还有另一种方法吗？

Answer 1

如果您正在操作的字符串很长,或者您在许多字符串上操作,那么使用java.util.regex.Matcher(这需要时间预先编译,因此它不会有效)是值得的.如果您的输入非常小或您的搜索模式经常更改).

下面是一个完整的示例,基于从地图中获取的令牌列表.(使用来自Apache Commons Lang的StringUtils).

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

编译正则表达式后,扫描输入字符串通常非常快(虽然如果你的正则表达式很复杂或涉及回溯,那么你仍然需要进行基准测试以确认这一点!)

Answer 2

算法

替换匹配字符串(没有正则表达式)的最有效方法之一是使用Aho-Corasick算法和高性能Trie(发音为"try"),快速散列算法和高效集合实现.

简单代码

一个简单的解决方案利用Apache StringUtils.replaceEach如下:

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

这会减慢大文本的速度.

快速代码

Bor的 Aho-Corasick算法的实现引入了更多的复杂性,通过使用具有相同方法签名的façade成为实现细节:

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

基准

对于基准测试,缓冲区是使用randomNumeric创建的,如下所示:

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

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

在哪里MATCHES_DIVISOR指示要注入的变量数量:

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

基准代码本身(JMH似乎有点过分):

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

1,000,000:1,000

一个简单的微基准测试,包含1,000,000个字符和1,000个随机放置的字符串.

• testStringUtils: 25秒,25533毫秒
• testBorAhoCorasick: 0秒,68毫安

没有比赛.

10,000:1,000

使用10,000个字符和1,000个匹配的字符串替换:

• testStringUtils: 1秒,1402毫秒
• testBorAhoCorasick: 0秒,37毫秒

分歧关闭.

1,000:10

使用1,000个字符和10个匹配的字符串替换:

• testStringUtils: 0秒,7毫秒
• testBorAhoCorasick: 0秒,19毫秒

对于短字符串,设置Aho-Corasick的开销会使蛮力方法黯然失色StringUtils.replaceEach.

基于文本长度的混合方法是可能的,以获得两种实现的最佳效果.

实现

考虑比较长度超过1 MB的文本的其他实现,包括:

• 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

文件

与算法有关的论文和信息:

• 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

Answer 3

如果您要多次更改String,那么使用StringBuilder通常会更有效(但要测量您的性能以找出):

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

每次对String执行替换时,都会创建一个新的String对象,因为字符串是不可变的.StringBuilder是可变的,也就是说,它可以根据需要进行更改.

Answer 4

这为我工作：

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

例：

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

输出： apple-banana-friui-