文字列内の複数の部分文字列を効率的に置き換える方法

Question

できるだけオーバーヘッドの少ないさまざまな入力文字列に同じ置換命令を数千回適用しようとしています。

1. 検索文字列は、必ずしもすべて同じ長さではありません：私はこのために2つのものを検討する必要がある1つだけの「A」、もう一つは「CH」であるかもしれない、また別には、「SCH」であるかもしれないかもしれを
2. すでに置き換えられたものは、もう一度置き換えられません。置換パターンが[a-> e; e-> a]の場合、 "beat"は "baet"または "beet"ではなく "baet"になります。念頭に置いて

、これは私が思い付いたコードです：ユーザー次第だろう

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は、ので、彼らは」プログラムが実際に使用しないのと同じように、例だけを返します。

これはコードは長い検索文字列が最初に検索され、上記の2番目の条件もカバーするようにします。

ただし、非常に高価です。私がここでやっていることを達成する最も効率的な方法は何でしょうか（特にwordsの文字列の数がかなり多い場合）？ （そうでない以外どうやら、;それは今、-1 split(p,-1)で感謝しています）私の現在のコードで

は、「ソファ」「KUC」に変換されなければならない

Answer 1

これは、完全なソリューションではありません入力をスキャンしてすべてのターゲット部分文字列を1回のパスで見つける方法を示しています。結果を組み立てるために、StringBuilderを使用し、現在行っているようにマップ内の置換を参照します。一致しないセグメントのコピーを処理するには、開始インデックスと終了インデックスを使用します。

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(); 
    } 
}