algorithm - 使用三元搜索树的拼写检查器

Question

我使用三元搜索树 (TST) 制作了一个拼写检查器。谁能告诉我如何在 TST 中找到下一个可能的单词？

例如：如果我想在拼写检查器中搜索“Manly”这个词，并且 TST 中不存在这个词，那么它会输出类似这样的近词：

你的意思是：“男人”“芒果”。

这是实现三元搜索树的代码。任何机构都可以修改以找到最接近的单词。 http://www.geeksforgeeks.org/ternary-search-tree/

score 0 · Accepted Answer

您可以尝试使用通配符。例如，用通配符替换搜索词中的某个字母，然后将该词拆分为两个子字符串并将它们插入 TST。然后搜索所有模式，而不仅仅是完全匹配。它通过创建字典单词的每个前缀来工作。但我建议尝试使用 TST 的 aho-corasick 算法。

score 0 · Accepted Answer

拼写检查器可能希望找到与目标词最近的匹配，而不是恰好具有相同前缀的词。TST 擅长查找前缀，但如果您想查找相似的单词，它们对您的帮助不大。

在您的示例中（假设“manly”不在您的字典中，尽管它是一个单词），建议“主要”比“芒果”更有可能，但从最长的扫描开始不会找到它匹配前缀。

但是，如果您希望从最长匹配前缀开始扫描：

1) 修改 searchTST 使其返回 a struct Node*，并将最后一个 else 子句替换为：

else if (*(word+1) == '\0')
  return root;
else {
  struct Node* child = searchTST(root->eq, word+1);
  return child ? child : root;
}

2)searchTST现在将向目标返回最长匹配前缀的根。调用者必须检查是否设置了返回的节点isEndOfString标志。

traverseTST3）您可以在返回的节点上使用类似的东西searchTST来生成以该前缀开头的所有单词。

2 回答 2