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. 由于数据是静态的,因此您应该能够在单独的执行线程中运行每个"long"循环.我会为你的每个"10"句子产生一个单独的线程并且并行运行它们.
3. 如果可以,您可能想要删除呼叫split.基本上,删除任何额外的内存分配.

最后的想法是获取算法书或谷歌的文本处理算法.这个问题听起来像是一遍又一遍地解决了.AOCP v3中可能有一些东西可以解决这个问题.您还可以分析代码(不确定可用的分析器类型),但这可能不会产生实质性的改进.

Answer 2

如果您首先拆分 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;
    }

相反，将返回替换为

返回找到最长的？值 : (firstArray.Length > secondaryArray.Length) ? 值/secondArray.length : 值/firstArray.Length);

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

问题更新后更新

那么您可以预处理这 100,000 个（例如对单词进行哈希处理）吗？每天只有 10-20 次更改，因此保持预处理数据最新很容易。

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

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