Un modo migliore per sostituire molte stringhe - offuscamento in C#

Question

Sto cercando di offuscare una grande quantità di dati. Ho creato una lista di parole (token) che voglio sostituire e Sto sostituendo le parole una per una utilizzando la classe StringBuilder, in questo modo:

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

E 'piuttosto lento! Ci sono cose semplici che posso fare per velocizzarlo?

token è un elenco di circa mille stringhe, ciascuna di lunghezza compresa tra 5 e 15 caratteri.

Answer 1

Invece di fare sostituzioni in una stringa enorme (il che significa che si spostano molti dati), lavorare sulla stringa e sostituire un token alla volta.

Creare un elenco contenente l'indice successivo per ciascun token, individuare il token che è il primo, quindi copiare il testo fino al token nel risultato seguito dalla sostituzione del token. Quindi controlla dove si trova la prossima occorrenza di quel token nella stringa per mantenere aggiornato l'elenco. Ripeti fino a quando non vengono trovati più token, quindi copia il testo rimanente nel risultato.

Ho eseguito un semplice test e questo metodo ha effettuato 125000 sostituzioni su una stringa di 1000000 caratteri in 208 millisecondi.

classi token e ListaToken:

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

} 

Esempio di utilizzo:

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

uscita:

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

Nota: Questo codice non gestisce sovrapposizione gettoni. Se per esempio hai i token "ananas" e "apple", il codice non funziona correttamente.

Edit:
per far funzionare il codice con sovrapposizione gettoni, sostituire questa linea:

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

con questo codice:

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

Answer 2

Sarebbe più veloce costruire la stringa un token alla volta, sostituendo solo se necessario? Per questo, GetObfuscatedString() potrebbero essere attuate in questo modo:

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

Ora, è possibile aggiungere ogni token per il costruttore in questo modo:

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

Dovrete solo a fare un passaggio sopra la stringa, e potrebbe essere più veloce.

Answer 3

Se si riesce a trovare i token tramite un'espressione regolare, si può fare qualcosa di simile:

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

quindi definire Replacer come:

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

Answer 4

OK, si vede il motivo per cui si sta prendendo tempo, destra?

Si dispone di 1   stringhe MB, e per ogni token, la sostituzione sta iterando tramite 1   MB e si esegue una nuova copia 1   MB. Bene, non una copia esatta, poiché ogni token trovato viene sostituito con il nuovo valore del token. Ma per ogni token stai leggendo 1   MB, aggiungendo 1   MB di spazio di archiviazione e scrivendo 1   MB.

Ora, possiamo pensare a un modo migliore di farlo? Che ne dici invece di iterare la stringa 1   MB per ciascun token, ma invece di eseguirla una volta.

Prima di spostarlo, creeremo una stringa di output vuota.

Mentre percorriamo la stringa sorgente, se troviamo un token, saltiamo in avanti i caratteri token.length() e scriviamo il token offuscato. Altrimenti procederemo al prossimo personaggio.

In sostanza, stiamo capovolgendo il processo, eseguendo il ciclo for sulla stringa lunga e in ogni punto cercando un token. Per velocizzare questo, vorremmo un loop-up rapido per i token, quindi li inseriremo in una sorta di array associativo (un set).

Vedo perché sta prendendo molto tempo, ma non sono sicuro sulla correzione. Per ogni stringa 1   MB su cui sto eseguendo sostituzioni , ho da 1 a 2 mila token che voglio sostituire.Quindi camminare carattere per carattere alla ricerca di qualsiasi di un migliaio di gettoni non sembra più veloce

In generale, ciò che prende più lungo in programmazione? Nuova memoria.

Ora, quando creiamo un StringBuffer, è probabile che venga allocata una certa quantità di spazio (diciamo 64 byte e che ogni volta che aggiungiamo più della sua capacità attuale, probabilmente raddoppia il suo spazio. copia il vecchio buffer di caratteri su quello nuovo. (È possibile che possiamo modificare il vecchio e non copiare.)

Quindi se iniziamo con 64 byte, per ottenere fino a 1   MB, assegniamo e copiamo : 64, quindi 128, quindi 256, quindi 512, quindi 1024, quindi 2048 ... lo facciamo venti volte per ottenere fino a 1   MB. E per arrivare qui, abbiamo assegnato 1   MB solo per lanciarlo

Pre-allocare, usando qualcosa di analogo alla funzione reserve() di C++, ci permetterà almeno di farlo tutto in una volta. Ma è ancora tutto in una volta per ogni token. Almeno stai producendo una stringa temporanea 1   MB per ogni token. Se hai 2000 token, stai allocando circa 2 miliardi di byte di memoria, il tutto per finire con 1   MB. Ogni 1   MB throwaway contiene la trasformazione della stringa risultante precedente, con il token corrente applicato.

Ed è per questo che ci vuole così tanto tempo.

Ora sì, decidere quale token applicare (se presente), ad ogni carattere, richiede anche del tempo. Potresti voler usare un'espressione regolare, che crea internamente una macchina a stati per scorrere tutte le possibilità, piuttosto che una ricerca set, come ho suggerito inizialmente. Ma quello che ti sta veramente uccidendo è il tempo di allocare tutta quella memoria, per 2000 copie di una stringa 1   MB.

Dan Gibson suggerisce:

Ordinare i gettoni in modo da non devono look per mille gettoni ogni personaggio . L'ordinamento richiederebbe un po 'di tempo per , ma probabilmente finirebbe a essendo più veloce dato che non è necessario cercare migliaia di token ogni carattere .

Questo era il mio ragionamento dietro la loro messa in un array associativo (ad esempio, Java HashSet). Ma l'altro problema è la corrispondenza, ad es. Se un token è "a" e un altro è "an" - se ci sono dei prefissi comuni, cioè, come possiamo farlo?

Ecco dove la risposta di Keltex è utile: egli delega l'abbinamento a un Regex, che è una grande idea, come già stabilisce un Regex (partita avida) e implementa come farlo. Una volta che la partita è stata fatta, possiamo esaminare ciò che è catturato, quindi utilizzare una mappa Java (anche un array associativo) per trovare il token offuscato per quello abbinato, non offuscato.

Volevo concentrare la mia risposta sul non solo come risolvere questo problema, ma sul perché c'era un problema in primo luogo.