Eine bessere Möglichkeit, viele Zeichenfolgen zu ersetzen - Verschleierung in C#

Question

Ich versuche, eine große Menge von Daten zu verschleiern. Ich habe eine Liste von Wörtern (Token) erstellt, die ich ersetzen wollen und ich bin die Worte eins nach dem anderen mit der Stringbuilder-Klasse zu ersetzen, etwa so:

var sb = new StringBuilder(one_MB_string); 
foreach(var token in tokens) 
{ 
    sb.Replace(token, "new string"); 
} 

Es ist ziemlich langsam! Gibt es irgendwelche einfachen Dinge, die ich tun kann, um es zu beschleunigen?

Token ist eine Liste von etwa eintausend Strings, die jeweils 5 bis 15 Zeichen lang sind.

Answer 1

Anstatt Ersetzungen in einer großen Zeichenfolge durchzuführen (was bedeutet, dass Sie viele Daten umziehen), arbeiten Sie die Zeichenfolge ab und ersetzen Sie jeweils ein Token.

Erstellen Sie eine Liste, die den nächsten Index für jedes Token enthält. Suchen Sie das Token, das zuerst angezeigt wird, und kopieren Sie den Text bis zum Token in das Ergebnis, gefolgt vom Ersetzen des Tokens. Überprüfen Sie dann, wo sich das nächste Vorkommen dieses Tokens in der Zeichenfolge befindet, um die Liste auf dem neuesten Stand zu halten. Wiederholen Sie den Vorgang, bis keine weiteren Token gefunden wurden, und kopieren Sie den verbleibenden Text in das Ergebnis.

Ich machte einen einfachen Test, und diese Methode ersetzte 125000 Ersetzungen auf einer 1000000 Zeichenfolge in 208 Millisekunden.

Token und TokenList Klassen:

public class Token { 

    public string Text { get; private set; } 
    public string Replacement { get; private set; } 
    public int Index { get; set; } 

    public Token(string text, string replacement) { 
     Text = text; 
     Replacement = replacement; 
    } 

} 

public class TokenList : List<Token>{ 

    public void Add(string text, string replacement) { 
     Add(new Token(text, replacement)); 
    } 

    private Token GetFirstToken() { 
     Token result = null; 
     int index = int.MaxValue; 
     foreach (Token token in this) { 
      if (token.Index != -1 && token.Index < index) { 
       index = token.Index; 
       result = token; 
      } 
     } 
     return result; 
    } 

    public string Replace(string text) { 
     StringBuilder result = new StringBuilder(); 
     foreach (Token token in this) { 
      token.Index = text.IndexOf(token.Text); 
     } 
     int index = 0; 
     Token next; 
     while ((next = GetFirstToken()) != null) { 
      if (index < next.Index) { 
       result.Append(text, index, next.Index - index); 
       index = next.Index; 
      } 
      result.Append(next.Replacement); 
      index += next.Text.Length; 
      next.Index = text.IndexOf(next.Text, index); 
     } 
     if (index < text.Length) { 
      result.Append(text, index, text.Length - index); 
     } 
     return result.ToString(); 
    } 

} 

Anwendungsbeispiel:

string text = 
    "This is a text with some words that will be replaced by tokens."; 

var tokens = new TokenList(); 
tokens.Add("text", "TXT"); 
tokens.Add("words", "WRD"); 
tokens.Add("replaced", "RPL"); 

string result = tokens.Replace(text); 
Console.WriteLine(result); 

Ausgang:

This is a TXT with some WRD that will be RPL by tokens. 

Hinweis: Dieser Code behandelt nicht Token überlappen. Wenn Sie zum Beispiel die Token "Ananas" und "Apfel" haben, funktioniert der Code nicht richtig.

Edit:
Um den Code Arbeit mit überlappenden Tokens zu machen, ersetzen Sie diese Zeile:

next.Index = text.IndexOf(next.Text, index); 

mit diesem Code:

foreach (Token token in this) { 
    if (token.Index != -1 && token.Index < index) { 
     token.Index = text.IndexOf(token.Text, index); 
    } 
} 

Answer 2

Wäre es schneller, die Zeichenfolge einen Token zu einem Zeitpunkt zu erstellen, nur wenn nötig ersetzen? Dazu GetObfuscatedString() wie so umgesetzt werden könnten:

string GetObfuscatedString(string token) 
{ 
    if (TokenShouldBeReplaced(token)) 
     return ReplacementForToken(token) 
    else 
     return token; 
} 

Jetzt können Sie jedes Token an den Baumeister wie folgt hinzu:

StringBuilder sb = new StringBuilder(one_MB_string.Length); 
foreach (string token in tokens) 
{ 
    sb.Append(da.GetObfuscatedString(token)); 
} 

Sie werden nur einen Durchlauf über die Saite zu machen haben, und es könnte schneller sein.

Answer 3

Wenn Sie Ihre Token über einen regulären Ausdruck finden können, können Sie etwas tun:

RegEx TokenFinder = new Regex("(tokencriteria)"); 
string newstring = myRegEx.Replace(one_MB_string, new MatchEvaluator(Replacer)); 

Dann definieren Replacer als:

