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

Question

我最近被授权开发一种检查数据库中重复客户记录的算法。 的DB布局是非常简单的：成千上万行与像全名，街道，城市，邮编，电话等领域...

首先给出一些背景：

我已经做了一些广泛的研究算法，并且已经决定每个字段都应该使用不同的算法在一定数量的 上进行加权，因为在所有情况下，并不是所有的字段性能都一样好。 例如，姓氏的权重因子为0.50。当我评价我选择哪些算法使用，他们的体重最终决定：
系数0.25：JaroWinkler
因子0.60：余弦2革兰氏相似
因子0.15：DamerauLevenshtein

一切运作良好，并稍微调整一下，我发现了很小的错误。 目前为止这么好。然而，正如你可以想象的那样，当处理数以万计的记录时，运行时间为O（n^2） - 或者实际上是E形式i = 0到i = n - 不是很有效。不用说，积极优化，使用针对速度，多线程等的编译器优化，只是简单的方法，因为真正的问题是复杂性。

从本质上讲，我正在寻找一种方式来预过滤可能的匹配，并在这现在所做的研究三天。 我发现了一些关于R-Trees，R * -Trees，KD-Trees，Eucledian向量，minhashing等的有价值的信息。然而，关于所有这些的大多数信息都是非常有学术价值的。我发现的最宝贵的资源是“挖掘海量数据集”，第3章

我们我真正的问题：

我读过所有这些信息，但我不知道如何把它全部一起。

我在想在树上或图形数据结构在那里我可以普京字符串某种索引，并说：“给我找都具有匹配> 0.20的概率”。 这个算法应该非常快。然后，当我得到一个潜在的（> 0.20）匹配列表时，我可以去比较几个项目与我的“昂贵”，但选择性算法。 这应该削减运行时间，我相信一个非常合理的价值。

我一直在试图寻找某种参考代码做什么，我想上面的事，但我似乎没有拿出比学术文章的任何其他。 我确实发现了“simstring”，它实际上是编译的，但似乎并没有很好地匹配7个测试记录。 任何人都可以指向正确的方向吗？当然一定有人以前碰到这个，发现一个解决方案...

非常感谢你提前！

P.S.我在C++中这样做，但在C＃/ C/Java/PHP中的任何示例都可以。

Answer 1

我ahve终于成功地通过执行以下操作实现预选： 1.使用特定客户记录的字段来构建2Grams 2.最小哈希的2Grams与6个最小哈希函数的家风到192位签名 3 。使用boost :: geometry库的rtree实现在签名上创建6维空间索引 4.为我正在比较的记录选择最近的k（我的情况30）记录，并在这些候选项上运行原始“昂贵的”比较 5.这降低了基于E的复杂性（I，I = N，I = 1）以大致30N + m，其中m是它需要建立索引的时间（几乎可以忽略，令人惊讶）。

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

Answer 2

截至本第一切，我会简单地选择足够接近相同的长度，他们可以在给定的概率内匹配到这些字符串。这不会很有选择性，但是（除非你指定相当宽松的公差）可能会很快消除相当大比例的不可能匹配非常。 （例如。，像Levenshtein这样的编辑度量将插入计为1次操作，如果您以5的字符串开始并且需要在5次操作中匹配，则可以在没有进一步检查的情况下删除超过10的所有字符串。

这是否将是足够的选择性的直来直去的昂贵相比是值得商榷的 - 显然这将取决于你对匹配的字符串的长度的变化。