如何构建匹配算法？

Question

我以前从未构建过匹配算法,也不知道从哪里开始.所以这是我的基本设置以及我为什么这样做.如果我没有问正确的问题,请随意纠正我.

我有一个人名的名字和唯一标识符的数据库.几个生成的标识符(内部生成的和一些第三方),姓氏,名字和出生日期是我将使用的主要标识符.

我全年多次收到第三方列表,该列表需要导入并绑定到我数据库中的现有人员,但数据从未像我的一样干净.ID可能会更改,出生日期可能会出现拼写错误,姓名可能会出现拼写错误,姓氏可能会更改,等等.

每次导入都可能有20,000条记录,所以即使它准确率为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'

Answer 1

您可能对Levenshtein distance感兴趣.

两个字符串之间的Levenshtein距离定义为将一个字符串转换为另一个字符串所需的最小编辑数,允许的编辑操作是单个字符的插入,删除或替换.这是弗拉基米尔·莱文斯坦,谁在1965年考虑过这个距离后命名1

可以比较每个字段并计算总距离.通过反复试验,您可以发现适当的阈值,以便将记录解释为匹配.我自己没有实现这个,只是想到了这个想法:}

例如:

• 记录A - ID:4831213321,姓名:简
• 记录B - ID:431213321,姓名:Jann
• 记录C - ID:4831211021,姓名:John

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