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

Question

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

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

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

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

Answer 1

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

在您的示例中(假设"manly“不在您的字典中，尽管它是一个单词)，这个建议”主要“比"mango”更有可能，但它不会通过以最长匹配前缀开始的扫描来找到。

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

1)修改searchTST，使其返回一个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标志。

3)您可以在由traverseTST返回的节点上使用类似searchTST的内容，以便生成以该前缀开头的所有单词。

Answer 2

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