c# - C#中查找关键字最快的算法

Question

您好，我正在尝试创建一种非常快速的算法来检测集合中的关键字或关键字列表。

在此之前，我已经阅读了很多 stackoverflow(和其他)帖子，但无法将性能提高到我期望的水平。

我当前的解决方案能够在 0.1825 毫秒内分析 200 个字符的输入 和 400 个列表的集合(在 1 毫秒内分析 5 个输入)，但这太长了，我希望将此性能提高至少 5 倍(这是我的要求)。

解决方案测试:

• 人工研究
• 高度复杂的正则表达式(组、反向引用...)
• 多次调用简单的正则表达式(以匹配每个关键字)
• 用于匹配输入关键字的简单正则表达式，后跟与跟踪关键字的交集(当前解决方案)
• 多线程(对性能有巨大影响 (*100)，所以我不确定这是否是解决此问题的最佳方案)

当前解决方案:

input (string) : 要解析和分析的字符串，以验证其中包含的关键字列表。示例:“世界您好!#piloupe 先生，您好吗？”。

tracks (string[]) :我们要匹配的字符串数组(空格表示 AND)。示例:“hello world”匹配包含“hello”和“world”的字符串，无论它们位于何处

keywordList (string[][]) :要从输入中匹配的字符串列表。示例:{{“你好”}，{“#piloupe”}，{“你好”，“世界”}}

uniqueKeywords (string[]) :表示关键字列表中所有唯一关键字的字符串数组。使用之前的关键字列表将是:{ "hello", "#piloupe", "world"}

所有这些先前的信息不需要任何性能改进，因为它们对任何输入只构建一次。

查找轨道算法:

// Store in the class performing the queries
readonly Regex _regexToGetAllInputWords = new Regex(@"\#\w+|\w+", RegexOptions.Compiled);

List<string> GetInputMatches(input)
{
    // Extract all the words from the input
    var inputWordsMatchCollection = _regexToGetAllInputWords.Matches(input.ToLower()).OfType<Match>().Select(x => x.Value).ToArray();

    // Get all the words from the input matching the tracked keywords
    var matchingKeywords = uniqueKeywords.Intersect(inputWordsMatchCollection).ToArray();

    List<string> result = new List<string>();

    // For all the tracks check whether they match
    for (int i = 0; i < tracksKeywords.Length; ++i)
    {
        bool trackIsMatching = true;

        // For all the keywords of the track check whether they exist
        for (int j = 0; j < tracksKeywords[i].Length && trackIsMatching; ++j)
        {
            trackIsMatching = matchingKeywords.Contains(tracksKeywords[i][j]);
        }

        if (trackIsMatching)
        {
            string keyword = tracks[i];
            result.Add(keyword);
        }
    }

    return result;
}

任何帮助将不胜感激。

Answer 1

简短的回答是解析每个单词，并将其存储到类似二叉树的集合中。 SortedList或 SortedDictionary 将是您的 friend 。

只需很少的代码，您就可以将单词添加到 SortedList，然后对该 SortedList 执行 .BinarySearch()。这是一个 O(log n) 实现，您应该能够在几次迭代中搜索数千或数百万个单词。使用 SortedList 时，性能问题将出现在对 SortedList 的插入上(因为它会在插入时进行排序)。但这是进行二分查找所必需的。

我不会为线程而烦恼，因为您需要不到 1 毫秒的结果。

长的答案是看像 Lucene 这样的东西，如果你正在做一个自动完成式的搜索，它会特别有用。 RavenDB 在幕后使用 Lucene，可以为您进行后台索引，它将在几毫秒内搜索数百万条记录。