python - Encontrar archivos duplicados a través de hashlib?

file duplicates

Question

Sé que esta pregunta ya se hizo antes, y he visto algunas de las respuestas, pero esta pregunta es más sobre mi código y la mejor manera de lograr esta tarea.

Quiero escanear un directorio y ver si hay algún duplicado (verificando hashes MD5) en ese directorio. El siguiente es mi código:

import sys
import os
import hashlib

fileSliceLimitation = 5000000 #bytes

# if the file is big, slice trick to avoid to load the whole file into RAM
def getFileHashMD5(filename):
     retval = 0;
     filesize = os.path.getsize(filename)

     if filesize > fileSliceLimitation:
        with open(filename, ''rb'') as fh:
          m = hashlib.md5()
          while True:
            data = fh.read(8192)
            if not data:
                break
            m.update(data)
          retval = m.hexdigest()

     else:
        retval = hashlib.md5(open(filename, ''rb'').read()).hexdigest()

     return retval

searchdirpath = raw_input("Type directory you wish to search: ")
print ""
print ""    
text_file = open(''outPut.txt'', ''w'')

for dirname, dirnames, filenames in os.walk(searchdirpath):
    # print path to all filenames.
    for filename in filenames:
        fullname = os.path.join(dirname, filename)
        h_md5 = getFileHashMD5 (fullname)
        print h_md5 + " " + fullname
        text_file.write("/n" + h_md5 + " " + fullname)   

# close txt file
text_file.close()


print "/n/n/nReading outPut:"
text_file = open(''outPut.txt'', ''r'')

myListOfHashes = text_file.read()

if h_md5 in myListOfHashes:
    print ''Match: '' + " " + fullname

Esto me da el siguiente resultado:

Please type in directory you wish to search using above syntax: /Users/bubble/Desktop/aF

033808bb457f622b05096c2f7699857v /Users/bubble/Desktop/aF/.DS_Store
409d8c1727960fddb7c8b915a76ebd35 /Users/bubble/Desktop/aF/script copy.py
409d8c1727960fddb7c8b915a76ebd25 /Users/bubble/Desktop/aF/script.py
e9289295caefef66eaf3a4dffc4fe11c /Users/bubble/Desktop/aF/simpsons.mov

Reading outPut:
Match:  /Users/bubble/Desktop/aF/simpsons.mov

Mi idea fue:

1) Escanear directorio 2) Escribir hashes MD5 + Nombre de archivo a archivo de texto 3) Abrir archivo de texto como de solo lectura 4) Escanear directorio OTRA VEZ y verificar contra archivo de texto ...

Veo que esta no es una buena manera de hacerlo Y no funciona. La ''coincidencia'' simplemente imprime el último archivo que se procesó.

¿Cómo puedo obtener este script para encontrar realmente duplicados? ¿Puede alguien decirme una forma mejor / más fácil de lograr esta tarea?

Muchas gracias por cualquier ayuda. Lo siento, esta es una publicación larga.

Answer 1

Lo primero que querrá hacer es guardar los h_md5 en una lista mientras recorre sus archivos. Algo como:

h_md5=[]

antes de recorrer su directorio. Y

h_md5.append(getFileHashMD5(fullname))

dentro de tu lazo Ahora tiene una lista de hashes para comparar con su archivo de salida en lugar de simplemente el último que hizo en su ciclo.

Además, obviamente, con su código actual, encontrará una coincidencia para cada archivo cada vez, porque encontrará hash para ese archivo en particular en su lista. Entonces, si desea buscar duplicados, tendrá que buscar instancias donde se encuentren dos coincidencias distintas.

editar: la respuesta anterior @senderle es una forma mucho mejor de hacerlo si estás dispuesto a cambiar tu código.

Answer 2

@senderle tiene una gran respuesta, pero como mencionó que mi solución generará falsos positivos, calculé que el guantelete había sido colocado y sería mejor que mostrara algún código. Reduje la función md5 (siempre debe usar el caso ''fileSliceLimitation'' y debe ser menos tacaño con su búfer de entrada), luego se filtra previamente por tamaño antes de hacer md5s.

import sys
import os
import hashlib
from collections import defaultdict

searchdirpath = sys.argv[1]

size_map = defaultdict(list)

