如何找到这两个词的差异距离>>有没有最短路径

Question

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

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

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

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

Answer 1

我想这取决于单词的结构.例如,这个人基于以下事实改进了实现:他按顺序处理他的单词并且不重复对公共前缀的计算.但是,如果你所有的10,000个单词完全不同,那对你来说就不会那么好.它是用python编写的,所以可能需要一些工作才能移植到C语言.

还有一些有点自制算法(我的意思是没有关于它的官方文件),但这可能会有所帮助.