Повышение эффективности регулярных выражений

Question

У меня есть около 100 тысяч почтовых отправлений, которые имеют около 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 Agility Pack для навигации по некоторым узлам и извлечения тела (nSearch.InnerHtml). _KeywordList - это элемент списка, а не массив.

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

Другая оптимизация была бы предложена Джеффом Йейтсом. Например. используя один шаблон:

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

Answer 2

Чаще всего происходит совпадение форм, поэтому вы хотите минимизировать сбои.

Если ключевое слово для поиска встречается не часто, вы можете проверить все из них одновременно (с помощью regexp \b(aaa|bbb|ccc|....)\b), а затем исключить электронные письма без совпадений. Тот, у которого есть хотя бы одно совпадение, вы делаете тщательный поиск.

Answer 3

Я не думаю, что это работа для регулярных выражений. Возможно, вам лучше будет искать каждое слово за словом и сверять каждое слово с вашим списком слов. При таком подходе вы просматриваете каждое сообщение n раз, где n - это количество слов, которое вы хотите найти - неудивительно, что это занимает некоторое время.

Answer 4

Это может быть быстрее. Вы можете использовать Regex Groups следующим образом:

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

Таким образом, вы используете только одно регулярное выражение. И индексы групп должны коррелировать с вашим _keywordList со смещением 1, поэтому строка wordFound.Add(_keywordList[i-1]);

UPDATE:

После того, как я снова посмотрел свой код, я просто понял, что помещать совпадения в группы действительно не нужно. И у Regex Groups есть некоторые накладные расходы. Вместо этого вы можете удалить скобки из шаблона, а затем просто добавить сами совпадения в список 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;
}    

Answer 5

одна вещь, которую вы можете легко сделать, это сопоставить слова со всеми словами за один раз, создав выражение вроде:

\ б (?: Word1 | word2 | word3 | ....) \ б

Затем вы можете предварительно скомпилировать шаблон и повторно использовать его для поиска всех случаев для каждого электронного письма (не уверен, как вы это делаете с .Net API, но должен быть способ).

Другое дело, вместо использования флага ignorecase, если вы преобразуете все в строчные буквы, это может дать вам небольшой прирост скорости (необходимо профилировать его, поскольку это зависит от реализации). Не забывайте прогревать CLR при профиле.

Answer 6

Если вы можете использовать .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 7

Если ваш поиск по ключевым словам является прямым литералом, то есть не содержит дальнейших совпадений с регулярным выражением, тогда другой метод может быть более подходящим. Следующий код демонстрирует один такой метод, этот код проходит через каждое письмо один раз, ваш код проходил через каждое письмо 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 8

Если ваша проблема связана с поиском элементов внешнего вида, содержащих определенную строку, вы должны получить выгоду от использования средств поиска внешнего вида ...

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

Answer 9

Если регулярное выражение действительно является узким местом, и даже его оптимизация (путем объединения поисковых слов в одно выражение) не помогает, рассмотрите возможность использования алгоритма многошагового поиска, такого как Wu -Manber.

Я опубликовал очень простую реализацию здесь, в Переполнении стека. Он написан на C ++, но поскольку код прост, его легко перевести на C #.

Обратите внимание, что слова будут найдены где угодно , а не только на границах слов. Однако это легко проверить после того, как вы проверили, содержит ли текст какие-либо слова; либо снова с помощью регулярного выражения (теперь вы проверяете только отдельные электронные письма - намного быстрее), либо вручную, проверяя символы до и после отдельных обращений.

Answer 10

Регулярные выражения можно немного оптимизировать, если вы просто хотите сопоставить их с фиксированным набором константных строк. Вместо нескольких матчей, например против «зима», «победа» или «вомбат», например, вы можете просто сопоставить с "w(in(ter)?|ombat)" (книга Джеффри Фридла может дать вам множество таких идей). Этот вид оптимизации также встроен в некоторые программы, в частности, в emacs ('regexp-opt'). Я не слишком знаком с .NET, но я предполагаю, что кто-то запрограммировал аналогичные функции - Google для "оптимизации регулярных выражений".