替换大字符串中的大量子串

Question

我们模块的一个性能在很大程度上取决于我们如何替换字符串中的子串.

我们形成一个"替换映射",它可以包含超过3500个字符串对,然后我们将它StringUtils.replaceEach(text, searchList, replacementList)应用于大字符串(几个MB).

键和值都是唯一的,在大多数情况下具有相同的字符长度(但它不是我们可以依赖的东西).

对我的任务有更复杂的方法StringUtils.replaceEach()吗？对于简单替换而言可能有点过分的东西可以解决replaceEach(),但在我的"沉重"情况下速度要快得多.

Answer 1

您可以使用正则表达式引擎,有效地将键与输入字符串匹配,并替换它们.

首先,将所有键与一个交替运算符连接起来,如下所示:

var keys = "keyA|keyB|keyC";

接下来,编译一个模式:

Pattern pattern = Pattern.compile("(" + keys + ")")

根据输入文本创建匹配器:

Matcher matcher= pattern.matcher(text);

现在,应用您正则表达式在一个循环中,找到所有的钥匙在你的文字,并使用appendReplacement(这是一个"内联"的字符串替换法),与相应的更换所有这些值:

StringBuffer sb = new StringBuffer();
while (matcher.find()) {
    matcher.appendReplacement(sb,dictionary.get(matcher.group(0)));
}
matcher.appendTail(sb);

你走了

请注意,这可能看起来有点天真,但实际上regexp引擎针对手头的任务进行了大量优化,并且由于Java regexp实现也允许"内联"替换,所以它都能很好地工作.

我做了一个小的基准,通过应用/usr/share/X11/rgb.txt中定义的颜色名称列表(约200种不同的颜色名称)对付Fyodor Dostoyevsky 的"犯罪和惩罚",我从Project Gutenberg下载(大小约1MB),使用所描述的技术,并且它可以解决

比StringUtils.replaceEach快x12倍 - 900ms vs 10700ms

对于后者(不计算模式编译时间).

PS如果你的密钥可能包含字符,对于regexp不安全,比如.^ $(),你应该在将它们添加到模式之前使用Pattern.quote().

边注:

这个方法将按顺序替换键,它们出现在模式列表中,例如"a => 1 | b => 2 | aa => 3"当应用于"welcome to bazaar"时将导致"欢迎来到b1z11r",而不是"欢迎来到b1z3r",如果你想要最长的匹配,你应该按字典顺序对键进行排序,然后再将它们添加到模式中(即"b | aa | a").它也适用于您原始的StringUtils.replaceEach()方法.

更新:

上述方法应该适用于问题,如原始问题中所述,即当替换地图的大小与输入数据大小相比(相对)较小时.

如果你有一个非常长的字典应用于短文本,那么由StringUtils.replaceEach()完成的线性搜索可能比它更快.

我做了一个额外的基准测试,通过应用10000个随机选择的单词(+4个字符长)的字典来说明:

cat /usr/share/dict/words | grep -E "^.{4,}$" | shuf | head -10000

反对:1024,2048,4096,8192,16384,32768,65536,131072,262144和524288字符长的摘录来自同样的"罪与罚"文本.

结果如下:

text    Ta(ms)  Tb(ms)  Ta/Tb(speed up)
---------------------------------------
1024    99      240     0.4125
2048    43      294     0.1462585
4096    113     721     0.1567267
8192    128     1329    0.0963130
16384   320     2230    0.1434977
32768   2052    3708    0.5533981
65536   6811    6650    1.0242106
131072  32422   12663   2.5603728
262144  150655  23011   6.5470862
524288  614634  29874   20.574211

• Ta - StringUtils.replaceEach()时间
• Tb - matcher.appendReplacement()时间

注意模式字符串长度是135537字节(所有10000个键连接)

Answer 2

While appendReplacement solution proposed by @zeppelin was surprisingly fast on "heaviest piece of data" it turned out to be a nightmare with bigger map.

The best solution so far turned out to be a composition of what we had (StringUtils.replaceEach) and what was proposed:

protected BackReplacer createBackReplacer(Map<ReplacementKey, String> replacementMap) {
        if (replacementMap.isEmpty()) {
            return new BackReplacer() {
                @Override
                public String backReplace(String str) {
                    return str;
                }
            };
        }

        if (replacementMap.size() > MAX_SIZE_FOR_REGEX) {
            final String[] searchStrings = new String[replacementMap.size()];
            final String[] replacementStrings = new String[replacementMap.size()];

            int counter = 0;
            for (Map.Entry<ReplacementKey, String> replacementEntry : replacementMap.entrySet()) {
                searchStrings[counter] = replacementEntry.getValue();
                replacementStrings[counter] = replacementEntry.getKey().getValue();
                counter++;
            }

            return new BackReplacer() {
                @Override
                public String backReplace(String str) {
                    return StringUtils.replaceEach(str, searchStrings, replacementStrings);
                }
            };
        }

        final Map<String, String> replacements = new HashMap<>();
        StringBuilder patternBuilder = new StringBuilder();

        patternBuilder.append('(');
        for (Map.Entry<ReplacementKey, String> entry : replacementMap.entrySet()) {
            replacements.put(entry.getValue(), entry.getKey().getValue());
            patternBuilder.append(entry.getValue()).append('|');
        }

        patternBuilder.setLength(patternBuilder.length() - 1);
        patternBuilder.append(')');

        final Pattern pattern = Pattern.compile(patternBuilder.toString());

        return new BackReplacer() {
            @Override
            public String backReplace(String str) {
                if (str.isEmpty()) {
                    return str;
                }

                StringBuffer sb = new StringBuffer(str.length());

                Matcher matcher = pattern.matcher(str);
                while (matcher.find()) {
                    matcher.appendReplacement(sb, replacements.get(matcher.group(0)));
                }
                matcher.appendTail(sb);

                return sb.toString();
            }
        };
    }

StringUtils algorithm (MAX_SIZE_FOR_REGEX=0):

type=TIMER, name=*.run, count=8127, min=4.239809, max=4235197.925261, mean=645.736554, stddev=47197.97968925558, duration_unit=milliseconds

appendReplace algorithm (MAX_SIZE_FOR_REGEX=1000000):

type=TIMER, name=*.run, count=8155, min=4.374516, max=7806145.439165999, mean=1145.757953, stddev=86668.38562815856, duration_unit=milliseconds

Mixed solution (MAX_SIZE_FOR_REGEX=5000):

type=TIMER, name=*.run, count=8155, min=3.5862789999999998, max=376242.25076799997, mean=389.68986564688714, stddev=11733.9997814448, duration_unit=milliseconds

我们的数据：

type=HISTOGRAM, name=initialValueLength, count=569549, min=0, max=6352327, mean=6268.940661478599, stddev=198123.040651236, median=12.0, p75=16.0, p95=32.0, p98=854.0, p99=1014.5600000000013, p999=6168541.008000023
type=HISTOGRAM, name=replacementMap.size, count=8155, min=0, max=65008, mean=73.46108949416342, stddev=2027.471388983965, median=4.0, p75=7.0, p95=27.549999999999955, p98=55.41999999999996, p99=210.10000000000036, p999=63138.68900000023

这一更改将之前解决方案中 StringUtils.replaceEach 花费的时间减少了一半，并为主要受 IO 限制的模块提供了 25% 的性能提升。