连续的String.replace的替代方案

Question

我想替换String输入中的一些字符串:

string=string.replace("<h1>","<big><big><big><b>");
string=string.replace("</h1>","</b></big></big></big>");
string=string.replace("<h2>","<big><big>");
string=string.replace("</h2>","</big></big>");
string=string.replace("<h3>","<big>");
string=string.replace("</h3>","</big>");
string=string.replace("<h4>","<b>");
string=string.replace("</h4>","</b>");
string=string.replace("<h5>","<small><b>");
string=string.replace("</h5>","</b><small>");
string=string.replace("<h6>","<small>");
string=string.replace("</h6>","</small>");

正如你所看到的那样,这种方法并不是最好的,因为每次我都要搜索要替换的部分等,而且字符串是不可变的......输入也很大,这意味着需要考虑一些性能问题.

有没有更好的方法来降低此代码的复杂性？

Answer 1

虽然StringBuilder.replace()相比之下是一个巨大的进步String.replace(),但它仍然远非最佳.

问题StringBuilder.replace()是,如果替换件的长度与可更换部件的长度不同(适用于我们的情况),则char可能必须分配更大的内部阵列,并且必须复制内容,然后才会发生替换(这也涉及到复印).

想象一下:你有一个10.000个字符的文本.如果要将"XY"位置1(第2个字符)中找到的子字符串替换为"ABC",则实现必须重新分配char至少大1 的缓冲区,必须将旧内容复制到新数组,并且必须复制9.997个字符(从位置开始3)向右移动1以适应"ABC"位置"XY",最后将字符"ABC"复制到起始位置1.每次更换都必须这样做!这很慢.

更快的解决方案:即时构建输出

我们可以即时构建输出:不包含可替换文本的部分可以简单地附加到输出中,如果我们找到可替换的片段,我们会附加替换而不是替换它.从理论上讲,只需将输入循环一次即可生成输出.听起来很简单,实现起来并不难.

执行:

我们将使用Map预加载的可替换替换字符串的映射:

Map<String, String> map = new HashMap<>();
map.put("<h1>", "<big><big><big><b>");
map.put("</h1>", "</b></big></big></big>");
map.put("<h2>", "<big><big>");
map.put("</h2>", "</big></big>");
map.put("<h3>", "<big>");
map.put("</h3>", "</big>");
map.put("<h4>", "<b>");
map.put("</h4>", "</b>");
map.put("<h5>", "<small><b>");
map.put("</h5>", "</b></small>");
map.put("<h6>", "<small>");
map.put("</h6>", "</small>");

使用这个,这里是替换代码:(代码后的更多解释)

public static String replaceTags(String src, Map<String, String> map) {
    StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

    for (int pos = 0;;) {
        int ltIdx = src.indexOf('<', pos);
        if (ltIdx < 0) {
            // No more '<', we're done:
            sb.append(src, pos, src.length());
            return sb.toString();
        }

        sb.append(src, pos, ltIdx); // Copy chars before '<'
        // Check if our hit is replaceable:
        boolean mismatch = true;
        for (Entry<String, String> e : map.entrySet()) {
            String key = e.getKey();
            if (src.regionMatches(ltIdx, key, 0, key.length())) {
                // Match, append the replacement:
                sb.append(e.getValue());
                pos = ltIdx + key.length();
                mismatch = false;
                break;
            }
        }
        if (mismatch) {
            sb.append('<');
            pos = ltIdx + 1;
        }
    }
}

测试它:

String in = "Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End";
System.out.println(in);
System.out.println(replaceTags(in, map));

输出:(包裹以避免滚动条)

Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End

Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

这个解决方案比使用正则表达式更快,因为它涉及很多开销,比如编译a Pattern,创建Matcher等等,而regexp也更通用.它还会在引擎盖下创建许多临时物体,这些物体在更换后会被丢弃.在这里我只使用一个StringBuilder(加上char数组),代码String只在输入上迭代一次.此解决方案使用StringBuilder.replace()此答案顶部详细说明的速度要快得多.

