关于算法：如何检测重复数据？

How to detect duplicate data?

我有一个简单的联系人数据库，但是用户输入重复数据时遇到了问题。我已经实现了简单的数据比较，但是不幸的是，输入的重复数据并不完全相同。例如，姓名拼写不正确，或者一个人将" Bill Smith"放进去，而另一个人将" William Smith"放进同一个人。

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

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"字段。重复输入姓氏和地址。完成此操作后，您应该能够检测到重复项而不会出现拼写错误。

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

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

逐个比较字段
计算匹配的内容(用于可能宽松的匹配定义，并可能对字段进行不同的加权)
存在任何人为干预的情况

使用现有数据库对阈值进行良好的初步猜测，并在积累经验时进行更正。

至少在一开始，您可能会偏向误报。

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

如果可以访问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

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

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

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

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

FullContact.com具有可以为您解决此问题的API，请在此处查看其文档：http://www.fullcontact.com/developer/docs/?category=name。

它们具有用于名称规范化(Bill into William)，名称推演器(用于原始文本)和名称相似性(比较两个名称)的API。

目前所有API都是免费的，这可能是入门的好方法。

对于那些在网上徘徊并最终到达这里的人，我建议您尝试使用我创建的名为Flookup的Google表格插件。
它特别适合使用名称，并且还具有其他一些很棒的功能，我将在下面进行描述：

假设您有一个姓名列表，有2个人称为"约翰·史密斯"。您可以使用Flookup中的rank参数来指示算法返回第一，第二，第三或第n个最佳匹配。如果您有其他信息可用于标识所需的" John Smith"，这将很有帮助。

假设您还有其他数据库/公寓号码列表。您可以通过键入以下内容来指定所需的" John Smith"：John Smith & Apartment A或John Smith & Apartment B作为查找参数，以帮助区分这两个名称。

我希望您发现Flookup和其他人一样有益。

您可能还希望研究概率匹配。

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

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

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