Aumento de Regex Efficiency

Question

Tengo aproximadamente 100 mil mensajes de correo de Outlook que tienen entre 500 y 600 caracteres por cuerpo. Tengo una lista de 580 palabras clave que deben buscar en cada cuerpo, luego anexar las palabras en la parte inferior.

Creo que he aumentado la eficacia de la mayoría de las funciones, pero aún lleva mucho tiempo. Incluso para 100 correos electrónicos, toma alrededor de 4 segundos.

Ejecuto dos funciones para cada lista de palabras clave (290 palabras clave en cada lista).

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

¿De todos modos puedo aumentar la eficacia de esta función?

La otra cosa que podría ser la hace lenta es que utilizo HTML agilidad Paquete para navegar a través de algunos nodos y sacar el cuerpo (nSearch.InnerHtml). La _keywordList es un elemento List, y no una matriz.

Answer 1

Supongo que la llamada COM nSearch.InnerHtml es bastante lenta y repite la llamada para cada palabra que está comprobando. Simplemente puede almacenar en caché el resultado de la llamada:

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

Otra optimización sería la sugerida por Jeff Yates. P.ej.mediante el uso de un único patrón:

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

Answer 2

Las expresiones regulares se pueden optimizar bastante cuando lo que desea es hacer coincidir con un conjunto fijo de cadenas constantes. En lugar de varias coincidencias, p. contra "invierno", "ganar" o "wombat", puede coincidir con "w(in(ter)?|ombat)", por ejemplo (el libro de Jeffrey Friedl puede darle muchas ideas como esta). Este tipo de optimización también está integrado en algunos programas, especialmente emacs ('regexp-opt'). No estoy muy familiarizado con .NET, pero supongo que alguien tiene una funcionalidad similar programada - google para "optimización de expresiones regulares".

Answer 3

No creo que este sea un trabajo para expresiones regulares. Puede que sea mejor buscar cada mensaje palabra por palabra y verificar cada palabra con su lista de palabras. Con el enfoque que tiene, está buscando cada mensaje n veces donde n es el número de palabras que desea encontrar, no es de extrañar que tarde un tiempo.

Answer 4

una cosa que fácilmente puede hacer es partido Agaist todas las palabras de una sola vez mediante la construcción de una expresión como:

\ b (?: Palabra1 | palabra2 | word3 | ....) \ b

Luego puede precompilar el patrón y reutilizarlo para buscar todas las ocurrencias de cada correo electrónico (no estoy seguro de cómo hacer esto con .Net API, pero debe haber una manera).

Otra cosa es que en lugar de usar el indicador ignorecase, si convierte todo a minúsculas, eso podría darle un pequeño aumento de velocidad (necesita perfilarlo ya que depende de la implementación). No olvide calentar el CLR cuando haga un perfil.

Answer 5

La mayoría de las veces proviene de las coincidencias que fallan, por lo que desea minimizar las fallas.

Si la palabra clave de búsqueda no es frecuente, puede probar todas al mismo tiempo (con regexp \b(aaa|bbb|ccc|....)\b), y luego excluirá los correos electrónicos sin coincidencias. El que tiene al menos una coincidencia, realiza una búsqueda exhaustiva.

Answer 6

Si la expresión regular es de hecho el cuello de la botella, e incluso optimizarlo (mediante la concatenación de las palabras de búsqueda a uno expresión) no ayuda, considere el uso de un multi-patrón algoritmo de búsqueda, como Wu-Manber.

I’ve posted a very simple implementation aquí en Desbordamiento de pila. Está escrito en C++ pero dado que el código es directo, debería ser fácil traducirlo a C#.

Observe que esto encontrará las palabras en cualquier parte, no solo en los límites de las palabras. Sin embargo, esto se puede probar fácilmente después de ha comprobado si el texto contiene alguna palabra; ya sea una vez más con una expresión regular (ahora solo prueba correos electrónicos individuales, mucho más rápido) o manualmente, marcando los caracteres antes y después de las visitas individuales.

Answer 7

Si su problema es sobre la búsqueda de elementos de Outlook que contienen cierta cadena, debe obtener una ganancia por el uso de servicios de búsqueda perspectivas ...

véase: http://msdn.microsoft.com/en-us/library/bb644806.aspx

Answer 8

Si la búsqueda de palabras clave es literales rectas, es decir, no contiene más coincidencias de patrón de expresiones regex, entonces otro método puede ser más apropiado. El código siguiente muestra uno de tales métodos, este código sólo pasa por cada correo electrónico una vez, su código fue a través de correo electrónico cada vez que 290 (dos veces)

 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 puede utilizar .Net 3.5 + y LINQ que podría hacer algo como esta.

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

... reutilizado ejemplo de expresiones regulares ...

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

Este puede ser más rápido. Puede aprovechar Grupos expresiones regulares como esto:

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 esta manera sólo está utilizando una expresión regular. Y los índices de los grupos deben correlacionar con su _keywordList por un desplazamiento de 1, por lo tanto, la línea wordFound.Add(_keywordList[i-1]);

ACTUALIZACIÓN:

Después de buscar en mi código de nuevo me he dado cuenta de que al poner los partidos en grupos es realmente innecesario. Y los grupos Regex tienen algunos gastos generales. En su lugar, puede eliminar los paréntesis del patrón y luego simplemente agregar las coincidencias a la lista de palabras completas. Esto produciría el mismo efecto, pero sería más rápido.

que sería algo como esto:

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