Java 一次替换字符串中的多个不同子字符串（或以最有效的方式）算法简单代码快速编码基准实现文件

string replace java

2022-08-31 09:24:38

我需要以最有效的方式替换字符串中的许多不同的子字符串。有没有另一种方法，然后使用string.replace替换每个字段的蛮力方式？

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

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

答案 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 算法的实现引入了更多的复杂性，通过使用具有相同方法签名的外观，这些复杂性成为实现细节：

  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 seconds， 25533 millis
测试硼橡胶：0 秒，68 毫

没有比赛。

10,000 : 1,000

使用 10，000 个字符和 1，000 个匹配字符串来替换：

testStringUtils： 1 seconds， 1402 millis
testBorAhoCorasick： 0 秒， 37 毫

鸿沟结束。

1,000 : 10

使用 1，000 个字符和 10 个匹配字符串替换：

testStringUtils： 0 秒， 7 毫
testBorAhoCorasick： 0 秒， 19 毫

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

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

实现

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

文件

与算法相关的论文和信息：