def getFileHashMD5(filename):
    m = hashlib.md5()
    with open(filename, ''rb'', 1024*1024) as fh:
          while True:
            data = fh.read(1024*1024)
            if not data:
                break
            m.update(data)
    return m.hexdigest()

# group files by size
for dirname, dirnames, filenames in os.walk(searchdirpath):
    for filename in filenames:
        fullname = os.path.join(dirname, filename)
        size_map[os.stat(fullname).st_size].append(fullname)

# scan files of same size
for fullnames in size_map.itervalues():
    if len(fullnames) > 0:
        hash_map = defaultdict(list)
        for fullname in fullnames:
            hash_map[getFileHashMD5(fullname)].append(fullname)
        for fullnames in hash_map.itervalues():
            if len(fullnames) > 1:
                print "duplicates:"
                for fullname in fullnames:
                    print "   ", fullname

(EDITAR)

Hubo varias preguntas sobre esta implementación que trataré de responder aquí:

1) por qué (1024 * 1024) tamaño no ''5000000''

Su código original se lee en incrementos de 8192 (8 KiB), que es muy pequeño para los sistemas modernos. Es probable que obtengas un mejor rendimiento agarrando más a la vez. 1024 * 1024 son 1048576 (1 MiB) bytes y fue solo una aproximación a un número razonable. En cuanto a por qué lo escribí de una manera tan extraña, las personas prefieren 1000 (kilobyte decimal), pero las computadoras y los sistemas de archivos adoran 1024 (kibibyte binario). Tengo la costumbre de escribir some_number*1024 por lo que es fácil ver que me refiero a incrementos de 1 KiB. 5000000 es también un número razonable, pero debería considerar 5 * 1024 * 1024 (es decir, 5 MiB) para que pueda obtener algo que esté bien alineado para el sistema de archivos.

2) qué hace exactamente este bit: size_map = defaultdict (list)

Crea un ''defaultdict'' que agrega funcionalidad a un objeto dict regular. Un dict regular plantea una excepción KeyError cuando está indexada por una clave inexistente. defaultdict crea un valor predeterminado y agrega ese par de clave / valor al dict en su lugar. En nuestro caso, size_map[some_size] dice "dame la lista de archivos de some_size y crea una nueva lista vacía si no tienes una".

size_map[os.stat(fullname).st_size].append(fullname) . Esto se divide a:

stat = os.stat(fullname)
size = stat.st_size
filelist = size_map[size]    # this is the same as:
                             #    if size not in size_map:
                             #        size_map[size] = list()
                             #    filelist = size_map[size]
filelist.append(fullname)

3) sys.argv [1] Supongo que sys.argv [1] simplemente hace que el argumento python py.py ''filepath'' funcione (¿dónde filepath es el argv [1]?

Sí, cuando llamas a un script de python, sys.argv [0] es el nombre del script y sys.argv [1:] (arg 1 y siguientes) son argumentos adicionales dados en la línea de comando. Utilicé sys.argv [1] como una forma rápida de probar el script cuando lo escribí y debe cambiarlo para satisfacer sus necesidades.

Answer 3

La herramienta obvia para identificar duplicados es una tabla hash. A menos que trabaje con una gran cantidad de archivos, podría hacer algo como esto:

from collections import defaultdict

file_dict = defaultdict(list)
for filename in files:
    file_dict[get_file_hash(filename)].append(filename)

Al final de este proceso, file_dict contendrá una lista para cada hash único; cuando dos archivos tienen el mismo hash, ambos aparecerán en la lista para ese hash. Luego, filtra el dict buscando listas de valores de más de 1, y compara los archivos para asegurarte de que son iguales, algo como esto:

for duplicates in file_dict.values():   # file_dict.itervalues() in Python 2
    if len(duplicates) > 1:
        # double-check reported duplicates and generate output

O esto:

duplicates = [files for files in file_dict.values() if len(files) > 1]

get_file_hash podría usar MD5s; o simplemente podría obtener el primer y último byte del archivo como Ramchandra Apte sugirió en los comentarios anteriores; o simplemente podría usar tamaños de archivo como sugirió tdelaney en los comentarios anteriores. Sin embargo, cada una de las últimas dos estrategias tiene más probabilidades de producir falsos positivos. Puede combinarlos para reducir la tasa de falsos positivos.

Si está trabajando con una gran cantidad de archivos, podría utilizar una estructura de datos más sofisticada, como un Bloom Filter .