ms-word - microsoft word 中的单词建议如何猜测替代方案？

Question

用ms word看这个例子；我故意拼错了“完成”这个词来告诉你我的意思；

我想知道 ms word 如何选择与我输入的最相似的词（我的意思是算法）

这不是拼写检查的情况，而是找到最相似的单词（如图中的结果）

我想实现一个算法，以便我可以找到与用户已经键入的最相似的单词；

Answer 1

这称为列文斯泰因距离。它衡量两个随机单词在删除、插入和替换单个字符方面的差异程度。

（为了提高效率，您可能不想将任何单词与整个单词列表进行比较。您可能希望使用一种或多种其他方法进行一些快速剔除，以剔除可能的替代方案。）

（编辑）

那很有趣！:) 只是为了看看它是如何工作的，我使用 OSX 的默认words列表和Wikibooks上算法的 C 版本在 C 中实现了它。以下是“赞美”的前 10 首热门歌曲：

'complment' -> LD=compliment(1)
   LD=complement(1)
   LD=component(2)
   LD=couplement(2)
   LD=comment(2)
   LD=compellent(2)
   LD=competent(2)
   LD=compilement(2)
   LD=complacent(2)
   LD=complaint(2)

比较例程保留了一个小的“迄今为止最好的”匹配数组，当数组填满时，最高值被丢弃。针对列表中的每个单词（235,886 个单词）的完整距离计算耗时 0.370 秒。

我添加了一个快速剔除例程，检查输入中的每个字母是否在比较字中至少出现一次（一个简单的位测试），以及依次检查每个其他字母。这将时间缩短到三分之一：0.150 秒。

我尝试了一些随机的其他词（未显示所有可能的解决方案）：

'unforutntately' -> LD=unfortunately(3) LD=infortunately(4) LD=fortunately(5)
'abcacadabra' -> LD=abracadabra(1) LD=barracuda(7)
'athtahn' -> LD=Ethan(3) LD=thawn(3) LD=Pathan(3) LD=attaghan(3)
'jongware' ->

...最后一个根本没有匹配。只有在删除我的 One-Character-Off 例程后，我才得到

'jongware' -> LD=nonglare(2)
   LD=congiary(3)
   LD=henware(3)
   LD=hogward(3)
   LD=honeyware(3)

那好吧。

（进一步编辑）既然你写了

这不是拼写检查的情况，而是找到最相似的单词

我用正确拼写的“compliment”再次运行它。这是结果：

'compliment' -> LD=compliment(0)
  LD=complement(1)
  LD=complimenter(2)
  LD=compliant(2)
  LD=complicant(2)
  LD=complacent(2)
  LD=couplement(2)

如您所见，第一个值是“0”——完全匹配——其他词是“相似的”。