我读过 Levenshtein distance 关于计算两个不同单词之间的距离。
我有一个源字符串,我必须将它与所有 10,000 个目标词匹配。应返回最接近的单词。
问题是我已经给出了一个包含 10,000 个目标词的列表,输入的源词也很大....那么在这里应用什么最短和高效的算法。每 n 个组合的编辑距离计算(蛮力逻辑)将非常耗时。
欢迎任何提示或想法。
最佳答案
我想这在一定程度上取决于单词的结构。例如this guy improved the implementation基于这样一个事实,他按顺序处理他的单词并且不重复计算公共(public)前缀。但是,如果您的 10,000 个单词都完全不同,那对您没有多大好处。它是用 python 编写的,因此可能需要一些工作才能移植到 C。
还有一些有点homebrew algorithms在那里(我的意思是没有关于它的官方论文)但这可能会成功。
关于c - 如何找到两个单词相差多少距离>>有没有最短的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5528909/