从BIG文本文件中删除重复文件

Question

我有一个相当大的文本文件，平均30GB。我想从这个文件中删除重复的行。什么是一个高效的算法来做到这一点。对于小文件，我通常使用字典，例如Python字典来存储唯一的密钥。但是这次文件相当大。任何语言建议都很好。 （我正在考虑使用C？还是它不是语言相关的，但算法更重要？）。感谢

Answer 1

如果你不能只火了与足够的内存来保存在RAM中的一切亚马逊的实例，这是战略的，我会用：

第1步 - 经历并生成校验和/散列值每一行。我可能会使用SIPHASH。将这些输出到一个文件。

第2步 - 对siphash值的文件进行排序，并丢弃只有一个条目的文件。将结果输出为一组哈希值&匹配数。

第3步 - 通读文件。重新生成每一行的散列值。如果它的一条线匹配，请在内存中保留它。如果存在另一个具有相同散列值的内存，则比较以查看这些行本身是否匹配。输出“匹配”如果为真。如果您已经看到所有具有相同散列值并且不匹配的N行，请继续处理该记录。

这种策略取决于副本的数量只是总行数的一小部分。如果情况并非如此，那么我会采用其他策略，如分而治之。