拼寫檢查器的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

回答