如何在單詞超過2億時使用Java刪除重複的單詞？

我有一個文件（大小=〜1.9 GB），其中包含約2.2億（〜2.2億）字/字符串。他們有重複，每100個單詞幾乎有1個重複的單詞。如何在單詞超過2億時使用Java刪除重複的單詞？

在我的第二個程序中，我想讀取文件。我成功地通過使用BufferedReader的行讀取文件。

我們刪除重複，我們可以使用SET（和它的實現），但設置有問題，如描述以下3個不同的場景：

在默認的JVM，集最多可包含0.7- 80萬字，然後是OutOfMemoryError。
使用512M JVM大小，Set可以包含高達5-6百萬字，然後是OOM錯誤。
使用1024M JVM大小，Set最多可包含12-13萬個字，然後出現OOM錯誤。這裏有1000萬條記錄添加到Set之後，操作變得非常緩慢。例如，添加下一個約4000條記錄，它花費了60秒。

我有限制，我無法進一步增加JVM的大小，我想從文件中刪除重複的單詞。

請讓我知道，如果你有任何其他方式/方法從這樣一個巨大的文件中使用Java刪除重複的單詞的任何想法。許多感謝:)

信息的添加問題：我的話基本上是字母數字，他們是我們的系統中唯一的ID。因此，他們不是簡單的英語單詞。

來源

2012-09-19 Ketan

的解決方案，你可以使用一個數據庫，甚至第二個文件來存儲結果呢？ –

我想你會迭代很長一段時間。 –

我會確保我有足夠的內存來完成任務。您可以購買大約100美元的16 GB PC內存。這些日子並沒有那麼多花費。 –

使用merge sort並在第二遍中刪除重複項。你甚至可以在合併的時候刪除重複的內容（把最新的單詞添加到RAM中輸出，並將候選對象也與之相比較）。

來源

2012-09-19 19:07:11

+1。對於這個問題，這應該相當簡單明瞭。 –

而且可能會導致OutOfMemory –

@lukas，你怎麼看到這種情況？合併排序在RAM上可能非常低。 –

根據單詞的第一個字母，將大文件劃分爲26個較小的文件。如果任何字母文件仍然太大，請使用第二個字母來分割該字母文件。

使用Set分別處理每個字母文件以刪除重複項。

來源

2012-09-19 19:07:55

這會假設'Q'與'A'一樣頻繁，或者您可能會翻閱適合某些字母的10M個單詞。 –

@Joachim Isaksson：很好。按前兩個字母分解最大的文件。 –

我發現這個解決方案比其他人提供的簡單的基於排序的解決方案更復雜，解釋也更復雜。對磁盤上的大文件進行排序是現成實現的常見任務。如果它們仍然太大，整個「將更大的文件細分」需要更多代碼或手動干預。要繼續分類整個事情並且完成它，實際上要簡單得多。 –

對於大文件，我嘗試不將數據讀入內存，而是對內存映射文件進行操作，並根據需要讓操作系統頁進/出內存。如果你的設置結構在這個內存映射文件中包含偏移量而不是實際的字符串，它會消耗更少的內存。

看看這篇文章：

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html

來源

2012-09-19 19:07:56

我會以同樣的方式處理這個在Java作爲在所有其他語言編寫一個重複數據刪除過濾，並根據需要管它經常。

這就是我的意思是（在僞代碼）：

輸入參數：Offset，Size
分配大小Size的搜索結構（= Set，但不必是一個）
閱讀從stdin（或EOF）讀取Size中的元素，將它們存儲在Set中。如果重複，則刪除，否則寫入標準輸出。從標準輸入直到EOF，如果他們在Set然後放下，否則寫
閱讀內容到標準輸出

現在管儘可能多的情況下，你需要（如果存儲是沒有問題的，因爲你有可能僅作爲多隨着Offsets和理智Size增加。這讓你可以使用更多的核心，因爲我懷疑這個過程是CPU綁定的。如果您匆忙，您甚至可以使用netcat並將處理擴展到更多機器。

來源

2012-09-19 19:09:20

解決這類問題的一個經典方法是Bloom filter。基本上你會多次散列你的單詞，並且每個散列結果都將一些位設置在一個位向量中。如果你正在檢查一個單詞，並且它的哈希中的所有位都被設置在矢量中，那麼你可能會看到它，並且它是重複的（可以通過增加矢量中的哈希/位的數目來任意設置此概率）。

這是早期的拼寫檢查工作。他們知道字典中是否有單詞，但他們無法告訴你正確的拼寫是什麼，因爲它只會告訴你是否看到當前單詞。

