提高正则表达效率

Question

我有大约100k个Outlook邮件项目，每个正文约500-600个字符。我有一个必须搜索每个主体的580个关键字列表，然后在底部添加单词。

我相信我已经增加了大多数功能的效率，但它仍然需要花费大量的时间。即使是100封电子邮件也需要4秒左右的时间。

我跑为每个关键字列表两种功能（290个关键字每个列表）。

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

是否有反正我可以提高此功能的效率？

可能放缓下来的另一件事是，我使用的HTML敏捷性包通过一些节点导航，并拉出体（nSearch.InnerHtml）。 _keywordList是一个List项目，而不是一个数组。

Answer 1

我假设COM调用nSearch.InnerHtml是相当缓慢的，你重复调用您所检查每一个字。您可以简单地缓存通话结果：

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

另一个优化是由Jeff Yates提出的。例如。通过使用单一模式：

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

Answer 2

正则表达式可以优化了不少，当你只是要匹配一组固定的常量字符串的。而不是几场比赛，例如对于“冬天”，“胜利”或“袋熊”，您可以匹配"w(in(ter)?|ombat)"，例如（杰弗里弗里德尔的书可以给你很多这样的想法）。这种优化也被嵌入到一些程序中，特别是emacs（'regexp-opt'）。我对.NET不太熟悉，但我认为某人已编程类似的功能 - 谷歌的“正则表达式优化”。

Answer 3

我不认为这是对正则表达式的工作。您最好逐字搜索每个消息，并检查每个单词是否与您的单词列表相对应。通过你的方法，你可以搜索每条消息n次，其中n是你想要查找的单词的数量 - 这也就不足为奇了。

Answer 4

一件事，你可以很容易做的就是比赛安剑铮，卓杰在一个全力以赴的话通过构建一个表达式，如：

\ B（：字词1 |单词2 | WORD3 | ....）\ b

然后，您可以预编译模式并重新使用它来查找每封电子邮件的所有发生（不知道如何使用.Net API执行此操作，但必须有一种方法）。

的另一件事是，而不是使用忽略大小写的标志，如果你将所有的都为小写，可能会给你一个小的提升速度（需要个人资料，因为它的实现依赖）。不要忘记在你的个人资料上预热CLR。

Answer 5

大部分的时间来失败，所以要尽量减少故障形式的比赛。

如果搜索关键字不频繁，您可以同时测试所有的关键字（使用正则表达式\b(aaa|bbb|ccc|....)\b），然后排除没有匹配的电子邮件。至少有一场比赛的球员会进行彻底搜索。

Answer 6

如果正则表达式确实是瓶颈，甚至对其进行优化（通过连接检索词一个表达）没有帮助，考虑使用多模式搜索算法，比如Wu-Manber。

I’ve posted a very simple implementation这里堆栈溢出。它是用C++编写的，但由于代码简单明了，应该很容易将其转换为C＃。

注意，这将找到的话随时随地，不只是在单词边界。然而，这可以很容易地测试后您检查文本是否包含任何话;由前后各命中后检查字符或手动 - 无论是再次使用正则表达式（更快现在你只测试单个电子邮件）。

Answer 7

如果你的问题是关于搜索包含特定字符串，你应该使用前景的搜索工具增益Outlook项目...

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

Answer 8

如果您的关键字搜索是直接的文字，即不包含进一步的正则表达式模式匹配，则其他方法可能更合适。下面的代码演示了一个这样的方法，该代码只能通过每个电子邮件去一次，你的代码通过每个电子邮件290时（两次）

 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

去如果你能使用的.Net 3.5+和LINQ，你可以这样做这个。

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 
    } 
} 

...重复使用正则表达式的例子...

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

这可能更快。你可以利用这样的正则表达式组：

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

这样你只能使用一个正则表达式。而小组的索引应通过1偏移与_keywordList相关，因此行wordFound.Add(_keywordList[i-1]);

UPDATE：

看着我的代码后再次我只是意识到，把比赛变成组实际上是不必要的。正则表达式组有一些开销。相反，您可以从模式中删除括号，然后将匹配自己添加到wordFound列表中。这会产生相同的效果，但速度会更快。

它会是这样的：

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