拼写检查器如何工作？

Question

我需要在C中实现拼写检查.基本上,我需要所有标准操作......我需要能够拼写检查一个文本块,提出单词建议并动态地向索引添加新单词.

我有点喜欢自己写这个,所以我真的不知道从哪里开始.

Answer 1

阅读Tree Traversal.基本概念如下:

1. 将字典文件读入内存(此文件包含给定语言可能/通用的正确拼写单词的完整列表).您可以在线下载免费的字典文件.一个例子是在java.sun.com
2. 将此字典文件解析为搜索树,以使实际文本搜索尽可能高效.我不会描述这种类型的树结构的所有脏细节,但树将由节点组成,这些节点具有(最多)26个到子节点的链接(每个字母一个),加上一个标志来表示或者不是当前节点是有效单词的结尾.
3. 遍历文档中的所有单词,并针对搜索树检查每个单词.如果到达树中的节点,其中单词中的下一个字母不是当前节点的有效子节点,则该单词不在字典中.此外,如果到达单词的末尾,并且未在该节点上设置"有效词尾"标志,则该单词不在词典中.
4. 如果在词典中找不到单词,请通知用户.在这个阶段,你也可以建议替代拼写,但这有点复杂.您将不得不循环遍历单词中的每个字符,替换替换字符并针对搜索树测试每个字符.可能有更高效的算法来查找推荐的单词,但我不知道它们是什么.

一个很短的例子:

字典:

apex apple任命

树:( *表示有效的词尾) 更新:感谢Curt Sampson指出这个数据结构叫做Patricia Tree

A -> P -> E -> X*
      \\-> P -> L -> E*
           \\-> O -> I -> N -> T* -> E -> D*

文献:

苹果appint猿

结果:

• "苹果"将在树中找到,因此被认为是正确的.
• "appint"将被标记为不正确.遍历树,您将跟随A -> P -> P,但第二个P没有I子节点,因此搜索失败.
• "ape"也将失败,因为E节点in A -> P -> E没有设置"有效字结束"标志.

编辑:有关拼写建议的更多详细信息,请查看Levenshtein Distance,它测量将一个字符串转换为另一个字符串时必须进行的最小更改次数.最好的建议是与错误拼写单词具有最小Levenshtein距离的字典单词.

Answer 2

鉴于您不知道从哪里开始，我建议使用现有的解决方案。例如，请参见aspell （GLPL 许可）。如果您确实必须自己实施，请告诉我们原因。