有一些開源實現在那裏，包括java-bloomfilter

來源

2012-09-19 19:10:43

你如何確認它實際上是重複的（而不是誤報）？ –

您可以將內存成本設置爲任意低的概率。不幸的是，這是您爲概率算法付出的代價。考慮到您的限制，數據大小以及在排序解決方案可能更合適之後您不需要檢查其他成員的事實。 –

布隆過濾器會不必要地不精確。 – NovaDenizen

問：難道這些真的話，還是他們是別的東西 - 短語，零件編號等？

對於普通口語中的單詞，人們會認爲在第一個幾千之後，你會發現大多數獨特的單詞，所以你真正需要做的就是讀一個單詞，在字典中檢查它，如果找到，跳過它，如果沒有找到，將它添加到字典並寫出來。

在這種情況下，你的字典只有幾千字大。你不需要保留源文件，因爲只要你找到它們就寫出唯一的單詞（或者你可以簡單地在完成時轉儲字典）。

來源

2012-09-19 19:13:46

如果您對這些項目進行排序，重複項將很容易檢測並刪除，因爲重複項會聚集在一起。

這裏有代碼，你可以用它來歸併大文件： http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

來源

2012-09-19 19:17:26

如果你有posibility（使用批量插入）插入詞語的數據庫的臨時表，那麼這將是一個選擇不同的表格。

來源

2012-09-19 20:03:59

在這種情況下，Quicksort將是一個比Mergesort更好的選擇，因爲它需要更少的內存。 This thread對於原因有很好的解釋。

來源

2012-09-19 20:17:53 Evo510

但是，快速排序是內存排序，並且mergesort只需要足夠的RAM來存放2個讀取緩衝區和一個寫入緩衝區。 – NovaDenizen

您可能可以使用trie數據結構來一次完成這項工作。它具有推薦它用於這類問題的優點。查找和插入很快。其代表性相對節省空間。你可能能夠在RAM中表示你的所有單詞。

來源

2012-09-19 21:33:11 gregg

這是迄今爲止最有趣的建議之一。您可能會耗盡內存，然後您需要查看全新的解決方案，但這至少可以提供將所有獨特字符串存儲在內存中的一些希望，這很方便。 – Buhb

你仍然需要不止一個節點親不同字 - 即使你不存儲字符串本身也是至少8字節，並且鏈接數組節點 –

爲了不必太擔心實現，您應該使用數據庫系統，無論是普通的舊關係SQL還是無SQL解決方案。我很肯定你可以使用例如Berkeley DB Java版，然後做（僞代碼）

for(word : stream) { 
    if(!DB.exists(word)) { 
    DB.put(word) 
    outstream.add(word) 
    } 
}

的問題在本質上是容易的，你需要的東西存儲在磁盤上，因爲沒有足夠的內存，那麼無論使用排序O（N日誌N）（不必要的）或散列O（N）來找到唯一的單詞。

如果您想要一個很有可能工作但不能保證這樣做的解決方案，請使用LRU類型的散列表。根據經驗Zpif's law你應該沒問題。

後續問題給那裏的一些聰明人，如果我有64位機器並且設置堆大小爲12GB，那麼虛擬內存不應該照顧問題（儘管不是最佳方式），或者java是不是這樣設計的？

來源

2012-09-20 01:56:01 user1443778

即使在英語中，對於自然語言而言，單詞數量也很大，但上面的估計值只有大約80000個單詞。在此基礎上，你可以只使用一個HashSet並添加所有你的話它（可能在所有小寫，以避免問題的情況下）：

Set<String> words = new HashSet<String>(); 
while (read-next-word) { 
    words.add(word.toLowerCase()); 
}

如果他們是真正的話，這不會造成內存問題，也會很快！

來源

2012-09-20 02:32:21 Bohemian

這是我第一次想到，但在他說他們已經嘗試過設置並失敗。他們一定不是真正的話 – enTropy

大多數高性能解決方案都是由於省略了不必要的東西而產生的。你只看重複，所以不要存儲單詞本身，存儲哈希值。但是，等一下，你也不會對哈希感興趣，只要他們已經見過 - 不要存儲它們。將哈希視爲非常大的數字，並使用bitset來查看您是否已經看過這個數字。

所以你的問題歸結爲真正大的稀疏填充位圖 - 大小取決於哈希寬度。如果你的哈希高達32位，你可以使用riak位圖。

...去思考真正的大位圖128+位散列％）（我會回來）

來源

2012-10-09 09:18:55

如何在單詞超過2億時使用Java刪除重複的單詞？

回答

相關問題