我最近的任务是开发一种算法来检查数据库中的重复客户记录。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 中的任何示例都可以。