Una mejor manera de reemplazar muchas cadenas: ofuscación en C#

Question

Intento ofuscar una gran cantidad de datos. He creado una lista de palabras (tokens) que quiero reemplazar y estoy reemplazando las palabras de uno en uno utilizando la clase StringBuilder, así:

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

Es bastante lento! ¿Hay alguna cosa simple que pueda hacer para acelerarla?

tokens es una lista de aproximadamente mil cadenas, cada una de 5 a 15 caracteres de longitud.

Answer 1

En lugar de hacer reemplazos en una cadena enorme (lo que significa que se mueve una gran cantidad de datos), trabaje a través de la cadena y reemplace un token a la vez.

Haz una lista que contenga el siguiente índice para cada token, localiza el token que está primero, luego copia el texto hasta el token en el resultado seguido del reemplazo del token. Luego, compruebe dónde está la próxima aparición de ese token en la cadena para mantener la lista actualizada. Repita hasta que no se encuentren más tokens, luego copie el texto restante al resultado.

Hice una prueba simple, y este método hizo 125000 reemplazos en una cadena de 1000000 caracteres en 208 milisegundos.

clases Token y listaElemento:

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

} 

Ejemplo de uso:

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

de salida:

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

Nota: Este código no maneja tokens superpuestas. Si, por ejemplo, tiene los símbolos "piña" y "manzana", el código no funciona correctamente.

Editar:
para hacer que el código con símbolos superpuestos, reemplace esta línea:

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

con este código:

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

Answer 2

¿Sería más rápido construir la cadena una ficha a la vez, solo reemplazando si fuera necesario? Para ello, GetObfuscatedString() podrían ser implementadas de esta manera:

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

Ahora, se puede añadir cada ficha al constructor de esta manera:

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

Usted lo único que tiene que hacer uno pase la cadena, y podría ser más rápido.

Answer 3

Si usted puede encontrar sus fichas a través de una expresión regular, puede hacer algo como esto:

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

a continuación, definir Sustituto como:

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

Answer 4

bien, ves por qué está tomando mucho tiempo, ¿derecho?

dispones de 1 MB   cuerdas, y por cada ficha, se sustituyen iteración a través de los   1 MB y hacer una nueva copia   1 MB. Bueno, no es una copia exacta, ya que cualquier token encontrado se reemplaza con el nuevo valor de token. Pero para cada token está leyendo 1   MB, renovando 1   MB de almacenamiento y escribiendo 1   MB.

Ahora, ¿podemos pensar en una mejor manera de hacer esto? ¿Qué tal si en lugar de iterar la cadena de 1   MB para cada token, en lugar de eso lo caminamos una vez?

Antes de recorrerlo, crearemos una cadena de salida vacía.

Mientras caminamos por la cadena fuente, si encontramos un token, saltaremos token.length() caracteres hacia adelante y escribiremos el token ofuscado. De lo contrario, procederemos al siguiente personaje.

Básicamente, estamos dando vuelta el proceso de adentro hacia afuera, haciendo el bucle for en la cuerda larga, y en cada punto buscando una ficha. Para que esto sea rápido, querremos un bucle rápido para los tokens, por lo que los colocaremos en una especie de matriz asociativa (un conjunto).

Veo por qué está tardando mucho bien, pero no estoy seguro de la solución. Para cada 1   MB cadena en la que realizo reemplazos , tengo de 1 a 2 mil tokans que deseo reemplazar.Por lo que caminar carácter por carácter en busca de cualquier de mil fichas no parece más rápido

En general, lo que lleva más tiempo en la programación? New'ing up memory.

Ahora cuando creamos un StringBuffer, lo que probablemente sucede es que se asigna una cierta cantidad de espacio (digamos, 64 bytes, y que cada vez que agreguemos más de su capacidad actual, probablemente, digamos, duplique su espacio. copia el búfer de caracteres anterior al nuevo. (Es posible que podamos el realloc de C, y no tener que copiar.)

Así que si comenzamos con 64 bytes, para obtener hasta 1   MB, asignamos y copiamos : 64, luego 128, luego 256, luego 512, luego 1024, luego 2048 ... hacemos esto veinte veces para obtener hasta 1   MB. Y al llegar aquí, hemos asignado 1   MB solo para lanzarlo de distancia.

La preasignación, al usar algo análogo a la función reserve() de C++, al menos nos permitirá hacerlo todo de una vez. Pero sigue siendo todo de una vez para cada token. Al menos está produciendo una cadena temporal de 1   MB para cada token. Si tiene 2000 tokens, está asignando aproximadamente 2 billones de bytes de memoria, todo para terminar con 1   MB. Cada 1   MB desechable contiene la transformación de la cadena resultante anterior, con el token actual aplicado.

Y es por eso que esto lleva tanto tiempo.

Ahora sí, decidir qué token aplicar (en su caso), en cada carácter, también lleva tiempo. Es posible que desee utilizar una expresión regular, que internamente crea una máquina de estado para ejecutar todas las posibilidades, en lugar de una búsqueda de conjunto, como sugerí inicialmente. Pero lo que realmente te está matando es el tiempo de asignar toda esa memoria, para 2000 copias de una cadena de 1   MB.

Dan Gibson sugiere:

Ordenar sus fichas por lo que no tienen que vistazo a mil Fichas cada uno carácter. El género demoraría un tiempo de , pero probablemente terminaría siendo más rápido ya que no es necesario que busque miles de tokens por cada caracteres.

Ese fue mi razonamiento detrás de ponerlos en una matriz asociativa (por ejemplo, Java HashSet). Pero el otro problema es la coincidencia, por ejemplo, si un token es "a" y otro es "an" - si hay algún prefijo común, es decir, ¿cómo coincidimos?

Aquí es donde la respuesta de Keltex es útil: delega la coincidencia en una Regex, lo cual es una gran idea, ya que una Regex ya define (coincidencia ambiciosa) e implementa cómo hacerlo. Una vez que se realiza la coincidencia, podemos examinar lo que se ha capturado y, a continuación, usar un mapa de Java (también una matriz asociativa) para encontrar el token ofuscado para el uno coincidente y no difuminado.

Quería concentrar mi respuesta no solo en cómo solucionar esto, sino en por qué había un problema en primer lugar.