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

Question

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

先介绍一下背景

我对算法做了一些广泛的研究，并决定每个领域都应该有一定的权重使用不同的算法，因为并非所有算法在所有情况下都表现得一样好。例如，LastName 的权重因子为 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、Eucledian vectors、minhashing 等的有值(value)的信息。然而，关于所有这些的大多数信息，嗯，相当学术。我找到的最有值(value)的资源是第 3 章“挖掘海量数据集”。

现在回答我真正的问题:

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

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

我一直在努力寻找某种引用代码来完成我上面想做的事情，但除了学术文章之外，我似乎没有想出任何其他东西。我确实找到了“simstring”，它实际上编译了，但似乎并没有很好地匹配 7 条测试记录..谁能指出我正确的方向？肯定有人以前遇到过这个问题并找到了解决方案......

非常感谢您!

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

Answer 1

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

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