Eliminar filas duplicadas de un archivo grande en Python

Question

Tengo un archivo csv del que quiero eliminar filas duplicadas, pero es demasiado grande para caber en la memoria. Encontré una manera de hacerlo, pero creo que no es la mejor manera.

Cada fila contiene 15 campos y varios cientos de caracteres, y todos los campos son necesarios para determinar la exclusividad. En lugar de comparar toda la fila para encontrar un duplicado, estoy comparando hash(row-as-a-string) en un intento de ahorrar memoria. Establecí un filtro que divide los datos en una cantidad aproximadamente igual de filas (por ejemplo, días de la semana) y cada partición es lo suficientemente pequeña como para que una tabla de búsqueda de valores hash para esa partición se ajuste a la memoria. Paso por el archivo una vez para cada partición, la comprobación de filas únicas y escribirlos a un segundo archivo (pseudo código):

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) 

Una forma pensaba para acelerar este proceso es mediante la búsqueda de un mejor filtro para reducir el número de pases necesarios. Suponiendo que la longitud de las filas se distribuye de manera uniforme, tal vez en lugar de

for day in days: 

y

if line['DayOfWeek']==day: 

tenemos

for i in range(n): 

y

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

donde 'n' como pequeño como la memoria lo permita. Pero esto sigue usando el mismo método.

Wayne Werner proporcionó una buena solución práctica a continuación; Tenía curiosidad de si había una forma mejor/más rápida/más simple de hacer esto desde la perspectiva del algoritmo.

P.S. Estoy limitado a Python 2.5.

Answer 1

Si desea una forma muy simple de hacer esto, basta con crear una base de datos 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 

Entonces no tendría que preocuparse acerca de cualquiera de la lógica de comparación ti mismo - simplemente dejar que cuidar de SQLite para ti. Probablemente no sea mucho más rápido que usar las cuerdas, pero probablemente sea mucho más fácil. Por supuesto, modificaría el tipo almacenado en la base de datos si quisiera, o no según sea el caso. Por supuesto, dado que ya está convirtiendo los datos en una cadena, podría tener un campo en su lugar. Un montón de opciones aquí.

Answer 2

Básicamente está haciendo un tipo de combinación y eliminando las entradas duplicadas.

Rompiendo la entrada en trozos del tamaño de la memoria, la clasificación de cada pieza, a continuación, la fusión de las piezas, mientras que la eliminación de duplicados es una buena idea en general.

En realidad, hasta un par de conciertos que iba a dejar el sistema de memoria virtual manejarlo y acaba de escribir:

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

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

Answer 3

Su método actual no se garantiza que funcione correctamente.

primer lugar, existe la pequeña probabilidad de que dos líneas que son realmente diferentes pueden producir el mismo valor hash.hash(a) == hash(b) no siempre significa que a == b

En segundo lugar, usted está haciendo la probabilidad más alta con su "lambda reducir /" alcaparra:

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

Por cierto, no "" .join ([ 'foo', '1', '23']) ser algo más claro?

BTW2, ¿por qué no utilizar un set en lugar de un dict para htable?

Aquí hay una solución práctica: obtenga el paquete "core utils" del sitio GnuWin32, e instálelo. Entonces:

1. escribir una copia de su archivo sin los encabezamientos de (digamos) infile.csv
2. c:\gnuwin32\bin\sort --unique -ooutfile.csv infile.csv
3. leer y escribir outfile.csv una copia con los títulos antepone

Para cada uno de los pasos 1 & 3, puede usar una secuencia de comandos de Python o algunas de las otras utilidades GnuWin32 (cabeza, cola, tee, cat, ...).

Answer 4

Su solución original es ligeramente incorrecta: puede tener hashing de diferentes líneas con el mismo valor (una colisión hash), y su código dejaría una de ellas.

En términos de complejidad algorítmica, si espera relativamente pocos duplicados, creo que la solución más rápida sería escanear el archivo línea por línea, agregar el hash de cada línea (como lo hizo), pero también almacenar el ubicación de esa línea. Luego, cuando encuentre un hash duplicado, busque el lugar original para asegurarse de que sea un duplicado y no solo una colisión hash, y si es así, busque y omita la línea.

Por cierto, si los valores de CSV están normalizados (es decir, los registros se consideran iguales si las filas de CSV correspondientes son equivalentes byte por byte), no necesita involucrar aquí el análisis de CSV, solo trate con texto sin formato líneas.

Answer 5

Como supongo que tendrás que hacer esto de forma regular (o habrías pirateado una secuencia de comandos), y mencionaste que te interesaba una solución teórica, esta es una posibilidad.

Lea las líneas de entrada en B-Trees, ordenadas por el valor hash de cada línea de entrada, y escríbalas en el disco cuando se llene la memoria. Nos ocupamos de almacenar, en los B-Trees, las líneas originales unidas al hash (como conjunto, ya que solo nos importan las líneas únicas). Cuando leemos un elemento duplicado, verificamos las líneas establecidas en el elemento almacenado y lo agregamos si se trata de una nueva línea que pasa al hash con el mismo valor.

¿Por qué B-Trees? Requieren menos lecturas de disco cuando solo puede (o desea) leer partes de ellas en la memoria. El grado (número de hijos) en cada nodo depende de la memoria disponible y el número de líneas, pero no desea tener demasiados nodos.

Una vez que tenemos esos B-Trees en el disco, comparamos el elemento más bajo de cada uno de ellos. Eliminamos el más bajo de todos, de todos los B-Trees que lo tienen. Fusionamos sus conjuntos de líneas, lo que significa que no tenemos duplicados para esas líneas (y también que no tenemos más líneas que hash para ese valor). Luego escribimos las líneas de esta fusión en la estructura csv de salida.

Podemos separar la mitad de la memoria para leer los B-Trees, y la mitad para mantener la salida csv en la memoria durante un tiempo. Descargamos el csv al disco cuando su mitad está llena, añadiendo lo que ya se ha escrito. La cantidad de cada B-Tree que leemos en cada paso se puede calcular aproximadamente por (available_memory/2)/number_of_btrees, redondeando para que podamos leer los nodos completos.

En pseudo-Python:

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) 

Answer 6

Cómo sobre el uso del módulo heapq para leer fragmentos de archivo hasta el límite de memoria y escribir a cabo las piezas clasificadas (heapq mantiene las cosas siempre en el orden de clasificación).

O podría tomar la primera palabra en línea y dividir el archivo en pedazos por eso. Luego puede leer las líneas (tal vez hacer '' .join (line.split()) para unificar las separaciones/pestañas en línea si está bien cambiar el espaciado) en orden alfabético despejando el conjunto entre las piezas (el conjunto elimina duplicados) para ordenar las cosas a medias (el conjunto no está en orden, si lo deseas puedes leerlo para almacenar y escribir para obtener el orden ordenado, la última ocurrencia en el juego reemplazando los valores anteriores sobre la marcha) Alternativamente también puedes ordenar la pieza y elimine las líneas duplicadas con la solución groupby de Joe Koberg. Por último, puede unir las piezas (por supuesto, puede escribir a medida que avance el archivo final durante la clasificación de las piezas)