如何从文件中删除重复项？

如何从大数量的大文件中删除重复项？这是一个关于算法和数据结构的访问问题，而不是sort -u以及类似的东西。如何从文件中删除重复项？

我假设文件不适合内存和数字范围足够大，所以我不能使用内存计数/桶排序。

唯一的选择就是对文件进行排序（例如merge sort）并再次传递排序文件以过滤出重复项。

是否合理。还有其他选择吗？

来源

2012-07-20 Michael

您对输入的了解越多，选择/开发适当算法的位置就越好。 – greybeard 2017-03-07 09:04:23

是的，解决方案是有道理的。

另一种方法是构建一个基于文件系统的散列表，并将其作为一个集合来维护。首先迭代所有元素并将其插入到您的集合中，然后在第二次迭代中打印集合中的所有元素。

这是执行和数据依赖性，在大O复杂性方面表现更好，散列提供O(n)时间平均情况和O(n^2)最差情况，而合并排序选项提供更稳定的O(nlogn)解决方案。

来源

2012-07-20 14:05:37 amit

如果在mergesort中使用“merge”（a.k.a.“union”）的重复删除变体，则甚至不需要单独传递排序数据。哈希表应该是空着的，以便表现良好，即比文件本身更大 - 我们被告知文件本身是大。

查找多路合并（例如here）和外部排序。

来源

2012-07-20 16:16:11

Mergesort或Timsort（这是一个改进的mergesort）是一个好主意。 EG：http://stromberg.dnsalias.org/~strombrg/sort-comparison/

你也许能够从bloom过滤器中获得一些里程数。这是一个具有低内存要求的概率数据结构。您可以使用布隆过滤器来调整错误概率。 EG：http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/你可以使用一个抛出绝对唯一的值，然后通过其他方法仔细检查可能不唯一的值。如果您的输入数据集有大量重复项，这将特别有价值。它不需要直接比较元素，它只是使用潜在的大量散列函数来散列元素。

您也可以使用磁盘BTree或2-3树或类似的。这些通常存储在磁盘上，并按键顺序保存键/值对。

来源

2012-07-20 21:20:57 user1277476

如何从文件中删除重复项？

回答

相关问题