optimization - A better way to replace many strings - obfuscation in C#

Question

I'm trying to obfuscate a large amount of data. I've created a list of words (tokens) which I want to replace and I am replacing the words one by one using the StringBuilder class, like so:

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

It's pretty slow! Are there any simple things that I can do to speed it up?

tokens is a list of about one thousand strings, each 5 to 15 characters in length.

Answer 1

Instead of doing replacements in a huge string (which means that you move around a lot of data), work through the string and replace a token at a time.

Make a list containing the next index for each token, locate the token that is first, then copy the text up to the token to the result followed by the replacement for the token. Then check where the next occurance of that token is in the string to keep the list up to date. Repeat until there are no more tokens found, then copy the remaining text to the result.

I made a simple test, and this method did 125000 replacements on a 1000000 character string in 208 milliseconds.

Token and TokenList classes:

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

}

Example of usage:

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

Output:

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

Note: This code does not handle overlapping tokens. If you for example have the tokens "pineapple" and "apple", the code doesn't work properly.

Edit:
To make the code work with overlapping tokens, replace this line:

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

with this code:

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