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

Question

我试图用尽可能少的开销将相同的替换指令几千次应用于不同的输入字符串。我需要考虑两两件事是：

1. 搜索字符串不一定都是相同的长度：一个可能只是“一”，另一种可能是“CH”，另一种可能是“SCH”
2. 已经替换的内容不应再次替换：如果替换模式为[a-> e; e-> a]，“beat”应该变成“baet”，而不是“baat”或“甜菜”。

考虑到这一点，这是我想出了代码：

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

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

然而，它是相当昂贵的。什么是最有效的方式来完成我在这里做的事情（特别是如果words中的字符串数量非常大）？

随着我当前的代码，“沙发”应该被转换为“KUC”（除了没有，显然，它现在，多亏了-1 split(p,-1)）

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' 

注意，在正则表达式中的字符串在下降长度正常工作的顺序进行排序。

Answer 2

人们可以从按键创建一个正则表达式模式，并将其留给该模块进行优化。

显然

"(ou|u|ch|ce|ci|c)" 

需要照顾CE/CI/C的，或者通过反向排序或立即作为树：

"(c(e|h|i)?|ou|u)" 

然后

String soughtKeys = "ou|u|ch|ce|ci|c"; // c last 
String replacements = "u|a|c|se|si|k"; 
Map<String, String> map = new HashMap<>(); 
... fill map 

Pattern pattern = Pattern.compile("(" + soughtKeys + ")"); 

for (String word : words) { 
    StringBuffer sb = new StringBuffer(); 
    Matcher m = pattern.matcher(word); 
    while (m.find()) { 
     m.appendReplacement(sb, map.get(m.group()); 
    } 
    m.appendTail(sb); 
    System.out.printf("%s -> %s%n", word, sb.toString()); 
} 

的优点是该正则表达式非常聪明（尽管很慢），并且替换不会替代文本。

Answer 3

public class Replacements 
{ 
    private String[] search; // sorted in descending length and order, eg: sch, ch, c 
    private String[] replace; // corresponding replacement 

    Replacements(String[] s, String[] r) 
    { 
     if (s.length != r.length) 
      throw new IllegalArgumentException(); 

     final TreeMap<String, String> map = new TreeMap<String, String>(Collections.reverseOrder()); 

     for (int i = 0; i < s.length; i++) 
      map.put(s[i], r[i]); 

     this.search = map.keySet().toArray(new String[map.size()]); 
     this.replace = map.values().toArray(new String[map.size()]); 
    } 

    public String replace(String input) 
    { 
     final StringBuilder result = new StringBuilder(); 

     // start of yet-to-be-copied substring 
     int s = 0; 

     SEARCH: 
     for (int i = s; i < input.length(); i++) 
     { 
      for (int p = 0; p < this.search.length; p++) 
      { 
       if (input.regionMatches(i, this.search[p], 0, this.search[p].length())) 
       { 
        // append buffer and replacement 
        result.append(input, s, i).append(this.replace[p]); 

        // skip beyond current match and reset buffer 
        i += this.search[p].length(); 
        s = i--; 

        continue SEARCH; 
       } 
      } 
     } 

     if (s == 0) // no matches? no changes! 
      return input; 

     // append remaining buffer 
     return result.append(input, s, input.length()).toString(); 
    } 
}