Tăng hiệu quả Regex

Question

Tôi có khoảng 100 nghìn mục thư Outlook có khoảng 500-600 ký tự trên mỗi Nội dung. Tôi có một danh sách 580 từ khóa phải tìm kiếm qua từng phần, sau đó nối thêm các từ ở dưới cùng.

Tôi tin rằng tôi đã tăng hiệu quả của phần lớn chức năng, nhưng vẫn mất rất nhiều thời gian. Ngay cả đối với 100 email, nó mất khoảng 4 giây.

Tôi chạy hai chức năng cho mỗi danh sách từ khóa (290 từ khóa cho mỗi danh sách).

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

Tôi có thể tăng hiệu quả của chức năng này không?

Điều khác có thể làm chậm nó xuống là tôi sử dụng Gói nhanh nhẹn HTML để điều hướng qua một số nút và kéo ra khỏi phần thân (nSearch.InnerHtml). _keywordList là một mục List và không phải là một mảng.

Answer 1

Tôi giả định rằng cuộc gọi COM nSearch.InnerHtml khá chậm và bạn lặp lại cuộc gọi cho từng từ mà bạn đang kiểm tra. Bạn có thể chỉ cần lưu lại kết quả của cuộc gọi:

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

Một tối ưu hóa khác sẽ được đề xuất bởi Jeff Yates. Ví dụ.bằng cách sử dụng một mô hình duy nhất:

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

Answer 2

Cụm từ thông dụng có thể được tối ưu hóa một chút khi bạn chỉ muốn đối sánh với một chuỗi cố định các chuỗi không đổi. Thay vì một số kết quả phù hợp, ví dụ: chống lại "mùa đông", "giành chiến thắng" hoặc "wombat", bạn có thể chỉ phù hợp với "w(in(ter)?|ombat)", ví dụ (sách của Jeffrey Friedl có thể cung cấp cho bạn rất nhiều ý tưởng như thế này). Loại tối ưu hóa này cũng được tích hợp vào một số chương trình, đặc biệt là các emacs ('regexp-opt'). Tôi không quá quen thuộc với .NET, nhưng tôi giả định ai đó đã lập trình chức năng tương tự - google cho "tối ưu hóa regexp".

Answer 3

Tôi không nghĩ đây là công việc cho cụm từ thông dụng. Bạn có thể nên tìm kiếm từng từ tin nhắn một cách tốt hơn và kiểm tra từng từ trong danh sách từ của bạn. Với cách tiếp cận bạn có, bạn đang tìm kiếm mỗi thông điệp n lần trong đó n là số từ bạn muốn tìm - không có gì lạ khi phải mất một lúc.

Answer 4

có một điều bạn có thể dễ dàng làm là trận đấu agaist tất cả các từ trong một đi bằng cách xây dựng một biểu hiện như:

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

Sau đó, bạn có thể biên dịch trước mẫu và sử dụng lại nó để tra cứu tất cả các lần xuất hiện cho mỗi email (không chắc chắn cách bạn thực hiện việc này với API .Net, nhưng phải có cách).

Một điều khác thay vì sử dụng cờ ignorecase, nếu bạn chuyển đổi mọi thứ thành chữ thường, điều đó có thể giúp bạn tăng tốc độ nhỏ (cần phải cấu hình nó khi phụ thuộc vào triển khai thực hiện). Đừng quên làm nóng CLR khi bạn cấu hình.

Answer 5

Phần lớn thời gian có các kết quả phù hợp với mẫu không thành công, do đó bạn muốn giảm thiểu lỗi.

Nếu từ khóa tìm kiếm không thường xuyên, bạn có thể kiểm tra tất cả chúng cùng một lúc (với regexp \b(aaa|bbb|ccc|....)\b), sau đó bạn loại trừ các email không khớp. Người có ít nhất một trận đấu, bạn thực hiện tìm kiếm kỹ lưỡng.

Answer 6

Nếu biểu thức thường xuyên thực sự là cổ chai, và thậm chí tối ưu hóa nó (bằng cách kết hợp các từ tìm kiếm để một expression) không giúp đỡ, xem xét sử dụng một mô hình đa thuật toán tìm kiếm, chẳng hạn như Wu-Manber.

I’ve posted a very simple implementation tại đây trên Stack Overflow. Nó được viết bằng C++ nhưng vì mã đơn giản nên dễ dàng dịch nó sang C#.

Lưu ý rằng điều này sẽ tìm các từ ở bất kỳ đâu, không chỉ ở ranh giới từ. Tuy nhiên, điều này có thể dễ dàng được kiểm tra sau bạn đã kiểm tra xem văn bản có chứa bất kỳ từ nào hay không; hoặc một lần nữa với một biểu thức chính quy (bây giờ bạn chỉ kiểm tra các email riêng lẻ - nhanh hơn nhiều) hoặc bằng tay bằng cách kiểm tra các ký tự trước và sau các lần truy cập riêng lẻ.

Answer 7

Nếu vấn đề của bạn là về tìm kiếm cho các hạng mục triển vọng chứa chuỗi nào đó, bạn sẽ nhận được một lợi ích từ việc sử dụng các cơ sở triển vọng tìm kiếm ...

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

Answer 8

Nếu tìm kiếm từ khóa của bạn là literals thẳng, tức là không chứa thêm các mẫu phù hợp với regex, thì phương pháp khác có thể phù hợp hơn. Ví dụ dưới đây là một phương pháp như vậy, mã này chỉ đi qua từng email một lần, mã của bạn đã đi qua từng thời gian email 290 (hai lần)

 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

Nếu bạn có thể sử dụng Net 3.5+ và LINQ bạn có thể làm một cái gì đó như điều này.

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

... tái sử dụng ví dụ regex ...

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

này có thể được nhanh hơn. Bạn có thể tận dụng các nhóm Regex như thế này:

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

Bằng cách này bạn chỉ sử dụng một cụm từ thông dụng. Và các chỉ số của nhóm nên tương quan với _keywordList của bạn bằng một bù đắp trong tổng số 1, vì thế mà dòng wordFound.Add(_keywordList[i-1]);

UPDATE:

Sau khi xem xét mã của tôi một lần nữa tôi chỉ nhận ra rằng việc đưa các trận đấu vào Groups là thực sự không cần thiết. Và các nhóm Regex có một số chi phí. Thay vào đó, bạn có thể xóa dấu ngoặc đơn khỏi mẫu và sau đó chỉ cần thêm các kết quả phù hợp vào danh sách wordFound. Điều này sẽ tạo ra hiệu ứng tương tự, nhưng nó sẽ nhanh hơn.

Nó muốn được một cái gì đó như thế này:

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