Optimize string.Replace method

Question

I have a list of 200+ words that are not allowed on a website. The string.Replace method below takes ~80ms. If I increase s < 1000 by a factor of 10.00 to s < 10,000 this delay goes to ~834ms, a 10.43 increase. I am woried about the scalability of this function, especially if the list increases in size. I was told strings are immutable and text.Replace() is creating 200 new strings in memory. Is there something similar to a Stringbuilder for this?

List<string> FilteredWords = new List<string>();
FilteredWords.Add("RED");
FilteredWords.Add("GREEN");
FilteredWords.Add("BLACK");
for (int i = 1; i < 200; i++)
{ FilteredWords.Add("STRING " + i.ToString()); }

string text = "";

//simulate a large dynamically generated html page
for (int s = 1; s < 1000; s++)
{ text += @"Lorem ipsum dolor sit amet, minim BLACK cetero cu nam.
            No vix platonem sententiae, pro wisi congue graecis id, GREEN assum interesset in vix.
            Eum tamquam RED pertinacia ex."; }

// This is the function I seek to optimize
foreach (string s in FilteredWords)
{ text = text.Replace(s, "[REMOVED]"); }

Answer 1

If you expect most of the text to be relatively nice than scanning whole text first for matching words could be better approach. You can also normalize words text at the same time to catch some standard replacements.

I.e. scan string by matching individual words (i.e. Regular expression like "\w+"), than for each detected word lookup (potentially normalized value) in dictionary of words to replace.

You can either simply scan first to get list of "words to replace" and than just replace individual word later, or scan and build resulting string at the same time (using StringBuilder or StreamWriter, obviously not String.Concat / +).

Note: Unicode provides large number of good characters to use, so don't expect your effort to be very successful. I.e. try to find "cool" in following text: "you are сооl".

Sample code (relying on Regex.Replace for tokenization and building the string and HashSet for matches).

var toFind = FilteredWords.Aggregate(
      new HashSet<string>(), (c, i) => { c.Add(i); return c;});

text = new Regex(@"\w+")
   .Replace(text, m => toFind.Contains(m.Value) ? "[REMOVED]" : m.Value));

Answer 2

The real regular expression solution would be:

var filteredWord = new Regex(@"\b(?:" + string.Join("|", FilteredWords.Select(Regex.Escape)) + @")\b", RegexOptions.Compiled);
text = filteredWord.Replace(text, "[REMOVED]");

I don’t know whether this is faster (but note that it also only replaces whole words).

Answer 3

There may be a better way, but this is how I would go about solving the problem.

You will need to create a tree structure that contains your dictionary of words to be replaced. The class may be something like:

public class Node 
{
    public Dictionary<char, Node> Children;
    public bool IsWord;
}

Using a dictionary for the Children may not be the best choice, but it provides the easiest example here. Also, you will need a constructor to initialize the Children field. The IsWord field is used to deal with the possibility that a redacted "word" may be the prefix of another redacted "word". For example, if you want to remove both "red" and "redress".

You will build the tree from each character in each of the replacement words. For example:

public void AddWord ( string word ) 
{
    // NOTE: this assumes word is non-null and contains at least one character...

    Node currentNode = Root;

    for (int iIndex = 0; iIndex < word.Length; iIndex++)
    {
        if (currentNode.Children.ContainsKey(word[iIndex])))
        {
            currentNode = currentNode.Children[word[iIndex];
            continue;
        }

        Node newNode = new Node();
        currentNode.Children.Add(word[iIndex], newNode);
        currentNode = newNode;
    }

    // finished, mark the last node as being a complete word..
    currentNode.IsWord = true;
}

You'll need to deal with case sensitivity somewhere in there. Also, you only need to build the tree once, afterwards you can use it from any number of threads without worrying about locking because you will be only reading from it. (Basically, I'm saying: store it in a static somewhere.)

Now, when you are ready to remove words from your string you will need to do the following:

• Create a StringBuilder instance to store the result
• Parse through your source string, looking for the start and stop of a "word". How you define "word" will matter. For simplicity I would suggest starting with Char.IsWhitespace as defining word separators.
• Once you have determined that a range of character is a "word", starting from the root of the tree, locate the child node associated with the first character in "word".
• If you do not find a child node, the entire word is added to the StringBuilder
• If you find a child node, you continue with the next character matching against Children of the current node, until you either run out of characters or out of nodes.
• If you reach the end of the "word", check the last node's IsWord field. If true the word is excluded, do not add it to the StringBuilder. If IsWord is false, the word is not replaced and you add it to the StringBuilder
• Repeat until you have exhausted the input string.

You will also need to add word separators to the StringBuilder, hopefully that will be obvious as you parse the input string. If you are careful to only use the start and stop indices within the input string, you should be able to parse the entire string without creating any garbage strings.

When all of this is done, use StringBuilder.ToString() to get your final result.

You may also need to consider Unicode surrogate codepoints, but you can probably get away without worrying about it.

Beware, I typed this code here directly, so syntax errors, typos and other accidental misdirections are probably included.

Answer 4

Use StringBuilder.Replace and try to do it as a batch operation. That is to say you should try to only create the StringBuilder once as it has some overhead. It won't necessarily be a lot faster but it will be much more memory efficient.

You should also probably only do this sanitation once instead of every time data is requested. If you're reading the data from the database you should consider sanitizing it once when the data is inserted into the database, so there is less work to do when reading and displaying it to the page.