Effiziente und nicht-interferierende Methode zum Ersetzen mehrerer Teilstrings in einem String

Question

Ich versuche, die gleichen Austauschanweisungen mehrere tausend Mal auf verschiedene Eingabezeichenfolgen mit so wenig Overhead wie möglich anzuwenden. Ich brauche zwei Dinge dafür zu berücksichtigen:

1. Die Suche Strings sind nicht unbedingt alle gleich lang: man kann nur „a“ sein, ein anderer könnte „ch“ sein, noch eine andere sein könnte „sch“
2. Was bereits ersetzt wurde, darf nicht wieder ersetzt werden: Wenn die Ersatzmuster [a-> e; e-> a], "beat" sollte "baet" werden, nicht "baat" oder "beet".

Mit dem im Verstand, das ist der Code, den ich mit aufkommen:

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

Und dann

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 und r_input bis zu dem Benutzer sein würde, so dass sie‘ nur Beispiele, genau wie das Programm nicht wirklich println())

Dies verwenden würde Code stellt sicher, dass längere Suchstrings zuerst gesucht werden und deckt auch die zweite Bedingung ab.

Es ist jedoch ziemlich teuer. Was wäre der effizienteste Weg, um das zu erreichen, was ich hier mache (besonders wenn die Anzahl der Strings in words sehr groß ist)?

Mit meinem aktuellen Code „Couch“ sollte in „kuc“ umgewandelt werden (außer es nicht, offenbar, es tut jetzt, dank der -1 in split(p,-1))

Answer 1

Dies ist keine vollständige Lösung aber es zeigt, wie man die Eingabe scannt und alle Ziel-Teilstrings in einem Durchgang findet. Sie würden eine StringBuilder verwenden, um das Ergebnis zusammenzustellen und die Ersetzungen in einer Map nachzusehen, wie Sie es gerade tun. Verwenden Sie die Start- und Endindizes, um das Kopieren nicht übereinstimmender Segmente zu verarbeiten.

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

Ausgang:

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' 

Beachten Sie die Zeichenfolgen in der Regex haben, um zu sortierende Länge absteigend richtig zu arbeiten.

Answer 2

Man könnte ein Regex-Muster aus den Tasten machen und es diesem Modul zur Optimierung überlassen.

Offensichtlich

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

Bedürfnisse ce/ci/c kümmern, entweder durch Reverse-Sortierung oder sofort als Baum:

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

Dann

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

Der Vorteil ist, Diese Regex ist ziemlich intelligent (wenn auch langsam), und es werden keine Ersetzungen über ersetzten Text vorgenommen.

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