Increasing Regex Efficiency

Question

I have about 100k Outlook mail items that have about 500-600 chars per Body. I have a list of 580 keywords that must search through each body, then append the words at the bottom.

I believe I've increased the efficiency of the majority of the function, but it still takes a lot of time. Even for 100 emails it takes about 4 seconds.

I run two functions for each keyword list (290 keywords each list).

       public List<string> Keyword_Search(HtmlNode nSearch)
    {
        var wordFound = new List<string>();
        foreach (string currWord in _keywordList)
        {
            bool isMatch = Regex.IsMatch(nSearch.InnerHtml, "\\b" + @currWord + "\\b",
                                                  RegexOptions.IgnoreCase);
            if (isMatch)
            {
                wordFound.Add(currWord);
            }
        }
        return wordFound;
    }

Is there anyway I can increase the efficiency of this function?

The other thing that might be slowing it down is that I use HTML Agility Pack to navigate through some nodes and pull out the body (nSearch.InnerHtml). The _keywordList is a List item, and not an array.

Answer 1

Regular expressions can be optimized quite a bit when you just want to match against a fixed set of constant strings. Instead of several matches, e.g. against "winter", "win" or "wombat", you can just match against "w(in(ter)?|ombat)", for example (Jeffrey Friedl's book can give you lots of ideas like this). This kind of optimisation is also built into some programs, notably emacs ('regexp-opt'). I'm not too familiar with .NET, but I assume someone has programmed similar functionality - google for "regexp optimization".

Answer 2

I don't think this is a job for regular expressions. You might be better off searching each message word by word and checking each word against your word list. With the approach you have, you're searching each message n times where n is the number of words you want to find - it's no wonder that it takes a while.

Answer 3

one thing you can easily do is match agaist all the words in one go by building an expression like:

\b(?:word1|word2|word3|....)\b

Then you can precompile the pattern and reuse it to look up all occurencesfor each email (not sure how you do this with .Net API, but there must be a way).

Another thing is instead of using the ignorecase flag, if you convert everything to lowercase, that might give you a small speed boost (need to profile it as it's implementation dependent). Don't forget to warm up the CLR when you profile.

Answer 4

Most of the time comes form matches that fail, so you want to minimize failures.

If the search keyword are not frequent, you can test for all of them at the same time (with regexp \b(aaa|bbb|ccc|....)\b), then you exclude the emails with no matches. The one that have at least one match, you do a thorough search.

Answer 5

I assume that the COM call nSearch.InnerHtml is pretty slow and you repeat the call for every single word that you are checking. You can simply cache the result of the call:

public List<string> Keyword_Search(HtmlNode nSearch)
{
    var wordFound = new List<string>();

    // cache inner HTML
    string innerHtml = nSearch.InnerHtml;

    foreach (string currWord in _keywordList)
    {
        bool isMatch = Regex.IsMatch(innerHtml, "\\b" + @currWord + "\\b",
                                              RegexOptions.IgnoreCase);
        if (isMatch)
        {
            wordFound.Add(currWord);
        }
    }
    return wordFound;
}

Another optimization would be the one suggested by Jeff Yates. E.g. by using a single pattern:

string pattern = @"(\b(?:" + string.Join("|", _keywordList) + @")\b)";

Answer 6

If the regular expression is indeed the bottle neck, and even optimizing it (by concatenating the search words to one expression) doesn’t help, consider using a multi-pattern search algorithm, such as Wu-Manber.

I’ve posted a very simple implementation here on Stack Overflow. It’s written in C++ but since the code is straightforward it should be easy to translate it to C#.

Notice that this will find words anywhere, not just at word boundaries. However, this can be easily tested after you’ve checked whether the text contains any words; either once again with a regular expression (now you only test individual emails – much faster) or manually by checking the characters before and after the individual hits.

Answer 7

If your problem is about searching for outlook items containing certain string, you should get a gain from using outlooks search facilities...

see: http://msdn.microsoft.com/en-us/library/bb644806.aspx

Answer 8

If your keyword search is straight literals, ie do not contain further regex pattern matches, then other method may be more appropriate. The following code demonstrates one such method, this code only goes through each email once, your code went through each email 290 time( twice)

        public List<string> FindKeywords(string emailbody, List<string> keywordList)
        {
            // may want to clean up the input a bit, such as replacing '.' and ',' with a space
            // and remove double spaces

            string emailBodyAsUppercase = emailbody.ToUpper();

            List<string> emailBodyAsList = new List<string>(emailBodyAsUppercase.Split(' '));

            List<string> foundKeywords = new List<string>(emailBodyAsList.Intersect(keywordList));


            return foundKeywords;
        }

Answer 9

If you can use .Net 3.5+ and LINQ you could do something like this.

public static class HtmlNodeTools
{
    public static IEnumerable<string> MatchedKeywords(
        this HtmlNode nSearch,
             IEnumerable<string> keywordList)
    {
        //// as regex
        //var innerHtml = nSearch.InnerHtml;
        //return keywordList.Where(kw =>
        //       Regex.IsMatch(innerHtml, 
        //                     @"\b" + kw + @"\b",
        //                     RegexOptions.IgnoreCase)
        //        );

        //would be faster if you don't need the pattern matching
        var innerHtml = ' ' + nSearch.InnerHtml + ' ';
        return keywordList.Where(kw => innerHtml.Contains(kw));
    }
}
class Program
{
    static void Main(string[] args)
    {
        var keyworkList = new string[] { "hello", "world", "nomatch" };
        var h = new HtmlNode()
        {
            InnerHtml = "hi there hello other world"
        };

        var matched = h.MatchedKeywords(keyworkList).ToList();
        //hello, world
    }
}

... reused regex example ...

public static class HtmlNodeTools
{
    public static IEnumerable<string> MatchedKeywords(
        this HtmlNode nSearch,
             IEnumerable<KeyValuePair<string, Regex>> keywordList)
    {
        // as regex
        var innerHtml = nSearch.InnerHtml;
        return from kvp in keywordList
               where kvp.Value.IsMatch(innerHtml)
               select kvp.Key;
    }
}
class Program
{
    static void Main(string[] args)
    {
        var keyworkList = new string[] { "hello", "world", "nomatch" };
        var h = new HtmlNode()
        {
            InnerHtml = "hi there hello other world"
        };

        var keyworkSet = keyworkList.Select(kw => 
            new KeyValuePair<string, Regex>(kw, 
                                            new Regex(
                                                @"\b" + kw + @"\b", 
                                                RegexOptions.IgnoreCase)
                                                )
                                            ).ToArray();

        var matched = h.MatchedKeywords(keyworkSet).ToList();
        //hello, world
    }
}

Answer 10

This may be faster. You can leverage Regex Groups like this:

    public List<string> Keyword_Search(HtmlNode nSearch)
    {
        var wordFound = new List<string>();

        // cache inner HTML
        string innerHtml = nSearch.InnerHtml;
        string pattern = "(\\b" + string.Join("\\b)|(\\b", _keywordList) + "\\b)";
        Regex myRegex = new Regex(pattern, RegexOptions.IgnoreCase);
        MatchCollection myMatches = myRegex.Matches(innerHtml);

        foreach (Match myMatch in myMatches)
        {
            // Group 0 represents the entire match so we skip that one
            for (int i = 1; i < myMatch.Groups.Count; i++)
            {
                if (myMatch.Groups[i].Success)
                    wordFound.Add(_keywordList[i-1]);
            }
        }

        return wordFound;
    }    

This way you're only using one regular expression. And the indices of the Groups should correlate with your _keywordList by an offset of 1, hence the line wordFound.Add(_keywordList[i-1]);

UPDATE:

After looking at my code again I just realized that putting the matches into Groups is really unnecessary. And Regex Groups have some overhead. Instead, you could remove the parenthesis from the pattern, and then simply add the matches themselves to the wordFound list. This would produce the same effect, but it'd be faster.

It'd be something like this:

public List<string> Keyword_Search(HtmlNode nSearch)
{
    var wordFound = new List<string>();

    // cache inner HTML
    string innerHtml = nSearch.InnerHtml;
    string pattern = "\\b(?:" + string.Join("|", _keywordList) + ")\\b";
    Regex myRegex = new Regex(pattern, RegexOptions.IgnoreCase);
    MatchCollection myMatches = myRegex.Matches(innerHtml);

    foreach (Match myMatch in myMatches)
    {
        wordFound.Add(myMatch.Value);
    }

    return wordFound;
}