從大型數據集中刪除重複的行

Question

我們假設我有一個非常大的數據集，它無法放入內存中，數據集中有數百萬條記錄，我想刪除重複的行（實際上保留了一行重複）

在空間和時間複雜性方面最有效的方法是什麼？

我的想法：

1.使用布隆過濾器，我不知道它是如何實現的，但我猜的副作用是有誤報，在這種情況下，我們怎麼能找到，如果它是真的是否重複？

2，採用哈希值，在這種情況下，如果我們有重複值的數量不多，唯一散列值的數量會很大，我們再次可能與內存問題，

Answer 1

您的解決方案2：使用哈希值不強制內存問題。你只需要將哈希空間分割成適合內存的切片。更確切地說：

考慮一個存儲記錄集合的散列表，每個記錄只能由表中的索引表示。舉例來說，這樣的散列表將是4GB。然後你將你的哈希空間分成k = 4片。根據散列值的最後兩位數字，每條記錄都會進入一個片段。所以算法大致如下：

let k = 2^M 
for i from 0 to k-1: 
    t = new table 
    for each record r on the disk: 
     h = hashvalue(r) 
     if (the M last bit of h == i) { 
      insert r into t with respect to hash value h >> M 
     } 
    search t for duplicate and remove them 
    delete t from memory 

缺點是你必須將每個記錄散列k次。它的優點是它可以平均分佈。

這裏是Python中的原型：

# Fake huge database on the disks 
records = ["askdjlsd", "kalsjdld", "alkjdslad", "askdjlsd"]*100 

M = 2 
mask = 2**(M+1)-1 
class HashLink(object): 
    def __init__(self, idx): 
     self._idx = idx 
     self._hash = hash(records[idx]) # file access 

    def __hash__(self): 
     return self._hash >> M 

    # hashlink are equal if they link to equal objects 
    def __eq__(self, other): 
     return records[self._idx] == records[other._idx] # file access 

    def __repr__(self): 
     return str(records[self._idx]) 

to_be_deleted = list() 
for i in range(2**M): 
    t = set() 
    for idx, rec in enumerate(records): 
     h = hash(rec) 
     if (h & mask == i): 
      if HashLink(idx) in t: 
       to_be_deleted.append(idx) 
      else: 
       t.add(HashLink(idx)) 

結果是：

>>> [records[idx] for idx in range(len(records)) if idx not in to_be_deleted] 
['askdjlsd', 'kalsjdld', 'alkjdslad'] 

Answer 2

由於需要重複的項目的缺失，不排序或索引，你可能會掃描整個數據集每刪除一次，在性能方面成本不可承受。鑑於此，您可能會想到一些外部排序或數據庫。如果你不關心輸出數據集的排序。根據記錄或記錄的密鑰的散列，創建存儲輸入數據集子集的「n」個文件。獲取散列並用'n'模取模並獲取正確的輸出文件來存儲內容。由於每個輸出文件的大小現在很小，所以您的刪除操作將會非常快;對於輸出文件，您可以使用普通文件或sqlite/berkeley數據庫。我會推薦sqlite/bdb。爲了避免掃描每個寫入輸出文件，您可以爲每個輸出文件都有一個前端布隆過濾器。布隆過濾器並不困難。很多圖書館都可用。計算'n'取決於你的主要記憶，我會說。爲'n'帶來悲觀，巨大的價值。完成工作後，將所有輸出文件連接成一個文件。