從BIG文本文件中刪除重複文件

Question

我有一個相當大的文本文件，平均30GB。我想從這個文件中刪除重複的行。什麼是一個高效的算法來做到這一點。對於小文件，我通常使用字典，例如Python字典來存儲唯一的密鑰。但是這次文件相當大。任何語言建議都很好。 （我正在考慮使用C？還是它不是語言相關的，但算法更重要？）。感謝

Answer 1

如果你不能只火了與足夠的內存來保存在RAM中的一切亞馬遜的實例，這是戰略的，我會用：

第1步 - 經歷並生成校驗和/散列值每一行。我可能會使用SIPHASH。將這些輸出到一個文件。

第2步 - 對siphash值的文件進行排序，並丟棄只有一個條目的文件。將結果輸出爲一組哈希值&匹配數。

第3步 - 通讀文件。重新生成每一行的散列值。如果它的一條線匹配，請在內存中保留它。如果存在另一個具有相同散列值的內存，則比較以查看這些行本身是否匹配。輸出「匹配」如果爲真。如果您已經看到所有具有相同散列值並且不匹配的N行，請繼續處理該記錄。

這種策略取決於副本的數量只是總行數的一小部分。如果情況並非如此，那麼我會採用其他策略，如分而治之。