2

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

在任何事情之前，我已经阅读了很多 stackoverflow（和其他）帖子，但无法将性能提高到我期望的水平。

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

解决方案测试：

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

当前解决方案：

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

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

keywordList (string[][]) : 从输入中匹配的字符串列表。示例：{ { "hello" }, { "#piloupe" }, { "hello", "world" } }

uniqueKeywords (string[]) ：表示keywordList的所有唯一关键字的字符串数组。使用前面的关键字列表：{ "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;
}

任何帮助将不胜感激。

4

3 回答 3

1

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

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

我不会打扰线程，因为您需要不到 1 毫秒的结果。

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

于 2013-09-17T02:26:16.790 回答
0

最终的解决方案是弹性二叉树数据结构。它在HAProxy中用于将规则与代理 HTTP 请求中的 URL 匹配（也用于许多其他目的）。
ebtree是从您的“关键字”模式构建的数据结构，它允许比 SortedList 或散列更快的匹配。比散列更快是可能的，因为散列读取输入字符串一次（或至少几个字符）以生成散列码，然后再次进行评估.Equals()。因此散列读取输入的所有字符 1 次以上。ebtree 最多读取所有字符一次并找到匹配项，或者如果没有匹配项，则在O(log(n))个字符之后告诉它n是模式的数量。
我不知道ebtree的现有 C# 实现，但如果有人接受它，肯定很多人会很高兴。

于 2013-10-03T16:16:26.800 回答
0

I would like to suggest using hash table. with hashing you can convert string text to integer representing the index of this string in hash table. It's much more faster than sequential search.

于 2013-09-16T15:48:56.853 回答