使用Trie或SortedSet進行字典操作？

Question

我有一些關於Tries/SortedSets用於字典的問題。

1. 哪種查找效率更高？
2. 哪個更有效的虛擬內存？
3. 當用於字典時，任何結構是否還有其他優點/缺點？

沒有必要回答所有三個，只是尋找一些好的迴應和源材料，如果你有任何。謝謝。

Answer 1

1. 查找在特里被速度極快的，因爲他們只是需要O(length of key)比較，幾乎一樣快，因爲它可能是。 SortedSet通常使用平衡二叉搜索樹來實現，它將執行更多的比較，在最壞的情況下O(height of tree)字符串比較。所以Trie在這裏是明顯的贏家。

2. 虛擬內存效率可以看作是數據結構可以加載到內存的速度。 SortedSet佔據與元素數量成正比的空間。它使用指針來實現，這可能會影響加載效率。可以通過序列化並將其存儲在數組中來改進，但這會增加所需的空間。最簡單形式的Trie需要內存批次。它也使用指針來實現，這對於加載效率來說也是不利的。即使序列化，也需要大量的內存。但是這裏有一些有趣的替代方案，它們壓縮了trie並給出了相同的性能。 基數測試佔用的內存量要少得多。更好的是，一個DAWG（定向非空字圖）重疊了常見的後綴和前綴，並壓縮了大量的字典。壓縮之後，DAWG可能會佔用比字典本身更少的空間。它是使用數組實現的，所以加載速度也很快。最後，如果你有一個靜態字典，DAWG將是最好的選擇，否則就取決於。

3. 一個trie將鍵看作序列。它是一個前綴樹。您可以非常快速地獲得從前綴開始的所有單詞。使用trie，可以高效地執行自動完成和自動更正。一些鍵如浮點數可能會導致長鏈，這是不好的。 SortedSet將鍵視爲可比項目。所以很容易劃分元素。 SortedSet和Trie都可以按字母順序提供密鑰，但我想SortedSet會更快。