logo标签列表

提高正则表达式效率

c#regex
6

我有大约10万个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 Agility Pack来遍历一些节点并提取正文（nSearch.InnerHtml）。_keywordList是一个列表项，而不是一个数组。

10
别猜测，用分析工具来解决问题。 - Paolo
我有dotTrace，但它不能在Outlook Addins上工作。 - cam
根据我的经验，调用COM API通常是瓶颈（在您的情况下检索100k项），您唯一能做的就是尝试减少这些调用的数量。但正如Paolo所说，最好使用分析器或者如果您的分析器不支持插件，则使用StopWatch类。 - Dirk Vollmar
据我所知，Outlook插件不允许多线程。那计时器难道不需要多线程支持吗？ - cam
1
你是如何获取这个包含10万个Outlook项目的列表的？遍历Outlook项目可能是速度缓慢的原因之一。 - Mesh
显示剩余2条评论
10个回答
7

我认为 nSearch.InnerHtml 这个 COM 调用非常缓慢，而且你需要为每个单词都重复进行调用。你可以简单地缓存调用的结果：

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)";
简化模式：@"(\b(?:" + string.Join("|", _keywordList) + @")\b)" - Konrad Rudolph
@Konrad Rudolph：噢，没错，这样更好。 - Dirk Vollmar
2

我认为这不是正则表达式可以解决的问题。你最好逐个单词搜索每个消息，并将每个单词与你的单词列表进行比较。采用你的方法，你会对每个消息进行 n 次搜索，其中 n 是你想要查找的单词数 - 难怪会花费一些时间。

是的，这就是我想做的。我认为这是最有效/准确的方法。 - cam
2
大部分时间都来自于匹配失败，因此您希望最小化失败率。如果搜索关键字不频繁，您可以同时测试所有关键字（使用正则表达式 \b(aaa|bbb|ccc|....)\b），然后排除没有匹配的电子邮件。至少有一个匹配项的电子邮件，您可以进行彻底搜索。
1

这可能会更快。您可以像这样利用正则表达式组：

    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]);

更新：

再次查看我的代码后，我才意识到将匹配项放入组中实际上是不必要的。并且正则表达式组存在一些额外开销。相反，您可以从模式中删除括号，然后将匹配本身简单地添加到 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;
}
谢谢Steve，这就是我想说的。如果您不介意，能否也让我们知道使用ignorecase标志和事先将正则表达式和文本转换为小写字母进行匹配而不区分大小写之间是否存在性能差异（当您旋转测量循环时，应该删除正则表达式的创建，但保留innerHtml.toLowerCase()）？ - ddimitrov
1

你可以轻松地通过构建一个表达式来一次性匹配所有单词，例如：

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

然后，您可以预编译模式并重复使用它来查找每个电子邮件的所有出现次数（不确定如何在 .Net API 中执行此操作，但一定有方法）。

另一件事是，如果您将所有内容转换为小写字母而不是使用 ignorecase 标志，那可能会给您带来一些速度提升（需要对其进行分析，因为它取决于实现）。别忘了在分析时热身 CLR。

如果将这些单词组合成一个正则表达式，就需要为每个单词使用分组，否则无法跟踪匹配的内容。 - Jeff Yates
@Jeff - 我也是这么想的。但我刚刚意识到，当使用单词边界时，匹配项将始终是单词本身。因此，实际上您可以将每个匹配项的值简单地添加到wordFound列表中。请参见我的答案以获取我的实现。 - Steve Wortham
@Steve：好观点。你指出来后现在看起来很明显。谢谢。 - Jeff Yates
0
如果您的关键字搜索是直接文字，即不包含其他正则表达式模式匹配，则可能有更适合的方法。以下代码演示了一种这样的方法，该代码仅一次遍历每个电子邮件，而您的代码则需要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;
        }
0
如果您可以使用 .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
    }
}
这种方法的好处是，如果您只想要包含关键字列表中一个值的所有消息，您可以将.ToList()替换为.Any()，它会在第一次匹配后返回。 - Matthew Whited
您还可以考虑将IEnumerable <Regex>传递到扩展方法中，其中关键字已转换为正则表达式。然后，您就不需要为扫描的每个电子邮件重新生成值了。 - Matthew Whited
0

当您只想匹配一组固定字符串时，正则表达式可以进行相当大的优化。例如，您可以使用 "w(in(ter)?|ombat)" 进行匹配，而不是多次匹配 "winter"、"win" 或者 "wombat" 等。Jeffrey Friedl 的书籍也提供了许多类似这样的想法。此类优化也内置于一些程序中，特别是 Emacs（'regexp-opt'）。我对 .NET 不是太熟悉，但我认为某人已经编写了类似的功能——搜索“regexp optimization”即可。

为什么这个表达式比 winter|wombat|win 更高效？它们都应该被编译成大致相同的自动机（减去捕获组，这实际上使您的表达式更复杂）。我并不确定，不幸的是我找不到关于技术细节的好信息。你有什么好的来源吗？ - Konrad Rudolph
它并不能被证明比“winter|wombat|win”更好，它只是让你不必相信正则表达式编译器能够做好工作。但是它确实比运行N个单独的匹配要好，这就是原帖中的情况。 - Kilian Foth
0

如果正则表达式确实是瓶颈，即使通过将搜索词连接到一个表达式中进行优化也没有帮助，请考虑使用多模式搜索算法，例如Wu-Manber。

我在Stack Overflow上发布了一个非常简单的实现。它是用C++编写的，但由于代码很简单，因此将其转换为C#应该很容易。

请注意，这将在任何地方找到单词，而不仅仅是在单词边界处。但是，在检查文本是否包含任何单词之后，可以通过正则表达式（现在只测试单个电子邮件-速度更快）或手动检查单个命中之前和之后的字符来轻松测试。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接