實現字典的最佳數據結構？

Question

什麼是存儲字典中所有單詞的最佳數據結構？我能想到的最好的是使用一個HashMap，這將映射到一個HashTable。基本上，根據第一個字符，我們將獲得關聯的HashTable，然後使用它，我們可以添加從該字符開始的單詞。然後我們將根據字符串選擇一個好的散列函數。

有沒有更好的方法？

Answer 1

取決於你想做的事，有很多不錯的數據結構。

如果你只是想保存的話，問「這個詞是在不在？」，沒有其他花哨的機械標準的哈希表是一種合理的方法。如果提前將該單詞列表固定，請考慮使用perfect hash table以獲得出色的性能和空間使用率。

如果您希望能夠檢查給定的前綴是否存在，同時支持快速查找，trie是一個不錯的選擇，雖然它可能有點空間效率低下。它也支持快速插入或刪除。它也允許按字母順序進行迭代，哈希不提供。這實質上就是你在答案中描述的結構，但根據用例，嘗試的其他表示可能會更好。

如果除了上面的內容，您知道單詞列表是固定的，請考慮使用DAWG（有向無環詞表），該語言本質上是語言的最小狀態DFA。它比trie更緊湊，但支持許多相同的操作。

如果您想要類似特里行爲但不想支付巨大的空間處罰，ternary search tree是另一個可行的選項，radix tree也是如此。這些結構是非常不同的，但是在不同的情況下可以比結果好得多。

如果空間是一個問題，但你想有一個線索，尋找到succinct trie表示，其中有慢查找，但只是理論上左右最佳空間使用情況。該鏈接討論了它如何在JavaScript中用作傳輸大量數據的簡單方法。一個替代的緊湊型代表是double-array trie，但我承認我對此知之甚少。

如果您想使用字典進行拼寫檢查等操作，您需要找到與其他字詞類似的字詞，則BK-tree是一個很好的數據結構。

希望這會有所幫助！