我需要将一组字符串与另一组字符串进行比较,并找出哪些字符串相似(模糊字符串匹配)。例如:
{ "A.B. Mann Incorporated", "Mr. Enrique Bellini", "Park Management Systems" }
and
{ "Park", "AB Mann Inc.", "E. Bellini" }
假设一个从零开始的索引,匹配将是 0-1、1-2、2-0。显然,在这类事情上没有算法是完美的。
我有一个 Levenshtein-distance 算法的工作实现,但是使用它从每个集合中查找相似的字符串需要循环遍历两组字符串来进行比较,从而产生 O(n^2) 算法。即使使用适度大小的集合,这也会运行得慢得令人无法接受。
我还尝试了一种使用 shingling 和 Jaccard 系数的聚类算法。不幸的是,这也是在 O(n^2) 中运行的,即使进行位级优化,最终也会变得太慢。
有谁知道更有效的算法(比 O(n^2) 更快),或者更好的是,已经用 C# 编写的库来完成这个?