Augmentation de l'efficacité de Regex

Question

J'ai environ 100k éléments de courrier Outlook qui ont environ 500-600 caractères par corps. J'ai une liste de 580 mots-clés qui doivent chercher dans chaque corps, puis ajouter les mots en bas.

Je crois que j'ai augmenté l'efficacité de la majorité de la fonction, mais cela prend encore beaucoup de temps. Même pour 100 courriels, cela prend environ 4 secondes.

Je cours deux fonctions pour chaque liste de mots-clés (290 mots-clés chaque liste).

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

Y at-il de toute façon je peux augmenter l'efficacité de cette fonction?

L'autre chose qui pourrait ralentir est que j'utilise HTML Agility Pack pour naviguer à travers certains nœuds et retirer le corps (nSearch.InnerHtml). Le _keywordList est un élément de la liste, et non un tableau.

Answer 1

Je suppose que l'appel COM nSearch.InnerHtml est assez lent et vous répétez l'appel pour chaque mot que vous vérifiez. Vous pouvez simplement mettre en cache le résultat de l'appel:

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

Une autre optimisation serait celle proposée par Jeff Yates. Par exemple.en utilisant un seul motif:

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

Answer 2

Les expressions régulières peuvent être optimisées un peu lorsque vous souhaitez simplement faire correspondre un ensemble fixe de chaînes constantes. Au lieu de plusieurs correspondances, par ex. contre "winter", "win" ou "wombat", vous pouvez simplement faire correspondre "w(in(ter)?|ombat)", par exemple (le livre de Jeffrey Friedl peut vous donner beaucoup d'idées comme ça). Ce type d'optimisation est également intégré dans certains programmes, notamment emacs ('regexp-opt'). Je ne suis pas trop familier avec .NET, mais je suppose que quelqu'un a programmé des fonctionnalités similaires - google pour "l'optimisation regexp".

Answer 3

Je ne pense pas que ce soit un travail pour les expressions régulières. Vous feriez peut-être mieux de chercher chaque mot mot par mot et de vérifier chaque mot par rapport à votre liste de mots. Avec l'approche que vous avez, vous recherchez chaque fois n fois où n est le nombre de mots que vous voulez trouver - il n'est pas étonnant que cela prenne un certain temps.

Answer 4

une chose que vous pouvez facilement faire est correspondance agaist tous les mots en une seule fois en construisant une expression comme:

\ b (: mot1 | mot2 | mot3 | ....) \ b

Ensuite, vous pouvez précompiler le modèle et le réutiliser pour rechercher toutes les occurrences de chaque e-mail (ne savez pas comment vous faites cela avec l'API .Net, mais il doit y avoir un moyen). Une autre chose est qu'au lieu d'utiliser le drapeau ignorecase, si vous convertissez tout en minuscules, cela pourrait vous donner un petit coup de pouce de vitesse (besoin de le profiler en fonction de l'implémentation). N'oubliez pas de réchauffer le CLR lorsque vous profilez.

Answer 5

La plupart du temps, les correspondances de formulaire échouent, ce qui vous permet de minimiser les échecs.

Si les mots clés de recherche ne sont pas fréquents, vous pouvez tous les tester en même temps (avec l'expression regexp \b(aaa|bbb|ccc|....)\b), puis vous excluez les e-mails sans correspondance. Celui qui a au moins un match, vous faites une recherche approfondie.

Answer 6

Si l'expression régulière est en effet le col de la bouteille, et même l'optimiser (en enchaînant les mots de recherche pour une expression) ne fonctionne pas, envisager d'utiliser un multi-modèle algorithme de recherche, tel que Wu-Manber.

I’ve posted a very simple implementation ici sur Stack Overflow. Il est écrit en C++ mais comme le code est simple, il devrait être facile de le traduire en C#.

Notez que cela trouvera les mots n'importe où, pas seulement aux limites de mots. Cependant, cela peut être facilement testé après vous avez vérifié si le texte contient des mots; soit encore une fois avec une expression régulière (maintenant vous ne testez que des emails individuels - beaucoup plus rapidement) ou manuellement en vérifiant les caractères avant et après les hits individuels.

Answer 7

Si votre problème est sur la recherche d'éléments Outlook contenant certaines chaînes, vous devriez obtenir un gain d'utiliser des installations de recherche de perspectives ...

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

Answer 8

Si votre recherche par mot clé est littéraux droite, c'est-à-dire ne contiennent pas d'autres correspondances de motifs regex, alors une autre méthode peut être plus appropriée. Le code suivant illustre une telle méthode, ce code ne va que dans chaque e-mail une fois, votre code est passé par e-mail à chaque fois 290 (deux fois)

 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

Si vous pouvez utiliser .Net 3.5+ et LINQ vous pourriez faire quelque chose comme ce.

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

... réutilisé par exemple ... 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

Ce peut être plus rapide. Vous pouvez tirer parti des groupes Regex comme ceci:

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

De cette façon, vous n'utilisez qu'une seule expression régulière. Et les indices des groupes devraient correspondre avec votre _keywordList par un décalage de 1, d'où la ligne wordFound.Add(_keywordList[i-1]);

MISE À JOUR:

Après avoir regardé mon code à nouveau, je viens de réaliser que mettre les matchs en groupes est vraiment inutile. Et les groupes Regex ont des frais généraux. Au lieu de cela, vous pouvez supprimer les parenthèses du modèle, puis ajouter simplement les correspondances elles-mêmes à la liste wordFound. Cela produirait le même effet, mais ce serait plus rapide.

Ce serait quelque chose comme ceci:

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