什么是寻找最接近单词的最佳算法？

Question

5

最佳的最近单词算法是什么。

给定可能的单词字典，输入单词的前几个字符可能是错误的。

- Avinash

2

为什么只有第一个字符可能是错误的？ - Leonid

3

你能先给出“最近”一词的定义吗？ - FrustratedWithFormsDesigner

我的意思是，前几个字符可能是错误的。 - Avinash

2

最接近的单词将是输入和可能正确单词之间编辑距离最小的单词。 - Avinash

2

所以你的意思不是第一个字符可能错误，而是中间或末尾的字符也可能错误，除非你有一些特殊的编辑距离定义... - ESRogs

显示剩余3条评论

3个回答

4

有一些工具，例如HunSpell（开源拼写检查器，广泛包括OpenOffice），它们从多个角度解决了这个问题。用于确定单词之间距离的一个广泛使用的标准是Levenshtein距离，该标准也在HunSpell中使用。

- Leonid

3

您可以使用 BLAST，并修改其使用字典中的单词作为离散单元，这使得匹配过程更具体，不像长的DNA字符串。

BLAST已经内置了编辑距离的概念。

或者，您可以使用后缀树（Dan Gusfeld在基本字符串匹配算法方面有一本优秀的书），并将编辑距离的想法简化。

- venky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Johnson · Accepted Answer

一种选择是使用BK树-请参阅我的博客文章这里。另一个更快但更复杂的选择是Levenshtein自动机，我也写了一篇关于它的文章，这里。