C# 中字符串比较的更快算法

Question

我有两个句子需要相互比较。 最终结果是一个句子包含另一个句子的百分比，我的问题是我有 100.000 条记录需要与另外 10 条记录进行比较。 那是 1.000.000 次循环，在我的算法中非常慢。

这是我正在使用的算法：

private double BreakStringsAndCheck(string s1, string s2)
{
    if (s1 == null || s2 == null || s1.Length == 0 || s2.Length == 0)
        return (double)0;
    string[] firstArray = s1.Split(' ');
    string[] secondArray = s2.Split(' ');
    if (firstArray.Length > secondArray.Length)
    {
        string[] tempArray = firstArray;
        firstArray = secondArray;
        secondArray = tempArray;
    }
    double value = 0;
    for (int i = 0; i < firstArray.Length; i++)
        for (int j = 0; j < secondArray.Length; j++)
            value += firstArray[i] == secondArray[j] ? (double)100 : (double)0;
    return findLongest ? value : value / firstArray.Length;
}

这是一个小方法，但速度不是很快。根据我的测试，我可以在 1 秒内进行 40-60 次比较，这对于 1.000.000 次循环来说几乎需要 5 个小时。

有人能想到另一种比这更快的方法或逻辑吗？

更新：

我会尝试用更多细节来解释这个问题。 我有超过 100.000 条记录的数据库，每天我都会在该数据库中插入并比较 10-20 条新记录。 这些记录是 2 到 10 个单词的句子，我需要编写快速方法来将这些新记录与数据库中的记录进行比较，结果应该是一个句子包含另一个句子的单词量的百分比。

我需要单词匹配率超过 70% 的记录。

我希望我现在已经清楚了。

Answer 1

我不是 C# 程序员，但这里有一些一般性提示：

1. 将浮点运算移出循环。您应该能够计算匹配的字符并稍后进行除法。
2. 由于数据是静态的，您应该能够在单独的执行线程中运行每个“长”循环。我将为每个“10”句子生成一个单独的线程并并行运行它们。
3. 如果可以的话，您可能希望删除对 split 的调用。基本上，删除任何额外的内存分配。

最后的想法是找一本算法书或谷歌搜索文本处理算法。这个问题听起来像是已经被解决了一遍又一遍的问题。 AOCP v3 中可能有一些东西可以解决这个问题。您还可以分析代码（不确定可用的分析器类型），但这可能不会产生实质性的改进。

Answer 2

您是否看过 Intersect 方法作为替代方法。我不知道它的性能，但看起来它可能有用

Answer 3

就我个人而言，我会避免创建这两个数组；内存分配会降低性能。

尝试查看 string.IndexOf 函数来查找下一个空格的位置在这两个字符串中，从前一个空格位置中减去该值即可计算出单词长度。如果两个长度相等，则使用 string.Compare 来查看是否两个子串相等。这将避免内存分配，并且只迭代字符串一次，因此应该更快。

另外，正如其他人提到的，一定要考虑使用并行扩展。

Answer 4

这是一种不同的方法。我猜测，当您将 10 个句子与 100'000 个句子进行比较时，将会有大量单词没有匹配且 % = 0。不要总是执行 100'000 次比较，而是在 100'000 个句子中找到这些句子其中至少有一个单词匹配并且仅比较它们。

创建（一次）包含 100,000 个句子中所有单词的字典。

每个条目都是包含该单词的句子列表 L。

tobetested=empty
For each s in the 10 sentences
  for each word in s
    if dictionary.contains(word) then
      add members of L that aren't already there to tobetested
  next
  for each sentence to tobetested ' hopefully much less than 100'000
    compare using your algorithm
  next
next

Answer 5

试试这个。

在执行任何比较之前，请预处理 100,000 行。
100,000 行中的每个单词都将成为 Dictionary<> 对象中的键，值将是 id 列表（单词出现的每行的 id），例如

Dictionary<string, List<int>> allWords

当“搜索匹配项”时，您保留第二个字典，该字典以行 id 为键，它的值是您将递增的整数。例如，

Dictionary<int, int> matches