注释和解释

我StringBuilder在replaceTags()方法中初始化了这样的:

StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

所以基本上我创建它的初始容量是原始长度的150%String.这是因为我们的替换比可替换文本更长,因此如果发生替换,输出显然会比输入长.提供更大的初始容量StringBuilder将导致根本没有内部char[]重新分配(当然,所需的初始容量取决于可替换替换对及其在输入中的频率/出现次数,但这+ 50%是一个很好的上限估计).

我还利用了这样一个事实,即所有可替换的字符串都以'<'字符开头,因此找到下一个可替换的位置变得非常快:

int ltIdx = src.indexOf('<', pos);

它只是一个简单的循环和char内部比较String,因为它始终从pos(而不是从输入的开头)开始搜索,整体上代码String只在输入上迭代一次.

最后,为了判断可替换String是否确实发生在潜在位置,我们使用该String.regionMatches()方法检查可更换的蜇,这也是超快速的,因为它只是比较char循环中的值并返回第一个不匹配的字符.

还有一个加号:

问题没有提到它,但我们的输入是一个HTML文档.HTML标记不区分大小写,这意味着输入可能包含<H1>而不是<h1>.
对于这个算法,这不是问题.的regionMatches()在String类具有一个过载支持区分大小写的比较:

boolean regionMatches(boolean ignoreCase, int toffset, String other,
                          int ooffset, int len);

因此,如果我们想要修改我们的算法以查找和替换相同但使用不同字母大小写的输入标签,我们必须修改的是这一行:

if (src.regionMatches(true, ltIdx, key, 0, key.length())) {

使用此修改后的代码,可替换标记变得不区分大小写:

Yo<H1>TITLE</H1><h3>Hi!</h3>Nice day.<H6>Hi back!</H6>End
Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

Answer 2

性能 - 使用StringBuilder.为方便起见,您可以使用它Map来存储值和替换值.

Map<String, String> map = new HashMap<>();
map.put("<h1>","<big><big><big><b>");
map.put("</h1>","</b></big></big></big>");
map.put("<h2>","<big><big>");
...
StringBuilder builder = new StringBuilder(yourString);
for (String key : map.keySet()) {
    replaceAll(builder, key, map.get(key));
}

...要替换StringBuilder中的所有出现,您可以在此处检查: 使用StringBuilder替换所有出现的String？

public static void replaceAll(StringBuilder builder, String from, String to)
{
    int index = builder.indexOf(from);
    while (index != -1)
    {
        builder.replace(index, index + from.length(), to);
        index += to.length(); // Move to the end of the replacement
        index = builder.indexOf(from, index);
    }
}

Answer 3

遗憾的StringBuilder是没有提供replace(string,string)方法,因此您可能需要考虑使用Pattern并Matcher结合使用StringBuffer:

String input = ...;
StringBuffer sb = new StringBuffer();

Pattern p = Pattern.compile("</?(h1|h2|...)>");
Matcher m = p.matcher( input );
while( m.find() )
{
  String match = m.group();
  String replacement = ...; //get replacement for match, e.g. by lookup in a map

  m.appendReplacement( sb, replacement );
}
m.appendTail( sb );

你可以做类似的事情StringBuilder但在这种情况下你必须appendReplacement自己实施等等.

至于表达式,你也可以尝试匹配任何 html标签(虽然这可能会导致问题,因为正则表达式和任意html不太合适)并且当查找没有任何结果时,你只需将匹配替换为自身.

Answer 4

您提供的特定示例似乎是HTML或XHTML.尝试使用正则表达式编辑HTML或XML很容易出问题.对于您似乎感兴趣的编辑类型,您应该考虑使用XSLT.另一种可能性是使用流式XML解析器SAX,并让您的后端即时编写已编辑的输出.如果文本实际上是HTML,您可能更好地使用容忍的HTML解析器(例如JSoup)来构建文档的解析表示(如DOM),并在输出之前对其进行操作.