2

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

{ "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# 编写的库来完成这个？

4

3 回答 3

1

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

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

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

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

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

不确定您是否可以摆脱N ^ 2。
但我建议你看看N1。

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

于 2012-11-07T21:09:52.743 回答
0

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

于 2012-11-08T06:24:22.980 回答
0

在给定的例子中，至少有一个词总是匹配的。一种可能的方法是使用 multimap（一个能够为每个键存储多个条目的字典）或Dictionary<TKey,List<TVlaue>>. 第一组中的每个字符串都将被拆分为单个单词。这些词将用作多图中的键，整个字符串将作为值存储。

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

于 2012-11-07T21:26:57.910 回答