我有一个简单的联系人数据库，但是用户输入重复数据时遇到了问题。我实现了一个简单的数据比较，但是不幸的是，输入的重复数据并不完全相同。例如，姓名拼写错误，或者同一个人将一个人放在"比尔·史密斯"中，另一个人将在"威廉·史密斯"中。

那么，是否存在某种算法可以给出一个条目与另一个条目的相似程度的百分比？

解决方案

回答

尽管我没有适合算法，但我的第一步是看一下输入新联系人所涉及的过程。也许用户没有一种简单的方法来找到他们想要的联系人。就像在Stack Overflow的新问题表格上一样，我们可以建议新联系人屏幕上已经存在的联系人。

回答

我想这个问题已经很好理解了，但是在我初读时发生的事情是：

• 逐个比较字段
• 计数匹配的内容(用于可能宽松的匹配定义，以及可能不同地权衡字段)
• 存在任何人为干预的情况，超过阈值的任何情况

使用我们现有的数据库可以很好地猜测阈值，并在积累经验时进行更正。

至少在一开始，我们可能更倾向于对误报采取相当强烈的偏见。

回答

我们可以将名称与Levenshtein距离进行比较。如果名称相同，则距离为0，否则由将一个字符串转换为另一个字符串所需的最少操作数确定。

回答

这可能相关也可能不相关，但是Soundex搜索可能会发现较小的拼写错误，例如，这将使我们可以将Britney Spears，Britanny Spares和Britny Spears视为重复项。

但是，昵称收缩很难视为重复，我怀疑这样做是否明智。肯定会有多个人，分别是比尔·史密斯(Bill Smith)和威廉·史密斯(William Smith)，我们必须使用Charles-> Chuck，Robert-> Bob等进行迭代。

同样，如果我们正在考虑使用穆斯林用户，那么问题会变得更加棘手(例如，穆斯林太多，被称为穆罕默德/穆罕默德)。

回答

如果可以访问SSIS，请检查Fuzzy分组和Fuzzy查找转换。

http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services

http://msdn.microsoft.com/en-us/library/ms137786.aspx

回答

我不确定它是否可以很好地解决名称与昵称的问题，但是在这种情况下，最常见的算法是编辑距离/ Levenshtein距离算法。基本上，这是将一个项目转换为另一个项目所需的字符更改，添加和删除的次数的计数。

对于名称，我不确定我们是否将通过纯算法方法获得良好的结果，真正需要的是海量数据。以Google拼写建议比普通桌面应用程序中的建议要好多少为例。这是因为Google可以处理数十亿个网络查询，并查看导致彼此查询的内容，实际点击的"意思"链接等。

有一些公司专门研究名称匹配问题(主要用于国家安全和欺诈应用程序)。我记得的是，"搜索软件美国"似乎已经被这些人收购了http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx，但是我怀疑这些解决方案中的任何一种都不会对于联系人应用程序来说太贵了。

回答

如果我们有一个包含字符串字段的大型数据库，则可以使用simhash算法非常快速地找到很多重复项。

回答

So is there some sort of algorithm
  that can give a percentage for how
  similar an entry is to another?

Soundex和Edit distances之类的算法(如上一篇文章中所建议)可以解决一些问题。但是，如果我们认真清理数据，这还不够。正如其他人所说，"比尔"听起来不像"威廉"。

我发现的最佳解决方案是使用归约算法和表将名称还原为其根名称。

在常规地址表中，添加名称的根版本，例如
人员(名字，RootFirstName，姓氏，Rootsurname...。)

现在，创建一个映射表。
FirstNameMappings(主密钥名，根名)

通过以下方式填充"映射表"：
将IGNORE(从Person中选择Firstname，选择" Undefined")插入FirstNameMappings

这将添加我们在人员表中拥有的所有名字以及RootName为" UNDEFINED"

现在，可悲的是，我们将必须遍历所有唯一的名字并将它们映射到RootName。例如，" Bill"，" Billl"和" Will"都应翻译为" William"
这非常耗时，但是如果数据质量对我们确实很重要，我认为这是最好的方法之一。

现在，使用新创建的映射表来更新Person表中的" Rootfirstname"字段。重复输入姓氏和地址。完成此操作后，我们应该能够检测到重复项而不会出现拼写错误。

回答

我们可能还想研究概率匹配。