24

我需要在 C 中实现一个拼写检查器。基本上，我需要所有标准操作......我需要能够对一段文本进行拼写检查，提出单词建议并动态地将新单词添加到索引中。

我有点想自己写这个，虽然我真的不知道从哪里开始。

4

7 回答 7

31

阅读树遍历。基本概念如下：

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

一个非常简短的例子：

字典：

apex 苹果任命

树：（*表示有效的词尾） 更新：感谢 Curt Sampson 指出这种数据结构称为Patricia 树

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

文档：

苹果appint猿

结果：

  • “apple”将在树中找到，因此它被认为是正确的。
  • “appint”将被标记为不正确。遍历树，你会跟着A -> P -> P，但是第二个P没有I子节点，所以搜索失败。
  • "ape" 也会失败，因为Ein 中的节点A -> P -> E没有设置 "valid end of word" 标志。

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

于 2008-12-06T21:35:10.420 回答
3

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

于 2008-12-06T20:58:34.017 回答
1

应该查看前缀和后缀。

突然 = 突然 + ly。

通过删除 ly's 你可以摆脱只存储根词。

同样preallocate = pre + allocate。

而lovely = love + ing + ly 会变得更复杂一些，因为ing的英语规则被调用了。

也有可能使用某种散列函数将根词映射到特定位是一个大位图，作为确定根词是否拼写正确的恒定时间方法。

通过尝试为拼写错误的单词提供可能正确拼写的替代列表，您可能会变得更加复杂。您可能会研究 soundex 算法以获得一些想法。

我建议用一小组单词进行原型设计。做大量测试，然后扩大规模。这是一个奇妙的教育问题。

于 2008-12-07T02:22:11.337 回答
0

将单词分成词根和后缀被称为“Porter Stemming Algorithm”，它是一种将英文词典放入极小的记忆的好方法。
它对 seach 也很有用，所以“拼写检查”也会找到“拼写检查”和“拼写检查”

于 2008-12-07T02:51:35.490 回答
0

我在课堂上做过

您应该考虑专门用于处理此问题的python Natural Language Toolkit NLTK 。

它还允许创建文本解释器，例如聊天机器人

于 2009-06-20T05:01:02.457 回答
0

Open Office Spell checker Hunspell 是一个很好的起点。这是主页： Sourceforge 的 Hunspell

于 2009-09-09T18:14:05.860 回答
0

E James 为如何判断一个词是否有效给出了一个很好的答案。这可能取决于拼写检查器如何确定可能的拼写错误。

一种这样的方法，我将使用的一种方法是Levenshteinn 字符串相似度，它查看必须在一个单词中添加、删除或交换多少个字母才能生成另一个单词。

如果你说拼写：Country as Contry。levenshtein 字符串相似度为 1，因为您只需添加 1 个字母即可将国家/地区转换为国家/地区。

然后，您可以遍历所有可能的正确拼写单词（只有 171,000 个英文单词，其中 3000 个占文本的 95%）。确定那些具有最低 levenshtein 字符串相似度值的词，然后返回与拼写错误的词最相似的前 X 个词。

有一个很棒的 python 包，叫做Fuzzy Wuzzy，它有效地实现了这一点，并根据这个公式在两个单词或句子之间生成 % 相似度。

于 2018-04-24T22:04:08.123 回答