Удалить повторяющиеся строки из большого файла в Python

Question

У меня есть CSV-файл, из которого я хочу удалить повторяющиеся строки, но он слишком велик, чтобы поместиться в память.Я нашел способ сделать это, но я думаю, что это не лучший способ.

Каждая строка содержит 15 полей и несколько сотен символов, и все поля необходимы для определения уникальности.Вместо того, чтобы сравнивать всю строку, чтобы найти дубликат, я сравниваю hash(row-as-a-string) в попытке сэкономить память.Я установил фильтр, который разбивает данные на примерно равное количество строк (например, дни недели), и каждый раздел достаточно мал, чтобы таблица соответствия значений хеш-функции для этого раздела помещалась в памяти.Я пропускаю файл один раз для каждого раздела, проверяю уникальные строки и записываю их во второй файл (псевдокод):

import csv

headers={'DayOfWeek':None, 'a':None, 'b':None}
outs=csv.DictWriter(open('c:\dedupedFile.csv','wb')
days=['Mon','Tue','Wed','Thu','Fri','Sat','Sun']

outs.writerows(headers)

for day in days:
    htable={}
    ins=csv.DictReader(open('c:\bigfile.csv','rb'),headers)
    for line in ins:
        hvalue=hash(reduce(lambda x,y:x+y,line.itervalues()))
        if line['DayOfWeek']==day:
            if hvalue in htable:
                pass
            else:
                htable[hvalue]=None
                outs.writerow(line)

Один из способов ускорить это - найти лучшийФильтр для уменьшения необходимого количества проходов.Предполагая, что длина строк распределена равномерно, возможно вместо

for day in days: 

и

if line['DayOfWeek']==day:

у нас есть

for i in range(n):

и

if len(reduce(lambda x,y:x+y,line.itervalues())%n)==i:

где 'n' настолько маленькое, насколько позволяет память.Но это все еще использует тот же метод.

Уэйн Вернер предоставил хорошее практическое решение ниже;Мне было любопытно, есть ли лучший / более быстрый / простой способ сделать это с точки зрения алгоритма.

PS Я ограничен Python 2.5.

Answer 1

Если вы хотите действительно простой способ сделать это, просто создайте базу данных sqlite:

import sqlite3
conn = sqlite3.connect('single.db')
cur = conn.cursor()
cur.execute("""create table test(
f1 text,
f2 text,
f3 text,
f4 text,
f5 text,
f6 text,
f7 text,
f8 text,
f9 text,
f10 text,
f11 text,
f12 text,
f13 text,
f14 text,
f15 text,
primary key(f1,  f2,  f3,  f4,  f5,  f6,  f7,  
            f8,  f9,  f10,  f11,  f12,  f13,  f14,  f15))
"""
conn.commit()

#simplified/pseudo code
for row in reader:
    #assuming row returns a list-type object
    try:
        cur.execute('''insert into test values(?, ?, ?, ?, ?, ?, ?, 
                       ?, ?, ?, ?, ?, ?, ?, ?)''', row)
        conn.commit()
    except IntegrityError:
        pass

conn.commit()
cur.execute('select * from test')

for row in cur:
    #write row to csv file

Тогда вам не придется беспокоиться о какой-либо логике сравнения - просто позвольте sqlite позаботиться об этом за вас. Это, вероятно, не будет намного быстрее, чем хеширование строк, но это, вероятно, намного проще. Конечно, вы бы изменили тип, хранящийся в базе данных, если хотите, или нет, в зависимости от ситуации. Конечно, поскольку вы уже конвертируете данные в строку, вы можете вместо этого иметь только одно поле. Здесь много вариантов.

Answer 2

Вы в основном выполняете сортировку слиянием и удаляете дублированные записи.

Разделение входных данных на фрагменты размером с память, сортировка каждого фрагмента, затем объединение фрагментов при удалении дубликатов - это в общем здравая идея.

На самом деле, до пары гигабайт я бы позволил системе виртуальной памяти справиться с этим и просто написать:

input = open(infilename, 'rb')
output = open(outfile, 'wb')

for key,  group in itertools.groupby(sorted(input)):
    output.write(key)

Answer 3

Ваш текущий метод не гарантированно работает должным образом.

Во-первых, существует небольшая вероятность того, что две строки, которые на самом деле отличаются друг от друга, могут давать одно и то же значение хеш-функции. hash(a) == hash(b) не всегда означает, что a == b

Во-вторых, вы увеличиваете вероятность с помощью каперса «уменьшить / лямбда»:

>>> reduce(lambda x,y: x+y, ['foo', '1', '23'])
'foo123'
>>> reduce(lambda x,y: x+y, ['foo', '12', '3'])
'foo123'
>>>

Кстати, неужели "" .join (['foo', '1', '23']) будет несколько понятнее?

Кстати, почему бы не использовать set вместо dict для htable?

Вот практическое решение: получите пакет "core utils" с сайта GnuWin32 и установите его. Тогда:

1. напишите копию вашего файла без заголовков, скажем, в infile.csv
2. c:\gnuwin32\bin\sort --unique -ooutfile.csv infile.csv
3. прочитайте outfile.csv и напишите копию с добавленными заголовками

Для каждого из шагов 1 и 3 вы можете использовать скрипт Python или некоторые другие утилиты GnuWin32 (голова, хвост, тройник, кошка, ...).

Answer 4

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

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

Кстати, если значения CSV нормализованы (т. Е. Записи считаются равными, если соответствующие строки CSV эквивалентны побайтно), вам вообще не нужно здесь разбирать CSV, просто разберитесь с простыми текстовыми строками .

Answer 5

Как насчет использования модуля heapq для чтения фрагментов файла до предела памяти и записи их отсортированных фрагментов (heapq хранит вещи всегда в отсортированном порядке).

Или вы можете поймать первое слово в строке иразделите файл на части этим.Затем вы можете прочитать строки (возможно, сделайте '' .join (line.split ()), чтобы объединить интервалы / табуляции в строке, если это нормально, чтобы изменить интервал) в наборе в алфавитном порядке, очистив набор между частями (набор удаляетдубликаты), чтобы получить вещи наполовину отсортированными (набор не в порядке, если вы хотите, чтобы вы могли читать в кучу и записывать, чтобы получить отсортированный порядок, последнее вхождение в набор заменяет старые значения по ходу.) В качестве альтернативы вы также можете отсортировать кусоки удалите дубликаты строк с помощью группового решения Джо Коберга.Наконец, вы можете соединять части вместе (вы, конечно же, можете писать, переходя по частям к конечному файлу во время сортировки частей)

Answer 6

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

Считать строки ввода в B-деревья, упорядоченные по хеш-значениям каждой строки ввода, записав их на диск, когда память заполнится.Мы заботимся о том, чтобы хранить на B-деревьях оригинальные строки, прикрепленные к хешу (в виде набора, поскольку мы заботимся только об уникальных строках).Когда мы читаем повторяющийся элемент, мы проверяем строки, установленные в сохраненном элементе, и добавляем его, если это новая строка с хешем с тем же значением.

Почему B-деревья?Они требуют меньше операций чтения с диска, когда вы можете (или хотите) только читать их части в память.Степень (число дочерних элементов) на каждом узле зависит от доступной памяти и количества строк, но вы не хотите иметь слишком много узлов.

Как только у нас есть эти B-деревья на диске, мы сравниваемсамый низкий элемент от каждого из них.Мы удаляем самое низкое из всех B-деревьев, которые его имеют.Мы объединяем их наборы строк, что означает, что у нас не осталось дубликатов для этих строк (а также что у нас больше нет строк, хэширующих до этого значения).Затем мы записываем строки этого слияния в выходную структуру csv.

Мы можем отделить половину памяти для чтения B-деревьев и половину, чтобы некоторое время сохранить выходной csv в памяти.Мы сбрасываем csv на диск, когда его половина заполнена, добавляя к уже написанному.Какую часть каждого B-дерева, которую мы читаем на каждом шаге, можно приблизительно рассчитать с помощью (available_memory / 2) / number_of_btrees, округленного, чтобы мы прочитали полные узлы.

В псевдопифон:

ins = DictReader(...)
i = 0
while ins.still_has_lines_to_be_read():
    tree = BTree(i)
    while fits_into_memory:
        line = ins.readline()
        tree.add(line, key=hash)
    tree.write_to_disc()
    i += 1
n_btrees = i

# At this point, we have several (n_btres) B-Trees on disk
while n_btrees:
    n_bytes = (available_memory / 2) / n_btrees
    btrees = [read_btree_from_disk(i, n_bytes)
              for i in enumerate(range(n_btrees))]
    lowest_candidates = [get_lowest(b) for b in btrees]
    lowest = min(lowest_candidates)
    lines = set()
    for i in range(number_of_btrees):
        tree = btrees[i]
        if lowest == lowest_candidates[i]:
            node = tree.pop_lowest()
            lines.update(node.lines)
        if tree.is_empty():
        n_btrees -= 1

    if output_memory_is_full or n_btrees == 0:
        outs.append_on_disk(lines)