近似字符串匹配概率的预选

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

先介绍一下背景:

我对算法做了一些广泛的研究,并决定每个领域都应该有一定的权重 使用不同的算法,因为并非所有算法在所有情况下都能同样出色地执行。 例如,LastName的权重因子为0.50。当我评估时,我会选择使用哪些算法,以及它们对最终决策的影响:
系数0.25:JaroWinkler
系数0.60:余弦2-克相似性
系数0.15:DamerauLevenstein

一切都很好,只要稍微调整一下,我就能检测到积极的一面,几乎没有错误。 到现在为止,一直都还不错。然而,正如你可以想象的那样,当处理数以万计的记录时,运行时O(n^2)——或者实际上E的形式i=0到i=n——不是很有效。 不用说,激进的优化,使用编译器优化速度、多线程等,只是权宜之计,因为真正的问题是复杂性。

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

现在是我真正的问题:

我已经阅读了所有这些信息,但我不确定如何将其整合在一起。

我在考虑在树或图数据结构中进行某种索引,在那里我可以输入一个字符串,然后说“找到所有匹配概率>0.20的字符串”。 这个算法应该非常快。然后,当我得到一个潜在(>0.20)匹配的列表时,我可以去用我的“昂贵”但有选择性的算法比较这几个项目。 我认为,这应该会将运行时间缩短到一个非常合理的值。

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

提前非常感谢!

附言:我是用C++做这件事的,但用C#/C/Java/PHP做任何示例都可以。