如何找到两个单词的距离有多远>>有没有最短的路数

Question

我已经阅读了有关计算两个不同单词之间距离的Levenshtein距离。

我有一个源字符串，我必须将它与所有10,000个目标字匹配。应该返回最接近的单词。

问题是我已经给出了10,000个目标词的列表，并且输入源词也是巨大的....那么在这里应用什么最短和高效的算法。 Levenshtein距离计算为每个组合（强力逻辑）将是非常耗时的。

任何提示或想法是最受欢迎的。

Answer 1

我猜这取决于字的结构。例如this guy improved the implementation基于他按顺序处理他的单词并且不重复对通用前缀的计算的事实。但是，如果你所有的10,000字都完全不同，那对你来说不会有多大的好处。它是用python编写的，因此可能需要一些工作才能移植到C上。

在那里也有一些homebrew algorithms（我的意思是没有官方的文章写它），但这可能会诀窍。

Answer 2

有两种常见的方法，我已经写了两篇文章。更简单的实现方法是BK-Trees - 一种树状数据结构，通过仅搜索树的相关部分来加速基于levenshtein距离的查找。它们可能对您的使用情况来说已经足够了。

更复杂但更有效的方法是Levenshtein Automata。这可以通过构建一个NFA来识别目标字符串的levenshtein距离x内的所有单词，然后以锁步方式遍历它和字典，从而有效地对它们执行合并连接。