private string Replacer(Match match) 
{ 
    string token= match.Groups[1].Value; 
    return GetObfuscatedString(token); 
} 

Answer 4

OK, Sie sehen, warum es lange dauert, Recht?

Sie haben 1   MB-Strings, und für jedes Token wird replace durch die 1   MB iterieren und eine neue 1   MB-Kopie erstellen. Nun, keine exakte Kopie, da ein gefundenes Token durch den neuen Token-Wert ersetzt wird. Aber für jeden Token, den Sie lesen 1   MB, neu erstellen 1   MB Speicher und Schreiben 1   MB.

Können wir uns jetzt einen besseren Weg vorstellen? Wie wäre es, anstatt die 1   MB-Zeichenkette für jedes Token zu durchlaufen, gehen wir stattdessen einmal darüber.

Bevor wir es gehen, erstellen wir eine leere Ausgabezeichenfolge.

Wenn wir die Quellzeichenfolge durchlaufen, werden wir token.length() Zeichen vorwärts springen und das verschleierte Token ausschreiben, wenn wir ein Token finden. Andernfalls gehen wir zum nächsten Zeichen über.

Im Wesentlichen drehen wir den Prozess um, machen die for-Schleife auf der langen Kette und suchen bei jedem Punkt nach einem Token. Um das schnell zu machen, wollen wir die Token schnell loopen, also fügen wir sie in eine Art assoziatives Array (ein Set) ein.

Ich sehe, warum es lange dauert in Ordnung, , aber nicht sicher auf die Lösung. Für jede 1   MB Zeichenfolge, auf der ich Ersetzungen durchführen, habe ich 1 bis 2 Tausend Tokans, die ich ersetzen möchte.So geht zeichenweise für jeden von tausend Token suchen scheint nicht schneller

Im Allgemeinen, was am längsten in der Programmierung nimmt? Speicher neu erstellen.

Jetzt, wenn wir einen StringBuffer erstellen, ist wahrscheinlich, dass etwas Speicherplatz zugewiesen wird (sagen wir 64 Bytes, und dass, wenn wir mehr als seine aktuelle Kapazität anhängen, es wahrscheinlich verdoppelt seinen Platz. Und dann Kopiert den alten Zeichenpuffer in den neuen. (Es ist möglich, dass wir Cs realloc und nicht kopieren müssen.)

Also, wenn wir mit 64 Bytes beginnen, um bis zu 1   MB zu erhalten, ordnen wir zu und kopieren : 64, dann 128, dann 256, dann 512, dann 1024, dann 2048 ... wir machen das zwanzigmal, um auf 1   MB zu kommen, und um hierher zu kommen, haben wir 1   MB zugewiesen, nur um es zu werfen

Vorzuordnen, indem man etwas verwendet, das der C++ reserve() Funktion analog ist, lässt uns mindestens das auf einmal machen. Aber es ist immer noch auf einmal jeder Token. Sie produzieren mindestens 1   MB temporäre Zeichenfolge für jeweils Token. Wenn Sie 2000 Tokens haben, reservieren Sie etwa 2 Milliarden Byte Speicher, die alle mit 1   MB enden. Jeder 1   MB-Wegwerfwert enthält die Transformation der vorherigen resultierenden Zeichenfolge, wobei das aktuelle Token angewendet wird.

Und deshalb dauert es so lange.

Nun ja, die Entscheidung, welches Token (falls vorhanden) für jedes Zeichen gilt, braucht auch Zeit. Vielleicht möchten Sie einen regulären Ausdruck verwenden, der intern eine Zustandsmaschine aufbaut, um alle Möglichkeiten zu durchlaufen, anstatt eine festgelegte Suche, wie ich es anfangs vorgeschlagen habe. Aber was dich wirklich umbringt, ist die Zeit, all diesen Speicher für 2000 Kopien einer 1   MB-Zeichenfolge zu reservieren.

Dan Gibson schlägt vor:

Sortieren Sie Ihre Jetons, so dass Sie nicht zu Blick haben für tausend jedes Charakter-Token. Die Sortierung würde etwa mal dauern, aber es würde wahrscheinlich schneller sein, da Sie Tausende von Tokens nicht jedes Zeichen suchen müssen.

Das war meine Überlegung dahinter, sie in ein assoziatives Array (z. B. Java HashSet) zu setzen. Aber das andere Problem ist die Übereinstimmung, z. B. wenn ein Token "a" und ein anderes "an" ist - wenn es irgendwelche gemeinsamen Präfixe gibt, das heißt, wie passen wir zusammen?

Hier kommt die Antwort von Keltex zum Tragen: Er delegiert das Matching an eine Regex, was eine großartige Idee ist, wie Regex bereits definiert (greedy match) und implementiert, wie das geht. Sobald die Übereinstimmung hergestellt ist, können wir untersuchen, was erfasst wurde, und dann eine Java-Map (auch ein assoziatives Array) verwenden, um das verschleierte Token für das übereinstimmende, unverschmutzte Token zu finden.

Ich wollte meine Antwort auf die nicht nur, wie dies zu beheben, sondern auf warum es ein Problem in erster Linie war konzentrieren.