.NET String parsing performance improvement - Possible Code Smell

Question

The code below is designed to take a string in and remove any of a set of arbitrary words that are considered non-essential to a search phrase.

I didn't write the code, but need to incorporate it into something else. It works, and that's good, but it just feels wrong to me. However, I can't seem to get my head outside the box that this method has created to think of another approach.

Maybe I'm just making it more complicated than it needs to be, but I feel like this might be cleaner with a different technique, perhaps by using LINQ.

I would welcome any suggestions; including the suggestion that I'm over thinking it and that the existing code is perfectly clear, concise and performant.

So, here's the code:

private string RemoveNonEssentialWords(string phrase)
{
    //This array is being created manually for demo purposes.  In production code it's passed in from elsewhere.
    string[] nonessentials = {"left", "right", "acute", "chronic", "excessive", "extensive", 
                                    "upper", "lower", "complete", "partial", "subacute", "severe",
                                    "moderate", "total", "small", "large", "minor", "multiple", "early",
                                    "major", "bilateral", "progressive"};
    int index = -1;

    for (int i = 0; i < nonessentials.Length; i++)
    {
        index = phrase.ToLower().IndexOf(nonessentials[i]);
        while (index >= 0)
        {
            phrase = phrase.Remove(index, nonessentials[i].Length);
            phrase = phrase.Trim().Replace("  ", " ");
            index = phrase.IndexOf(nonessentials[i]);
        }
    }

    return phrase;
}

Thanks in advance for your help.

Cheers,

Steve

Answer 1

I would use a regular expression (created inside the function) for this task. I think it would be capable of doing all the processing at once without having to make multiple passes through the string or having to create multiple intermediate strings.

private string RemoveNonEssentialWords(string phrase)
{
    return Regex.Replace(phrase, // input
                         @"\b(" + String.Join("|", nonessentials) + @")\b", // pattern
                         "", // replacement
                         RegexOptions.IgnoreCase)
           .Replace("  ", " ");
}

The \b at the beginning and end of the pattern makes sure that the match is on a boundary between alphanumeric and non-alphanumeric characters. In other words, it will not match just part of the word, like your sample code does.

Answer 2

Yeah, that smells.

I like little state machines for parsing, they can be self-contained inside a method using lists of delegates, looping through the characters in the input and sending each one through the state functions (which I have return the next state function based on the examined character).

For performance I would flush out whole words to a string builder after I've hit a separating character and checked the word against the list (might use a hash set for that)

Answer 3

I guess your code is not doing what you want it to do anyway. "moderated" would be converted to "d" if I'm right. To get a good solution you have to specify your requirements a bit more detailed. I would probably use Replace or regular expressions.

Answer 4

I would create A Hash table of Removed words parse each word if in the hash remove it only one time through the array and I believe that creating a has table is O(n).

Answer 5

How does this look?

        foreach (string nonEssent in nonessentials)
        {
            phrase.Replace(nonEssent, String.Empty);
        }
        phrase.Replace("  ", " ");

Answer 6

This appears to be an algorithm for removing stop words from a search phrase.

Here's one thought: If this is in fact being used for a search, do you need the resulting phrase to be a perfect representation of the original (with all original whitespace intact), but with stop words removed, or can it be "close enough" so that the results are still effectively the same?

One approach would be to tokenize the phrase (using the approach of your choice - could be a regex, I'll use a simple split) and then reassemble it with the stop words removed. Example:

public static string RemoveStopWords(string phrase, IEnumerable<string> stop)
{
    var tokens = Tokenize(phrase);
    var filteredTokens = tokens.Where(s => !stop.Contains(s));
    return string.Join(" ", filteredTokens.ToArray());
}

public static IEnumerable<string> Tokenize(string phrase)
{
    return string.Split(phrase, ' ');
    // Or use a regex, such as:
    //    return Regex.Split(phrase, @"\W+");
}

This won't give you exactly the same result, but I'll bet that it's close enough and it will definitely run a lot more efficiently. Actual search engines use an approach similar to this, since everything is indexed and searched at the word level, not the character level.

Answer 7

If you want to go the Regex route, you could do it like this. If you're going for speed it's worth a try and you can compare/contrast with other methods:

Start by creating a Regex from the array input. Something like:

var regexString = "\\b(" + string.Join("|", nonessentials) + ")\\b";

That will result in something like:

\b(left|right|chronic)\b

Then create a Regex object to do the find/replace:

System.Text.RegularExpressions.Regex regex = new System.Text.RegularExpressions.Regex(regexString, System.Text.RegularExpressions.RegexOptions.IgnoreCase);

Then you can just do a Replace like so:

string fixedPhrase = regex.Replace(phrase, "");