提高正則表達效率

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