使用三元搜索树的拼写检查器
Spell Checker using Ternary Search tree
我使用三元搜索树 (TST) 制作了一个拼写检查器。
谁能告诉我如何在 TST 中找到下一个可能的单词？
例如：如果我想在拼写检查器中搜索单词 "Manly" 并且如果该单词不存在于 TST 中，那么它会输出类似这样的单词：
你的意思是："Man" "Mango" .
下面是实现三元搜索树的代码。
任何机构都可以修改以找到最接近的单词。
http://www.geeksforgeeks.org/ternary-search-tree/
你可以试试通配符。例如，用通配符替换搜索词中某处的字母，然后将该词拆分为两个子字符串并将它们插入 TST。然后搜索所有模式，而不仅仅是完全匹配。它通过创建字典单词的每个前缀来工作。但我建议尝试使用 TST 的 aho-corasick 算法。
拼写检查器可能希望找到与目标词最接近的匹配项，而不是恰好具有相同前缀的词。 TST 擅长查找前缀，但如果您想查找 相似 个单词，它们对您的帮助不大。
在你的例子中（假设 "manly" 不在你的字典中，虽然它是一个词），建议 "mainly" 比 "mango" 更有可能，但它赢了' 通过从最长匹配前缀开始的扫描找到。
但是，如果您希望扫描从最长的匹配前缀开始：
1) 修改 searchTST，使其 return 成为 struct Node*，并将最后一个 else 子句替换为：
else if (*(word+1) == '[=10=]')
return root;
else {
struct Node* child = searchTST(root->eq, word+1);
return child ? child : root;
}
2) searchTST 现在将 return 目标的最长匹配前缀的根。调用者必须检查是否设置了 returned 节点的 isEndOfString 标志。
3) 您可以在由 searchTST 编辑的节点 return 上使用类似 traverseTST 的内容，以便生成以该前缀开头的所有单词。
我使用三元搜索树 (TST) 制作了一个拼写检查器。 谁能告诉我如何在 TST 中找到下一个可能的单词？
例如：如果我想在拼写检查器中搜索单词 "Manly" 并且如果该单词不存在于 TST 中，那么它会输出类似这样的单词：
你的意思是："Man" "Mango" .
下面是实现三元搜索树的代码。 任何机构都可以修改以找到最接近的单词。 http://www.geeksforgeeks.org/ternary-search-tree/
你可以试试通配符。例如，用通配符替换搜索词中某处的字母，然后将该词拆分为两个子字符串并将它们插入 TST。然后搜索所有模式，而不仅仅是完全匹配。它通过创建字典单词的每个前缀来工作。但我建议尝试使用 TST 的 aho-corasick 算法。
拼写检查器可能希望找到与目标词最接近的匹配项，而不是恰好具有相同前缀的词。 TST 擅长查找前缀，但如果您想查找 相似 个单词，它们对您的帮助不大。
在你的例子中（假设 "manly" 不在你的字典中，虽然它是一个词），建议 "mainly" 比 "mango" 更有可能，但它赢了' 通过从最长匹配前缀开始的扫描找到。
但是，如果您希望扫描从最长的匹配前缀开始：
1) 修改 searchTST，使其 return 成为 struct Node*，并将最后一个 else 子句替换为：
else if (*(word+1) == '[=10=]')
return root;
else {
struct Node* child = searchTST(root->eq, word+1);
return child ? child : root;
}
2) searchTST 现在将 return 目标的最长匹配前缀的根。调用者必须检查是否设置了 returned 节点的 isEndOfString 标志。
3) 您可以在由 searchTST 编辑的节点 return 上使用类似 traverseTST 的内容，以便生成以该前缀开头的所有单词。