如何找出这两个单词的distance>>不同有什么最短的方法吗？
我读过关于Levenshtein distance的文章，关于两个不同单词之间距离的计算。
我有一个源字符串，我必须将它与所有10,000个目标单词进行匹配。应该返回最接近的单词。
问题是我已经给出了一个10,000个目标词的列表，并且输入的源词也很大……那么，在这里应用什么最短且高效的算法。计算每个n的Levenshtein距离每个组合(蛮力逻辑)将非常耗时。
任何提示或想法都非常受欢迎。
回答 2
Stack Overflow用户
发布于 2011-04-03 18:33:27
我想这有点取决于单词的结构。例如，this guy improved the implementation基于这样一个事实，即他按顺序处理他的单词，并且不重复计算常见前缀。但是，如果你的10,000个单词都完全不同，那对你没有太大的好处。它是用python编写的，所以移植到C语言可能会涉及到一些工作。
也有一些homebrew algorithms (我的意思是没有关于它的官方论文)，但这可能会起到作用。
Stack Overflow用户
发布于 2011-04-04 08:18:14
有两种常见的方法，我已经在博客上介绍了这两种方法。更简单的实现是BK-Trees -一种树数据结构，通过只搜索树的相关部分来加速基于levenshtein距离的查找。对于您的用例来说，它们可能是完全足够的。
一种更复杂但更有效的方法是Levenshtein Automata。这是通过构造一个NFA来识别目标字符串的levenshtein距离x内的所有单词，然后以锁步方式迭代它和字典，有效地对它们执行合并连接。
https://stackoverflow.com/questions/5528909
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号