0

我最近的任务是开发一种算法来检查数据库中的重复客户记录。DB 布局非常简单：数以万计的行，包含 FullName、Street、City、ZIP、Phone 等字段。

先说一点背景：

我对算法进行了一些广泛的研究，并决定每个领域都应该使用不同的算法进行一定程度的权衡，因为并非所有领域在所有情况下都表现得一样好。例如，姓氏的权重因子为 0.50。当我评估时，我会选择要使用的算法以及它们对最终决定的影响：
因子 0.25：JaroWinkler
因子 0.60：余弦 2-Gram 相似
因子 0.15：DamerauLevenshtein

一切运行良好，稍加调整后，我检测到的积极因素几乎没有错误。到现在为止还挺好。但是，正如您可以想象的那样，在处理数万条记录时，运行时间为 O(n^2) - 或者实际上是 E 从 i=0 到 i=n - 并不是很有效。不用说，积极优化，使用编译器优化速度，多线程等，只是创可贴，因为真正的问题是复杂性。

本质上，我正在寻找一种预先过滤潜在匹配的方法，并且现在已经对此进行了三天的研究。我发现了一些关于 R-Trees、R*-Trees、KD-Trees、欧几里德向量、minhashing 等的有价值的信息。然而，关于所有这些的大多数信息都是相当学术性的。我发现的最有价值的资源是“挖掘海量数据集”，第 3 章。

现在到我真正的问题：

我已经阅读了所有这些信息，但我不确定如何将它们放在一起。

我正在考虑在树或图形数据结构中进行某种索引，我可以在其中输入一个字符串并说“找到所有匹配概率> 0.20的人”。这个算法应该非常快。然后，当我得到一个潜在的（>0.20）匹配列表时，我可以去比较几个项目和我的“昂贵”但有选择性的算法。我认为这应该将运行时间减少到一个非常合理的值。

我一直在尝试找到某种参考代码来做我想做的上面的事情，但除了学术文章之外，我似乎没有想出任何东西。我确实找到了实际编译的“simstring”，但似乎与 7 条测试记录不太匹配。有人能指出我正确的方向吗？肯定有人以前遇到过这个问题并找到了解决方案......

非常感谢您！

PS 我在 C++ 中执行此操作，但 C#/C/Java/PHP 中的任何示例都可以。

4

2 回答 2

1

作为第一个切入点，我只需选择那些足够接近相同长度的字符串，它们可以在给定的概率内匹配。这不会是非常有选择性的，但是（除非您指定非常宽松的公差）可能会很快消除相当大比例的不可能匹配。（例如，使用像 Levenshtein 这样的编辑度量将插入计为 1 次操作，如果您从长度为 5 的字符串开始并且需要在 5 次操作中匹配，那么您可以消除所有超过 10 的字符串而无需进一步检查）。

这是否具有足够的选择性以直接进行昂贵的比较是值得商榷的——显然这将取决于您匹配的字符串长度的可变性。

于 2013-02-20T00:04:03.120 回答
1

我终于通过执行以下操作成功实现了预选： 1. 使用客户记录的某些字段来构造 2Grams 2. 将具有 6 个 minhash 函数家族的 2Grams Minhash 到 192 位签名 3. 使用 boost::geometry库的 rtree 实现，以在签名上创建 6 维空间索引 4. 为我正在比较的记录选择最近的 k（我的情况是 30）记录，并在这些候选者上运行原始的“昂贵”比较 5。这减少了复杂度从 E(i,i=n,i=1) 到大约 30n + m，其中 m 是构建索引所需的时间（几乎可以忽略不计，令人惊讶）。

我现在可以在 60 秒内以高精度运行 15,000 次比较，这是在单线程测试中。多线程到 4 或 8 个内核，这将运行得更快。

于 2013-02-22T15:45:55.060 回答