问题 c＃中字符串比较的更快算法
我有两个句子需要相互比较。
最后的结果是一个句子在另一个句子中包含多少百分比，我的问题是我有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％单词匹配的记录。
我希望我现在很清楚。
7464
2017-11-23 12:06
起源
答案:
我不是C＃程序员，但这里有一些一般提示：
- 将浮点运算移出循环。您应该能够计算匹配的字符并稍后进行除法。
- 由于数据是静态的，您应该能够在单独的执行线程中运行每个“long”循环。我会为你的每个“10”句子生成一个单独的线程并并行运行它们。
- 您可能想要删除对此的调用
split 如果你可以的话。基本上，删除任何额外的内存分配。
最后的想法是获取算法书或谷歌的文本处理算法。这个问题听起来像是一遍又一遍地解决了。可能有一些东西 AOCP v3 解决了这个问题。您还可以分析代码（不确定可用的分析器类型），但这可能不会产生实质性的改进。
6
2017-11-23 12:19
你看过了吗？ 相交 方法作为替代方案。我不知道它的性能，但看起来它可能会起作用
2
2017-11-23 12:15
就个人而言，我会避免创建两个数组;内存分配会扼杀性能。
试着看看 string.IndexOf 函数用于查找两个字符串中下一个空格的位置，从前一个空格位置中减去该空格以计算字长。如果两个长度相等则使用 string.Compare 看两个子串是否相等。这将避免内存分配，并且只迭代字符串一次，因此应该更快。
另外，正如其他人所提到的，一定要看看使用Parallel扩展。
2
2017-11-23 12:44
这是一种不同的方法。我猜测当你将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
0
2017-11-23 13:10
尝试这个。
在执行任何比较之前，预处理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)。
0
2017-11-23 12:44
由于数据在数据库中，您是否可以在数据库中完成工作？
将句子分成对句子行的单词。
加入你的话来对抗破碎的话语。这应该允许您查看哪些句子具有匹配的单词。
如果然后按句子ID对它们进行分组和求和，则应该得到指定句子中与存储句子匹配的单词总和。
我希望事先粉碎你的数据。将它们用作主句表的索引。
0
2017-11-23 14:56
相交示例
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());
}
然后循环遍历你所有的100.000个字符串 Parallel.For。
PS。我认为你将不得不做下去并删除 .， , 等等从字符串中获得更正确的比例。
DS。
0
2017-11-23 12:44
如果先拆分10条记录，那么你会在许多较大的字符串中找到少量的字符串。这似乎很合适 http://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_finite_set_of_patterns
和 Aho-Corasick算法 可能适合你
记录有多长？
编辑：
这是一个不必要的switcharound - 你的比较是对称的wrt firstArray和secondArray
if (firstArray.Length > secondArray.Length)
{
string[] tempArray = firstArray;
firstArray = secondArray;
secondArray = tempArray;
}
相反，用。替换返回
返回findLongest？ value：（firstArray.Length> secondArray.Length）？ value / secondArray.length：value / firstArray.Length）;
只有更可读的东西:)
问题更新后更新
所以你可以预处理100,000（例如哈希单词）？每天只需10-20次更改，这样可以很容易地保持预处理数据的最新状态。
你肯定需要做一些使用100,000的相对静态性质的东西。即使您每天只进行一次预处理，您也可以对所有最后几天的记录进行比较，然后对上次预处理运行后添加的其他任何记录使用当前的慢速方法。根据你的说法，最多可以有10-20个
我认为无论是散列的想法，还是从语料库中构建一个Aho-Comisack特里，都会让你更快地搜索。
0
2017-11-23 12:11