我需要写一个返回最接近的匹配基于用户输入的姓名和地址的联系人的算法。这两者都是令人不安的，因为有这么多的方法输入公司名称和地址，例如：加权搜索算法找到像联系人
Company A, 123 Any Street Suite 200, Anytown, AK 99012
Comp. A, 123 Any St., Suite 200, Anytown, AK 99012
CA, 123 Any Street Ste 200, Anytown, AK 99012
我已经看过这样的名称的Levenshtein距离，但似乎并没有很大的工具，因为它们可以缩写名称。我正在寻找可能的最多信息匹配的东西。
我最初的尝试是首先以邮政编码的前5位数字限制结果，然后尝试根据其他信息过滤到一个结果，但必须有一个更加标准的方法来完成此操作。我在.NET中工作，但会查看您可以提供的任何代码，以了解如何完成此操作。
我并不确切，现在这是如何实现的，但所有主要的快递公司（联邦快递，美国邮政，UPS）似乎对他们的数据库相匹配的地址，你输入和其转化为规范化形式的一种方式。正如我在多个网站上看到过这种情况（亚马逊想到的），我假设这个功能有一个API，但我不知道在哪里寻找它，以及它是否适合您的目的。
虽然只是一个想法。
编辑：我发现USPS API
我认为基于邮政编码滤波首先是最简单的，因为发现它是相当明确的。从那里你可以提取城市和街道。我不知道如何去查找名称，但如果您已经有（名称，地址）对的数据库是可行的，它似乎与地址匹配。
敦& Bradstreet的做到这一点。他们要收钱，因为这真的很难。没有“标准”解决方案。这在D & B这样的服务或自己推出的服务之间通常是一个痛苦的选择。
其实，这听起来像一个*有趣*的问题...所以我会去与后来:-) – 2009-01-28 01:14:19
作为一个开始，我可能会做一个词索引搜索。这将意味着两个阶段：
离线阶段：通过生成的关键字的所有地址的索引。例如，“公司”，“A”和“123”都将成为您在上面提供的地址的关键字。你可以做一些词干，这意味着像“街道”这样的词你也可以在它的索引中加入一个词“st”。
在线阶段：用户给你的搜索查询。将搜索查询分解为所有关键字，并查找数据库中每个关键字的所有可能匹配项。计算每个地址上匹配关键字的数量。然后根据匹配关键字的数量对结果进行排序。如果没有太多匹配，这应该能够很快完成，因为它只是一些排序列表合并和增量，最后是一种排序。
鉴于您知道您的问题的领域，您可以专门化该算法以使用关于该领域的知识 - 例如前面提到的邮政编码过滤。
也只是为了让我能够为您提供更好的答案，您是否使用SQL数据库？我问，因为我会这样做的方式是将关键字索引存储在SQL数据库中，然后通过关键字进行搜索的SQL查询变得非常容易，因为数据库完成所有工作。
也许不是仅将Levenshtein用于名称，而是与联系人的整个字符串表示形式一起使用时可能会有用。例如，你的第一个例子到第二个例子的距离是7到9。考虑到字符串长度为54,50和45，这似乎是一个相对有用和相当简单的相似性度量。
这是我会做的。我不知道算法，所以我只是使用有意义的东西。
我假设这个人会提供姓名，街道地址，城市名称，州名称和邮政编码。
如果邮政编码提供了9个数字，或者有一个连字符，我会将其分成5个数字。我将在数据库中搜索具有该邮政编码的所有地址。[查询1] 然后，我将比较州数字与数据库中的状态字母。如果不匹配，那么我会告诉用户。城市名称也一样。
据我所知，街道名称并不是数字，只有街道上的房子里有数字。此外，房屋编号通常在一开始，除非是房屋或套房编号。
所以我会做正则表达式来搜索数字和旁边的下一个空格或逗号。然后找到没有句点（。）或以逗号结尾的第一个单词的位置。我有街道名称的一部分，所以我可以对之前获取的行进行比较，或者我将更改查询以使街道名称LIKE％streetName％。
我猜数据库有一个块的房子的开始号码和结束号码。我会检查那条街，看看提供的街道号是否在那条街上。 现在，您将知道要显示的正确数据，并且可以在不同的表格中查找哪个名称与该门牌号码相关联。我不知道你为什么要比较它。如果您想查找地址未提供的人，则仅用于名称比较。你可以在这里查看比较字符串的方法Similar String algorithm
如果你可以可靠地找出每个地址的一般结构（也许根据其他答案中的建议），最好的办法是通过USPS认证的（含义：结果可靠，准确，并符合联邦标准）地址验证服务。
@RyanDelucchi，它是一个有趣的问题，但只有一次，你已经解决了它。因此，@SteveBering，我会建议您提交您的联系人列表a list processing service，根据美国邮政的指导方针，将根据地址标记重复。
由于我在地址验证领域工作，我会建议SmartyStreets（我工作），因为它会为您的特定需求提供最大价值 - 但是，有几个CASS认证的供应商基本上可以做类似的事情。
我已经使用地址规范化，Metaphone和Levenshtein距离的组合解决了这个问题。您需要将名称与地址分开，因为它们具有不同的特征。以下是您需要执行的步骤：
1）使用（邮政编码的前六个字符）缩小您的匹配列表。基本上你需要计算两个琴弦的Levenshtein距离，并选择最长距离为1或2的琴弦。如果您确实需要加快搜索速度，您可以预先计算邮政编码表及其“Levenshtein邻居”表。
http://en.wikipedia.org/wiki/Levenshtein_distance
2）转换所有地址缩写使用从USPS官方前缀和后缀缩写表的标准格式。这将有助于确保您的结果，为下一步更均匀：
https://www.usps.com/send/official-abbreviations.htm
3）转换地址使用Methaphone算法的短代码。这将消除最常见的拼写错误。只要确保您的实现可以消除所有非单词字符，通过数字完整和处理多个字（确保每个字由一个空格隔开）：
http://en.wikipedia.org/wiki/Metaphone
4）一旦你的Methaphone结果比较使用Levenshtein距离的地址字符串。通过将结果除以较长字符串中的字符数来计算更改分数的百分比。
5）重复步骤3和4，但现在使用名称而不是地址。
6）使用以下公式计算每个条目的分数：（地址权重*地址分数）+（名称权重*名称分数）。根据什么更重要选择你的权重。我以.9开头的地址（因为地址更具体）和.1的名称，但权重可能取决于您的应用程序。选择分数最低的条目。如果得分太高（超过.15，你可能会声明没有匹配）。
USPS API确实可以工作到一定程度，因为它是免费的，但缺乏重要功能，可能不会返回所有需要的信息来查找重复的联系人。我认为，CASS认证的USPS服务供应商（如SmartyStreets;请参阅我的补充答案）将提供更多SteveBering的需求。 – Matt 2012-01-05 19:30:43