c - 如何找到两个单词相差多少距离>>有没有最短的方法

Question

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

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

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

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

Answer 1

我想这在一定程度上取决于单词的结构。例如，这个人改进了实现，基于他按顺序处理他的单词并且不重复计算公共前缀的事实。但是，如果你所有的 10,000 个单词都完全不同，那对你没有多大好处。它是用 python 编写的，因此移植到 C 可能需要一些工作。

还有一些自制算法（我的意思是没有关于它的官方论文），但这可能会奏效。

Answer 2

有两种常见的方法，我已经在博客中介绍了这两种方法。实现起来更简单的是BK-Trees - 一种树数据结构，它通过仅搜索树的相关部分来基于 levenshtein 距离加快查找速度。对于您的用例，它们可能已经足够了。

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