您将搜索字符串拆分为单词，并且对于每个单词的每个行 id，您递增该行 id 的值。

var searchWords = search.Split(" ");
foreach(var word in searchWord)
{
    foreach(var id in allWords[word])
        matches[id] += 1;
}
var bestRowId = (from m in matches orderby m.Value select m.Key).Last();

具有最大值的行 id 是最佳匹配。

预先构建字典需要一些时间（但我猜不会比单次比较多多少时间），但之后速度会快得令人眼花缭乱。

注意： 这里速度的关键是 Dictionary 将使用它存储的键的 HashCode，并且 .net 字符串哈希函数非常出色。

更新

如果此订单的预处理时间太长，那么您可以进行更轻松的预处理。
当您读取 100,000 行中的每一行时，将其拆分为单词，并对单词数组进行排序。然后在比较时，拆分字符串进行比较并对其进行排序。
然后，您的函数可以节省时间，因为它不会多次分割每个字符串，并且您的嵌套循环可以替换为 min(words1.length, Words2.length) 的循环。

Answer 6

既然数据都在数据库里，那能不能不在数据库里做这些工作呢？

根据句子行将句子分解为单词。

将你的话语与破碎的话语结合起来。这应该可以让您看到哪些句子有匹配的单词。

如果您然后按句子 id 对它们进行分组和求和，您应该获得指定句子中与存储的句子匹配的单词的总和。

我会考虑提前粉碎你的数据。使用它们作为主句表的索引。

Answer 7

相交示例

private double BreakStringsAndCheck(string s1, string s2)
{
    var split1 = s1.Split(' ');
    return (double)split1.Intersect(s2.Split(' ')).Count() / split1.Count() * 100.0;
}

我更愿意返回比率 0.4 而不是 40.0，因为：

var percent = BreakStringsAndCheck("Jan Banan går till GAIS.", "I Torsk på Tallin så var en annan Jan Banan med.");

我刚刚意识到您的算法总是将较短的字符串与较长的字符串进行比较。因此，即使输入参数像这样切换，您的算法也会返回 40.0

var percent = BreakStringsAndCheck("I Torsk på Tallin så var en annan Jan Banan med.", "Jan Banan går till GAIS.");

，但我的相交示例将返回 18.18。我觉得这更正确，但如果你真的想要你的方式，那么只需添加

if (s1.Length > s2.Length)
{
    var tmp = s2;
    s2 = s1;
    s1 = tmp;
}

到方法的开头即可。

预分割

var presplits = new List<string[]>() { s1.Split(' '), s2.Split(' '), s3.Split(' ') };

...

private static IEnumerable<double> StringsInString(IEnumerable<string[]> strings, string s2)
{
    return strings.Select(h => (double)h.Intersect(s2.Split(' ')).Count() / h.Count());
}

然后循环遍历 Parallel.For 中的所有 100.000 个字符串。

附言。我认为您必须小写并从字符串中删除 .、、 等以获得更正确的比率。
DS。

Answer 8

如果您首先拆分 10 条记录，那么您会在许多较大的字符串中找到少量的字符串。这似乎适合 http://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_finite_set_of_patterns

算法可能适合您

Aho- Corasick 记录？

编辑：

这是一个不必要的转换 - 您的比较是对称的 firstArray 和 secondaryArray

 if (firstArray.Length > secondArray.Length)
    {
        string[] tempArray = firstArray;
        firstArray = secondArray;
        secondArray = tempArray;
    }

相反，将 return 替换为

return findLongest ？值 : (firstArray.Length > secondaryArray.Length) ?值/secondArray.length : 值/firstArray.Length);

只有更具可读性的东西:)

问题更新后更新

所以你可以预处理100,000（例如散列单词）？每天只有 10-20 次更改，因此保持预处理数据最新很容易。

你肯定需要做一些利用 100,000 的相对静态特性的事情。即使您每天只进行一次预处理，您也可以与最近几天的所有记录进行比较，然后对自上次预处理运行以来添加的任何其他记录使用当前较慢的方法。根据你的说法，最多有 10-20 个，

我认为散列想法或从语料库构建 Aho-Comisack trie 会让你的搜索速度更快。