Поиск дубликатов файлов с помощью hashlib?
Я знаю, что этот вопрос задавался ранее, и я видел некоторые ответы, но этот вопрос больше касается моего кода и лучшего способа выполнения этой задачи.
Я хочу отсканировать каталог и посмотреть, есть ли в этом каталоге дубликаты (путем проверки хэшей MD5). Вот мой код:
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
Это дает мне следующий вывод:
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
Моя идея была:
1) Сканирование каталога 2) Запись хэшей MD5 + имя файла в текстовый файл 3) Открытие текстового файла только для чтения 4) Сканирование каталога СНОВА и проверка по текстовому файлу...
Я вижу, что это не очень хороший способ сделать это, и он не работает. "Match" просто печатает самый последний файл, который был обработан.
Как я могу получить этот скрипт для поиска дубликатов? Может кто-нибудь сказать мне лучший / более простой способ выполнения этой задачи.
Большое спасибо за любую помощь. Извините, это длинный пост.
3 ответа
Очевидным инструментом для идентификации дубликатов является хеш-таблица. Если вы не работаете с очень большим количеством файлов, вы можете сделать что-то вроде этого:
from collections import defaultdict
file_dict = defaultdict(list)
for filename in files:
file_dict[get_file_hash(filename)].append(filename)
В конце этого процесса file_dict будет содержать список для каждого уникального хэша; если два файла имеют одинаковый хэш, они оба появятся в списке для этого хеша. Затем отфильтруйте dict, ища списки значений длиннее 1, и сравните файлы, чтобы убедиться, что они одинаковые - что-то вроде этого:
for duplicates in file_dict.values(): # file_dict.itervalues() in Python 2
if len(duplicates) > 1:
# double-check reported duplicates and generate output
Или это:
duplicates = [files for files in file_dict.values() if len(files) > 1]
get_file_hash может использовать MD5; или он мог бы просто получить первый и последний байт файла, как предложил Рамчандра Апте в комментариях выше; или он может просто использовать размеры файлов, как предложено tdelaney в комментариях выше. Тем не менее, каждая из двух последних стратегий с большей вероятностью дает ложные срабатывания. Вы можете объединить их, чтобы уменьшить количество ложных срабатываний.
Если вы работаете с очень большим количеством файлов, вы можете использовать более сложную структуру данных, такую как Bloom Filter.
У @senderle отличный ответ, но, поскольку он упомянул, что мое решение приведет к ложным срабатываниям, я решил, что перчатка уже проложена, и мне лучше показать код. Я разбавил вашу функцию md5 (она всегда должна использовать регистр 'fileSliceLimitation' и должен быть менее скупым со своим входным буфером), а затем предварительно отфильтрован по размеру перед выполнением 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
(РЕДАКТИРОВАТЬ)
Было несколько вопросов об этой реализации, на которые я постараюсь ответить здесь:
1) почему (1024*1024) размер не "5000000"
Ваш исходный код читается с шагом 8192 (8 КиБ), что очень мало для современных систем. Вы, вероятно, получите лучшую производительность, схватив больше сразу. 1024*1024 - это 1048576 (1 МиБ) байт, и это было лишь предположение о разумном числе. Что касается того, почему я написал это таким странным образом, 1000 (десятичный килобайт) любят люди, а 1024 (двоичный кибибайт) любят компьютеры и файловые системы. Я имею привычку писать some_number*1024 так что легко увидеть, что я использую 1 КиБ. 5000000 - это тоже разумное число, но вы должны рассмотреть 5*1024*1024 (то есть 5 МБ), чтобы получить что-то, что хорошо выровнено для файловой системы.
2) что именно делает этот бит: size_map = defaultdict(список)
Он создает "defaultdict", который добавляет функциональность к обычному объекту dict. A regular dict raises a KeyError exception when it is indexed by a non-existant key. defaultdict creates a default value and adds that key/value pair to the dict instead. В нашем случае size_map[some_size] says "give me the list of files of some_size and create a new empty list if you don't have one".
size_map[os.stat(fullname).st_size].append(fullname), Это разбивается на:
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] I'm guessing the sys.argv[1] just makes the python py.py 'filepath' argument work (where filepath is the argv[1]?
Yes, when you call a python script, sys.argv[0] is the name of the script and sys.argv[1:] (arg 1 and following) are any additional arguments given on the command line. I used sys.argv[1] as a quick way to test the script when I wrote it and you should change that to meet your needs.
Первое, что вы захотите сделать, это сохранить h_md5 в список, пока вы просматриваете ваши файлы. Что-то вроде:
h_md5=[]
прежде чем вы переберите свой каталог. А также
h_md5.append(getFileHashMD5(fullname))
внутри вашей петли. Теперь у вас есть список хэшей для сравнения с выходным файлом, а не просто последний, который вы создали в цикле.
Кроме того, очевидно, что с вашим текущим кодом вы будете находить одно совпадение для каждого файла каждый раз, потому что вы найдете хеш для этого конкретного файла в своем списке. Поэтому, если вы хотите искать дубликаты, вам придется искать случаи, когда два разных совпадения найдены.
изменить: ответ выше @senderle является гораздо лучшим способом сделать это, если вы хотите изменить свой код.