java - 替换字符串中多个子字符串的高效且无干扰的方法

Question

我试图以尽可能小的开销将相同的替换指令应用于不同的输入字符串数千次。为此我需要考虑两件事:

1. 搜索字符串的长度不一定相同:一个可能是“a”，另一个可能是“ch”，还有一个可能是“sch”
2. 已经被替换的内容不再被替换:如果替换模式是[a->e; e->a]，“beat”应该变成“baet”，而不是“baat”或“beet”。

考虑到这一点，这是我想出的代码:

public class Replacements {
    private String[] search;
    private String[] replace;
    Replacements(String[] s, String[] r)
    {
        if (s.length!=r.length) throw new IllegalArgumentException();
        Map<String,String> map = new HashMap<String,String>();
        for (int i=0;i<s.length;i++)
        {
            map.put(s[i], r[i]);
        }
        List<String> sortedKeys = new ArrayList(map.keySet());
        Collections.sort(sortedKeys, new StringLengthComparator());
        this.search = sortedKeys.toArray(new String[0]);
        Stack<String> r2 = new Stack<>();
        sortedKeys.stream().forEach((i) -> {
            r2.push(map.get(i));
        });
        this.replace = r2.toArray(new String[0]);
    }
    public String replace(String input)
    {
        return replace(input,0);
    }
    private String replace(String input,int i)
    {
        String out = "";
        List<String> parts = Arrays.asList(input.split(this.search[i],-1));
        for (Iterator it = parts.iterator(); it.hasNext();)
        {
            String part = it.next().toString();
            if (part.length()>0 && i<this.search.length-1) out += replace(part,i+1);
            if (it.hasNext()) out += this.replace[i];
        }
        return out;
    }
}

然后

String[] words;
//fill variable words
String[] s_input = "ou|u|c|ch|ce|ci".split("\\|",-1);
String[] r_input = "u|a|k|c|se|si".split("\\|",-1);
Replacements reps = new Replacements(s_input,r_input);
for (String word : words) {
    System.out.println(reps.replace(word));
}

(s_input 和 r_input 将由用户决定，因此它们只是示例，就像程序实际上不会使用 println() )

此代码确保首先查找较长的搜索字符串，并且还涵盖上面的第二个条件。

然而，它的成本相当高。完成我在这里所做的事情的最有效方法是什么(特别是如果 words 中的字符串数量非常大)？

使用我当前的代码，“couch”应该转换为“kuc”(显然，它没有转换为“kuc”；由于 split(p,-1) 中的 -1，现在可以转换为“kuc”))

Answer 1

这不是一个完整的解决方案，但它展示了如何扫描输入并一次性找到所有目标子字符串。您将使用 StringBuilder 来组合结果，像您当前所做的那样在 Map 中查找替换项。使用开始和结束索引来处理不匹配段的复制。

public static void main(String[] args) throws Exception
{
    Pattern p = Pattern.compile("(ou|ch|ce|ci|u|c)");
    Matcher m = p.matcher("auouuchcceaecxici");
    while (m.find())
    {
        MatchResult r = m.toMatchResult();
        System.out.printf("s=%d e=%d '%s'\n", r.start(), r.end(), r.group());
    }
}

输出:

s=1 e=2 'u'
s=2 e=4 'ou'
s=4 e=5 'u'
s=5 e=7 'ch'
s=7 e=8 'c'
s=8 e=10 'ce'
s=12 e=13 'c'
s=15 e=17 'ci'

请注意，正则表达式中的字符串必须按长度降序排序才能正常工作。