最先进的近似字符串匹配算法
Approximate string matching algorithms state-of-the-art
我寻求最先进的算法来近似字符串匹配。
你给我参考（文章，论文，...）？
谢谢
您可能想要了解 Levenshtein 距离。
您可能已经有了答案，但我想表达我对近似字符串匹配的观点，以便其他人受益。我是根据我致力于解决云服务问题以处理真正大规模需求的经验说的。
如果只是说近似字符串匹配算法，那么有很多。
其中很少有：
Jaro-Winkler、编辑距离（Levenshtein）、Jaccard 相似度、基于 Soundex/Phonetics 的算法等。
一个简单的谷歌搜索就会给我们所有的细节。
具有讽刺意味的是，它们在您尝试匹配两个给定的输入字符串时起作用。从理论上讲，并演示模糊或近似字符串匹配的工作方式。
然而，严重低估的一点是，我们如何在生产设置中使用它。在我认识的寻找近似字符串匹配算法的人中，并不是每个人都知道如何在生产环境中解决相同的问题。
假设我们有一个包含数百万个名字的列表，如果我们想使用上述标准算法之一针对列表中的所有条目搜索给定的输入名称，那将意味着灾难。
典型的编辑距离算法的时间复杂度为 O(N^2)，其中 N 是字符串中的字符数。要扫描大小为 M 的列表，复杂度为 O(M * N^2)。这将意味着非常高的硬件要求，而且无论您要堆叠多少 h/w，它都不会对您有利。
这是我们必须开始考虑其他方法的地方。
在生产环境中解决此类问题的一种常见方法是使用标准搜索引擎，例如 -
Apache Lucene。
Lucene 索引引擎索引参考数据（称为文档）并且可以针对引擎触发输入查询。返回的结果根据它们与输入的接近程度进行排名。
这与 google 搜索引擎的工作方式很接近。 Googles 对整个网络进行抓取和索引，但您应该有一个模仿 Google 所做的事情的微型系统。
这适用于大多数情况，包括名字、中间名和姓氏互换的复杂名称匹配。
您可以 select 根据 Lucene 发出的分数得出您的结果。
当您的角色成熟时，您将开始考虑使用托管解决方案，例如 Amazon Cloudsearch，它为您包装了 Solr 和 ElastiSearch。当然，它在底层使用 Lucene，并且由于用于索引的参考数据较大，因此您可以独立于索引的潜在大小。
我寻求最先进的算法来近似字符串匹配。 你给我参考（文章，论文，...）？ 谢谢
您可能想要了解 Levenshtein 距离。
您可能已经有了答案，但我想表达我对近似字符串匹配的观点，以便其他人受益。我是根据我致力于解决云服务问题以处理真正大规模需求的经验说的。
如果只是说近似字符串匹配算法，那么有很多。 其中很少有： Jaro-Winkler、编辑距离（Levenshtein）、Jaccard 相似度、基于 Soundex/Phonetics 的算法等。 一个简单的谷歌搜索就会给我们所有的细节。
具有讽刺意味的是，它们在您尝试匹配两个给定的输入字符串时起作用。从理论上讲，并演示模糊或近似字符串匹配的工作方式。
然而，严重低估的一点是，我们如何在生产设置中使用它。在我认识的寻找近似字符串匹配算法的人中，并不是每个人都知道如何在生产环境中解决相同的问题。
假设我们有一个包含数百万个名字的列表，如果我们想使用上述标准算法之一针对列表中的所有条目搜索给定的输入名称，那将意味着灾难。
典型的编辑距离算法的时间复杂度为 O(N^2)，其中 N 是字符串中的字符数。要扫描大小为 M 的列表，复杂度为 O(M * N^2)。这将意味着非常高的硬件要求，而且无论您要堆叠多少 h/w，它都不会对您有利。
这是我们必须开始考虑其他方法的地方。 在生产环境中解决此类问题的一种常见方法是使用标准搜索引擎，例如 - Apache Lucene。
Lucene 索引引擎索引参考数据（称为文档）并且可以针对引擎触发输入查询。返回的结果根据它们与输入的接近程度进行排名。 这与 google 搜索引擎的工作方式很接近。 Googles 对整个网络进行抓取和索引，但您应该有一个模仿 Google 所做的事情的微型系统。
这适用于大多数情况，包括名字、中间名和姓氏互换的复杂名称匹配。
您可以 select 根据 Lucene 发出的分数得出您的结果。
当您的角色成熟时，您将开始考虑使用托管解决方案，例如 Amazon Cloudsearch，它为您包装了 Solr 和 ElastiSearch。当然，它在底层使用 Lucene，并且由于用于索引的参考数据较大，因此您可以独立于索引的潜在大小。