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

Intento confundir una gran cantidad de datos. He creado una lista de palabras (tokens) que quiero reemplazar y estoy reemplazando las palabras una por una usando 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.

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.

Haga una lista que contenga el siguiente índice para cada token, busque el token que es primero, luego copie 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.

Token y TokenList clases:

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

Salida:

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

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

Editar:
Para hacer que el código funcione con tokens 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); } } 

OK, ves por qué está tomando mucho tiempo, ¿verdad?

Tiene cadenas de 1 MB, y para cada token, replace itera a través de 1 MB y hace una nueva copia de 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 ello lo recorremos una vez?

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

A medida que recorremos la cadena fuente, si encontramos un token, token.length() caracteres token.length() hacia adelante y escribiremos el token ofuscado. De lo contrario, procederemos al siguiente personaje.

Esencialmente, estamos volviendo el proceso al revés, haciendo el ciclo for en la cadena larga, y en cada punto buscando un token. 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é tarda todo el tiempo, pero no estoy seguro de la solución. Por cada cadena de 1 MB en la que realizo reemplazos, tengo de 1 a 2 mil tokans que deseo reemplazar. Así que caminar carácter por personaje en busca de miles de tokens no parece más rápido

En general, ¿qué lleva más tiempo en la progtwigción? New’ing up memory.

Ahora cuando creamos un StringBuffer, lo que probablemente ocurra es que se asigne una cierta cantidad de espacio (digamos, 64 bytes, y que cada vez que anexemos más de su capacidad actual, probablemente, digamos, duplique su espacio. Y luego copie el viejo personaje buffer para el nuevo. (Es posible que podamos can realloc de C, y no tener que copiar.)

Entonces, 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 desecharlo.

La asignación previa, al usar algo análogo a la función reserve() 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 por cada token. Si tiene 2000 tokens, está asignando aproximadamente 2 billones de bytes de memoria, todo para terminar con 1 MB. Cada 1 MB de descarte 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 personaje 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 para asignar toda esa memoria, para 2000 copias de una cadena de 1 MB.

Dan Gibson sugiere:

Clasifica tus tokens para que no tengas que buscar miles de tokens en cada personaje. El género tomaría algún tiempo, pero probablemente terminaría siendo más rápido ya que no tienes que buscar miles de tokens en cada personaje.

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 el emparejamiento en un Regex, que es una gran idea, ya que Regex ya define (concordancia 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.

Si puede encontrar sus tokens 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)); 

Luego defina Replacer como:

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

¿Sería más rápido construir la cadena una ficha a la vez, solo reemplazando si fuera necesario? Para esto, GetObfuscatedString() podría implementarse así:

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

Ahora puede agregar cada token al generador de esta manera:

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

Solo tendrá que hacer una pasada sobre la cadena, y podría ser más rápido.