在無限的詞彙流中找到重複的單詞

Question

給予你無限量的單詞來源，單詞的長度和單詞的長度可能很大，而且不知道它有多大。你會如何發現新單詞是否被重複使用，你將使用什麼樣的數據結構來存儲。這是面試時問我的問題。請幫助我驗證我的答案。

Answer 1

通常使用散列表來跟蹤每個單詞的計數。由於您只需回答單詞是否重複，因此可以將單詞計數減少爲位掩碼，以便僅爲每個散列索引存儲單個位。

如果問題與大數據有關，比如如何爲Google編寫搜索引擎，則您的答案可能需要與MapReduce或類似的分佈式技術相關（這在某種程度上與上述相同的哈希表技術有所不同）

Answer 2

與大多數順序數據一樣，在這裏，trie將是一個不錯的選擇。使用一個特里可以非常經濟地存儲新單詞，但仍然一定要找到新單詞。嘗試實際上可以被看作是單詞的多重哈希形式。如果這仍然會導致問題，因爲單詞的大小很大，您可以通過從單詞中生成一個directed acyclic word graph（DAWG）以便減少常見後綴和前綴，從而提高效率。

Answer 3

如果您只需要有效地檢測每個單詞是否曾經見過，那麼布隆過濾器就是一個不錯的選擇。這有點像一個集合和一個哈希表合併成一個，因此可能會導致誤報 - 因此，他們有時可以使用其他技術來降低風險。布盧姆過濾器的優點是它們非常節省空間（重要的是如果你真的不知道列表會有多大）。他們也很快。不利的一面是，你不能再把話說出來，你只能說出你是否看過他們。

這裏有個不錯的描述：http://en.wikipedia.org/wiki/Bloom_filter。