我需要编写一个算法，根据用户输入的姓名和地址返回与联系人最接近的匹配项。这两者都令人不安，因为输入公司名称和地址的方法有很多，例如：
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 中工作，但会查看您可以提供的任何代码，以了解如何完成此操作。
我现在不知道这是如何完成的，但所有主要的快递公司（FedEx、USPS、UPS）似乎都有办法将您输入的地址与他们的数据库进行匹配，并将其转换为规范化的形式。正如我在多个网站上看到的那样（想到亚马逊），我假设此功能有一个 API，但我不知道在哪里寻找它以及它是否适合您的目的。
不过只是一个想法。
编辑：我找到了USPS API
我通过地址规范化、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) 一旦您获得了使用 Levenshtein 距离比较地址字符串的 Methaphone 结果。通过将结果除以较长字符串中的字符数来计算更改分数的百分比。
5) 重复步骤 3 和 4，但现在使用名称而不是地址。
6) 使用以下公式计算每个条目的得分：（地址权重 * 地址得分）+（姓名权重 * 姓名得分）。根据更重要的因素选择您的权重。我会以 0.9 作为地址（因为地址更具体）和 0.1 作为名称开始，但权重可能取决于您的应用程序。选择得分最低的条目。如果分数太高（比如超过 0.15，您可以声明没有匹配项）。
这就是我会做的。我不知道算法，所以我只使用有意义的。
我假设此人会提供姓名、街道地址、城市名称、州名和邮政编码。
如果邮政编码以 9 个数字提供，或者有连字符，我会将其删除为 5 个数字。我将在数据库中搜索具有该邮政编码的所有地址。[查询 1] 然后我会将状态字母与数据库中的字母进行比较。如果它不匹配，那么我会告诉用户。城市名称也是如此。
据我了解，街道名称不是数字，只有街道上的房子有数字。此外，门牌号通常在开头，除非它是门牌号或套房号。
所以我会做正则表达式来搜索数字和旁边的下一个空格或逗号。然后找到第一个没有句点（。）或以逗号结尾的单词的位置。我有部分街道名称，因此我可以与之前获取的行进行比较，或者我将更改查询以使用街道名称 LIKE %streetName%。
我猜数据库有一个街区的房子的开始号码和结束号码。我会检查该街道行，以查看提供的街道号码是否在该街道上。到目前为止，您将知道要显示的正确数据，并且可以在不同的表中查找与该门牌号相关联的名称。我不知道你为什么要比较它。如果您想查找未提供地址的人，则仅用于名称比较。您可以在此处查找比较字符串方式类似的字符串算法
我认为首先基于邮政编码进行过滤是最简单的，因为发现它是相当明确的。从那里你可能可以提取城市和街道。我不确定您将如何查找名称，但如果您已经有一个（名称，地址）对的数据库是可行的，那么它似乎与地址匹配。
邓白氏就是这样做的。他们收费，因为这真的很难。没有“标准”解决方案。在像 D&B 这样的服务或推出自己的服务之间，这主要是一个痛苦的选择。
首先，我可能会进行单词索引搜索。这将意味着两个阶段：
离线阶段：通过关键字生成所有地址的索引。例如，“公司”、“A”和“123”都将成为您上面提供的地址的关键字。你可以做一些词干提取，这意味着对于像“street”这样的词，你还要在它的索引中添加一个词“st”。
在线阶段：用户给你一个搜索查询。将搜索查询分解为所有关键字，并在数据库中找到每个关键字的所有可能匹配项。统计每个地址上匹配关键字的数量。然后按匹配关键字的数量对结果进行排序。如果没有太多匹配，这应该能够很快完成，因为它只是几个排序列表合并和递增，最后是排序。
鉴于您知道问题的领域，您可以专门使用有关该领域的知识的算法 - 例如前面提到的邮政编码过滤。
也只是为了让我能够为您提供更好的答案，您是否使用 SQL 数据库？我问是因为我这样做的方式是将关键字索引存储在 SQL 数据库中，然后按关键字搜索的 SQL 查询变得非常容易，因为数据库完成了所有工作。
也许与其仅将 Levenshtein 用作名称，不如将其与联系人的整个字符串表示形式一起使用时会很有用。例如，您的第一个示例到第二个示例的距离是 7，到第三个示例的距离是 9。考虑到字符串的长度为 54、50 和 45，这似乎是一个相对有用且非常简单的相似性度量。
如果您可以可靠地确定每个地址的一般结构（也许通过其他答案中的建议），您最好的选择是通过 USPS 认证运行数据（意思是：结果可靠、准确并符合联邦标准）地址验证服务。
@RyanDelucchi，这是一个有趣的问题，但只有在你解决了它之后。因此，@SteveBering，我建议将您的联系人列表提交给列表处理服务，该服务将根据 USPS 指南根据地址标记重复项。
由于我在地址验证领域工作，我建议 SmartyStreets（我工作），因为它会为您的特定需求提供最大的价值——但是，有一些 CASS 认证的供应商会做基本类似的事情。