c# - 类似于一组字符串的字符串

Question

我需要将一组字符串与另一组字符串进行比较，找出哪些字符串相似(模糊字符串匹配)。 例如:

{ "A.B. Mann Incorporated", "Mr. Enrique Bellini", "Park Management Systems" } 
and
{ "Park", "AB Mann Inc.", "E. Bellini" }

假设一个从零开始的索引，匹配将是 0-1、1-2、2-0。显然，在这类事情上没有任何算法是完美的。

我有一个 Levenshtein 距离算法的有效实现，但使用它从每个集合中查找相似的字符串需要循环遍历两组字符串来进行比较，从而产生 O(n^2) 算法。即使是中等大小的集合，它的运行速度也慢得令人无法接受。

我也试过 clustering algorithm使用叠瓦和 Jaccard 系数。不幸的是，这也在 O(n^2) 中运行，最终速度太慢，即使使用位级优化也是如此。

有谁知道一个更有效的算法(比 O(n^2) 更快)，或者更好的是，一个已经用 C# 编写的库来完成这个？

Answer 1

不是对 O(N^2) 的直接回答，而是对 N1 算法的评论。

那是样本数据，但都是干净的。那不是我会使用 Levenstien 的数据。 Incriminate 与 Incorporated 的距离比 Inc. E. 更接近 Enrique。

Levenshtein-distance 擅长捕捉关键输入错误。
它也适用于匹配 OCR。

如果您有干净的数据，我会使用词干提取和其他自定义规则。
Porter stemmer 可用于 C#，如果你有干净的数据
例如
消除 。和其他标点符号
删除停用词 (the)
干
解析每个列表一次并为每个唯一的词干分配一个 int 值
对 int
进行匹配 仍然是 N^2 但现在 N1 更快
你可以在一个大写字母中添加匹配以 cap 开头的单词得到部分分数
还需要考虑字数
两组 5 人匹配 3 应该比两组 10 人匹配 4 得分更高

我会为每个短语创建 Int 哈希集，然后相交并计数。

不确定你能不能从 N^2 中脱身。
但我建议你看看 N1。

Lucene 是一个短语匹配的库，但它并不是真正为批处理而设置的。
创建索引的目的是多次使用它，以便在索引创建时间上优化索引搜索速度。