Удаление повторяющихся строк из большого набора данных

Question

Предположим, что у меня очень большой набор данных, который не может быть помещен в память, в наборе данных есть миллионы записей, и я хочу удалить повторяющиеся строки (фактически сохраняя одну строку из дубликаты)

Каков наиболее эффективный подход с точки зрения пространственной и временной сложности?

То, что я подумал:

1.Using цветения фильтра, я не уверен, как это реализовано, но я предполагаю, что побочный эффект, имеющий ложные срабатывания, в этом случае, как мы можем найти, если это действительно дублировать или нет?

2.Using хэш-значение, в этом случае, если у нас есть небольшое количество повторяющихся значений, число уникальных значений хэша будет большим и снова мы можем иметь проблемы с памятью,

Answer 1

Вашего решением 2: с помощью хэш-значение не вызывает проблемы с памятью. Вам просто нужно разделить хэш-пространство на срезы, которые вписываются в память. Точнее:

Рассмотрим хеш-таблицу, хранящую набор записей, каждая запись представлена ​​только ее индексом в таблице. Скажем, например, что такая хэш-таблица будет 4 ГБ. Затем вы разбиваете хэш-пространство на 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 

Недостаток заключается в том, что у вас есть хэш каждая запись к раз. Преимущество состоит в том, что его можно распределить тривиально.

Вот прототип в 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 db. Я бы порекомендовал sqlite/bdb. Чтобы избежать сканирования для каждого файла записи в выходной файл, у вас может быть встроенный фильтр цветения для каждого выходного файла. Фильтр Bloom не так уж и трудный. Имеется множество библиотек. Я бы сказал, вычисление «n» зависит от вашей основной памяти. Пойдите с пессимистичным, огромным значением для 'n'. Как только ваша работа будет выполнена, объедините все выходные файлы в один.