我该如何构建一个匹配算法？

Question

我之前从未构建过匹配算法，也不知道该从哪里开始。这是我的基本设置和我所做的原因，如果我问的问题不正确，请随意纠正。

我有一个人名和唯一标识符的数据库。主要使用由内部生成和第三方生成的多个标识符、姓、名和出生日期。

每年我会多次收到来自第三方的列表，需要导入并与我的数据库中现有的人员相关联，但数据通常没有我的数据干净。标识符可能会更改，出生日期可能会有拼写错误，姓名可能会有拼写错误，姓氏可能会更改等。

每次导入可能会有20000条记录，即使准确率为99%，仍然需要手动匹配200条记录。我认为在将传入的人员与我的用户进行匹配时，应该达到99.9%的准确性。

那么，我如何制定一个算法来解决这个问题呢？

PS即使您没有确切的答案，但知道一些参考资料也会很有帮助。

PPS一些示例类似于m3rLinEz编写的内容：

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Original'

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84  '- Typo in birth date'
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Wrong ID'
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84  '- Hyphenated last name'
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84  '- Added middle initial'
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84  '- Probably someone else with same birthdate and same last name'

- Mikecancook

---

真正有帮助的是一个导入脚本，它会在每个不确定的情况下向您询问。比自己添加最后200条记录要快得多。 - Georg Schölly

你知道是否存在一对一的映射，或者可能存在一些记录完全不在你的数据库中，或者存在一些记录在你的数据库中但不在导入文件中吗？ - Mark Byers

我在下面进行了评论，但我确实有一个导入脚本，其中包含一堆情况语句，以尝试适应错误。最终结果是当没有精确匹配时，它们需要手动查看并匹配。我正在努力将其缩小到尽可能小的数量。 - Mikecancook

Answer 1

你可能会对 Levenshtein距离 感兴趣。

两个字符串之间的Levenshtein距离被定义为将一个字符串转换成另一个字符串所需的最小编辑次数，允许的编辑操作包括插入、删除或替换单个字符。它由Vladimir Levenshtein在1965年考虑而得名。1

可以比较每个字段并计算总距离。通过试错，可以发现适当的阈值来允许记录被解释为匹配。我自己没有执行过此操作，只是想到了这个想法：}

例如：

• 记录A - ID: 4831213321，姓名：Jane
• 记录B - ID: 431213321，姓名：Jann
• 记录C - ID: 4831211021，姓名：John

A和B之间的距离将低于A和C / B和C之间的距离，这表示更好的匹配。

- Gant

Answer 2

说到这种事情，不要重复造轮子。如果你非得自己做的话，Levehstein距离可能是你最好的选择，但除此之外，也可以研究一下已有的解决方案，这些解决方案能够进行数据库查询和模糊搜索。它们比你做的时间长，所以可能效果也更好。

祝你好运！

- Trevoke

Answer 3

如果你正在处理这种规模的数据集和导入不同资源，那么你可能想要考虑使用身份管理解决方案。我最熟悉的是Sun Identity Manager，但它可能过于复杂了。不过还是值得去研究一下。

- Jon

Answer 4

如果你从第三方获取的数据是一致的（每次都是相同的格式），我建议为每个提供数据的第三方创建一个表。然后每次将新的数据导入到同一个表中。我知道有一种方法可以使用SQL语句基于每个表中的共同列连接这两个表。这样，您就可以执行SQL查询并从多个表中获取数据，但使其看起来像来自一个单一的统一表。类似地，可以找到添加的记录，在两个表中没有匹配项，然后手动配对。这样，您可以将“干净”的数据与从第三方获取的垃圾数据分开。如果您想要真正的导入，那么您可以使用该连接表创建包含所有数据的第三个表。

- mjh2007

---

不幸的是，这种情况每年都不一致。这是州/政府数据，似乎他们每年都会更改格式。 - Mikecancook

你可以为每一年的数据使用不同的表格，但这样很快就会变得烦人。 - mjh2007

你是在处理所有记录的匹配问题还是只是想找到一种匹配非完全匹配的方法？ - mjh2007

我正在更新一个5年前开发的导入工具。目前它是一个case语句，试图进行精确匹配，但当无法匹配时，必须手动匹配。当需要查看几百个时，这是耗时的。 - Mikecancook

Answer 5

我会先处理容易匹配的近乎100%确定匹配的数据，然后再处理需要修复的200条名单。

对于剩余的行，您可以使用贝叶斯定理的简化版本。

对于每个未匹配的行，根据数据集包含某些以一定概率发生的更改的假设，计算它与数据集中每一行匹配的可能性。例如，一个人姓氏更改的概率是0.1％（也可能取决于性别），名字更改的概率为0.01％，可能有一个拼写错误的概率为0.2％（使用Levenshtein距离来计算拼写错误数量）。其他字段也以一定的概率发生更改。对于每行数据，考虑到所有更改的字段，计算其匹配的可能性。然后选择最有可能匹配的那个。

例如，一行记录只有一个字段有小错误，但其他字段都相等的概率是0.2%，而在许多字段上不同的行可能只有0.0000001%的概率。因此，您应该选择有小错误的那一行记录。

- Mark Byers

Answer 6

正则表达式是您所需要的，为什么要重复造轮子呢？

- Greg

---

我不同意正则表达式是一个自动问题，但我同意在这种情况下正则表达式并不是答案。 - Aaron