大規模處理在非常大的字符串列表中查找唯一最長的單詞？

Question

我在輸入列表中找到最長的非重複字符串。代碼是here。我的問題是假設輸入列表太大而不適合內存。

1. 如何解決這個問題，如果輸入不能適應內存，（即可以說輸入是一個永無止境的字符串的新聞報紙）？

2. 燦/如果是的話，怎麼能只使用Hadoop /地圖縮小的概念（任何URL的讚賞）

Answer 1

輸入列表並不需要留在記憶：你就不能流它在？

就使用MapReduce進行此類任務而言，請看Data-Intensive Text Processing with MapReduce。

Answer 2

如果輸入是太大，無法在內存中，你有兩個選擇：

1）委派到數據庫，或其他一些基於磁盤的結構。這將花費時間和資源，但你會得到一個準確的答案

2）使用概率的方法，如Bloom filter，這是一種概率HashSet。這與地圖以及工作減少如下：

地圖輸入<word>元組到<word, bloom_filter>元組，其中word是不是最長的字又重複，並且bloom_filter是迄今發現

可以將所有單詞的概率表示然後通過比較兩個word長度來減少兩個<word, bloom_filter>元組，並且在組合兩個bloom_filter之前檢查每個元素與另一個的bloom_filter。注意，這可能導致沒有最長的word - 這是非常有效的，如可以在輸入案例(dog, dog, plant, plant)。