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

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

在你的例子中(假设“manman”不在你的字典中,虽然它是一个词),“main”这个词比“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 在返回的节点上 搜索TST 以便产生以该前缀开头的所有单词。

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