樹或平衡二叉搜索樹來存儲字典？

Question

我有一個簡單的要求（或許是假設的）：

我想存儲英文單詞詞典（n個單詞）並給出一個單詞（字符長度爲m），詞典能夠告訴，如果單詞存在於詞典中或不。 這將是一個適當的數據結構？

平衡二叉搜索樹？如在C++ STL關聯數據結構等集，地圖

或

完成對字符串字典樹

一些複雜性分析：在平衡BST ，時間將是（log n）的*米（比較2個字符串需要每個字符需要O（m）個時間）

如果在每個節點，我們可以在O（1）時間分支出來，我們可以使用O（m）在每個節點上，我們可以在O（1）中分支時間無效。在每個節點處，最大可能的分支將是26.如果我們想要O（1）在一個節點上，我們將在每個節點的字符上保留一個短的數組索引。這將炸燬空間。在trie中的幾個級別之後，分支會減少，所以最好保留下一個節點字符和指針的鏈表。

什麼看起來更實用？任何其他的權衡？

感謝，

Answer 1

我想說的是使用Trie，或者更好的方式是使用其更高效的空間表親Directed Acyclic Word Graph (DAWG)。

它具有與Trie相同的運行時特性（插入，查找，刪除），但重疊了常見的後綴以及常見的前綴，這可以大大節省空間。

Answer 2

二進制搜索將是更容易實現和它一定會涉及到最多幾十比較字符串。鑑於您事先知道數據，您可以構建一個平衡二叉樹，以便可以預測並輕鬆理解性能。考慮到這一點，我會使用一個標準的二叉樹（可能使用C++的set，因爲它通常以樹的形式實現）。

Answer 3

一個簡單的解決方案是將dict作爲已排序的\ n分隔的單詞存儲在磁盤上，將其加載到內存中並執行二分搜索。這裏唯一的非標準部分是當你進行二分搜索時，你必須向後掃描一個單詞的開頭。

這是一些代碼！ （它假定全局wordlist指向加載字典，並wordlist_end這只是加載的字典結束後百分點。

// Return >0 if word > word at position p. 
// Return <0 if word < word at position p. 
// Return 0 if word == word at position p. 
static int cmp_word_at_index(size_t p, const char *word) { 
    while (p > 0 && wordlist[p - 1] != '\n') { 
    p--; 
    } 
    while (1) { 
    if (wordlist[p] == '\n') { 
     if (*word == '\0') return 0; 
     else return 1; 
    } 
    if (*word == '\0') { 
     return -1; 
    } 
    int char0 = toupper(*word); 
    int char1 = toupper(wordlist[p]); 
    if (char0 != char1) { 
     return (int)char0 - (int)char1; 
    } 
    ++p; 
    ++word; 
    } 
} 

// Test if a word is in the dictionary. 
int is_word(const char* word_to_find) { 
    size_t index_min = 0; 
    size_t index_max = wordlist_end - wordlist; 
    while (index_min < index_max - 1) { 
    size_t index = (index_min + index_max)/2; 
    int c = cmp_word_at_index(index, word_to_find); 
    if (c == 0) return 1; // Found word. 
    if (c < 0) { 
     index_max = index; 
    } else { 
     index_min = index; 
    } 
    } 
    return 0; 
} 

這種方法的一個巨大優勢是，字典存儲在人類可讀的方式並且你不需要任何花哨的代碼來加載它（分配一塊內存並一次讀取（）它）

如果你想使用一個trie，你可以使用一個包和後綴壓縮的表示形式，下面是Donald Knuth的學生Franklin Liang的一個鏈接，他在論文中寫了這個技巧。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7018&rep=rep1&type=pdf

它採用了簡單的文字字典代表性的存儲一半，爲您提供了一個線索的速度，並且可以（如文字字典表示）在磁盤上存儲整個事情，在一個加載走。

它使用的技巧是將所有trie節點打包到單個數組中，並在可能的情況下將它們交錯。除了像常規trie中的每個陣列位置中的新指針（以及詞尾標記位）之外，您還可以存儲此節點用於的字母 - 這可以讓您知道該節點對於您的狀態是否有效或者它來自重疊節點。閱讀鏈接的文檔以獲得更全面更清晰的解釋，以及將樹狀結構包裝到此陣列中的算法。

實現所描述的後綴壓縮和貪婪包裝算法並不是微不足道的，但它很容易。

Answer 4

如果這是C++，您還應該考慮std::tr1::unordered_set。 （如果你有C++ 0x，你可以使用std::unordered_set。）

這只是在內部使用一個哈希表，我會打賭在實踐中，它會超出任何樹狀結構。實施起來也是微不足道的，因爲你沒有什麼可實施的。

Answer 5

行業標準是將字典存儲在散列表中，並具有一個分期O（1）查找時間。空間在行業中並不是至關重要的，特別是由於分佈式計算的進步。

散列表是谷歌如何實現其自動完成功能。具體來說，將每個詞的前綴作爲關鍵字，並將該詞作爲哈希表中的值。