拼写检查器的BST或哈希表字典

如果我要实现一个文字处理器的拼写检查器，哪个会更高效的执行？字典需要频繁检索和偶尔插入。由于没有最大数量的字典项目，BST将是更好的选择。但它也需要频繁的检索，并且哈希表具有更快的搜索操作时间。在这种情况下更好的答案是什么？拼写检查器的BST或哈希表字典

2016-12-15 JJTO

你打算有这样的拼写检查器实际上提供更正，或只返回一个已知的字/未知字标记每个字？ – Blorgbeard

这个问题没有说明......我想如果你需要提供更正，你需要支持一个快速有序的遍历操作，所以BST将是最好的选择。 – JJTO

我知道这不是，所以我问。这似乎是一个没有更正的相当无用的拼写检查器。你真的在拼写检查器，还是这个问题只是学术？另外，您是否阅读过这篇文章：http：//norvig.com/spell-correct.html – Blorgbeard

由于没有最大数量的字典项目，BST将是一个更好的选择。

IMO，使用BST实现字典将是一个坏主意。 Trie是您的正确选择。

2016-12-15 11:57:54

回答