类似于一组字符串的字符串

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-distance算法的工作实现，但是使用它从每个集合中查找相似的字符串需要遍历两个字符串集合进行比较，从而导致O(n^2)算法。即使在中等大小的集合中，这种运行速度也是不可接受的。

我还尝试了使用shingling和Jaccard系数的clustering algorithm。不幸的是，这也是在O(n^2)中运行的，即使使用位级优化，最终也会太慢。

有没有人知道更有效的算法(比O(n^2)更快)，或者更好的是，已经用C#编写的库，可以实现这一点？

Answer 1

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

这是样本数据，但都是干净的。这不是我会使用Levenstien处理的数据。被牵连的人与公司的距离比与公司的距离更近。E不能很好地与Enrique匹配。

Levenshtein-distance擅长捕捉关键输入错误。

它对于匹配OCR也很好。

如果你有干净的数据，我会使用词干分析和其他自定义规则。

Porter词干分析器可用于C#，如果您有干净的数据

例如。

删除。和其他标点符号

删除停用词(the)

词干

解析每个列表一次，并为每个唯一的词干分配一个int值

在int上进行匹配

仍然是N^2，但现在N1速度更快

你可以添加一个大写字母来匹配以大写字母开头的单词，从而得到部分分数

还需要考虑字数

匹配3的两组5比匹配4的两组10的得分更高

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

不确定您是否可以退出N^2。

但我建议你看看N1。

Lucene是一个具有短语匹配的库，但它并不是真正为批处理而设置的。

使用多次使用的意图创建索引，因此索引搜索速度在索引创建时间内得到优化。

Answer 2

在给定的示例中，至少有一个单词总是匹配的。一种可能的方法是使用多映射(一种能够为每个键存储多个条目的字典)或Dictionary<TKey,List<TVlaue>>。第一个集合中的每个字符串将被拆分成单个单词。这些单词将用作multimap中的关键字，整个字符串将存储为值。

现在，您可以将第二个集合中的字符串拆分为单个单词，并对每个单词执行O(1)查找，即对所有单词执行O(N)查找。这将产生第一个原始结果，其中每个匹配项至少包含一个匹配词。最后，您必须通过应用其他规则(如搜索首字母或缩略词)来优化此原始结果。

Answer 3

这个问题被称为“字符串相似性连接”，最近在研究界得到了很多研究。我们在C++中发布了一个名为Flamingo的源代码包，它实现了这样一个算法http://flamingo.ics.uci.edu/releases/4.1/src/partenum/。如果你的数据集对于一台机器来说太大，我们在http://asterix.ics.uci.edu/fuzzyjoin/上也有一个基于Hadoop的实现。