我有一张Java地图。我想将源字符串与地图中的所有项目进行比较，并根据levenshtein比率算法返回最佳匹配。我想知道对列表中的每个元素执行此检查的最佳方法是什么。

谢谢，马特

解决方案

由于levenshtein比率取决于来源和目标，因此每个来源字符串的值都会变化。除非很有可能在后续搜索中重复源字符串，否则只需迭代map元素即可。如果速度确实是一个问题，请确保我们使用的是最新的Java编译器并使用优化选项。

当然，如果我们还没有这样做，请使用现成的优化Levenshtein实现，例如commons-lang StringUtils中的实现。

如果遍历所有地图元素的开销太大，则可以考虑使用k-gram索引。

仅使用按顺序测试它们的幼稚方法，就无法使用标准Map获得比O(n)更好的性能。

不过，还有很多更有效的方法可以做到这一点。其中之一称为bk树。基本上，我们将构造一棵n路树，其边缘由节点之间的levenshtein距离确定。然后，我们可以利用三角形不等式来大规模削减我们必须搜索的节点。对于短距离，这是非常有效的。这是我前一段时间写的一篇博客文章，详细描述了该文章。只需做一些额外的工作，我们就可以查询最近的邻居，而不必重复查询距离1、2等。