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