如何從文件中刪除重複項？

如何從大數量的大文件中刪除重複項？這是一個關於算法和數據結構的訪問問題，而不是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

如何從文件中刪除重複項？

回答

相關問題