通过hashlib找到重复文件？

Question

我知道以前有人问过这个问题，我看到了一些答案，但这个问题更多的是关于我的代码，以及完成这个任务的最佳方式。

我想扫描一个目录，看看目录中是否有任何重复的(通过检查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)再次扫描目录，并对照文本文件.

我知道这不是一个很好的方法，也不起作用。“匹配”只打印出处理过的最后一个文件。

我如何才能让这个脚本真正找到副本呢？有人能告诉我一种更好/更容易的方法来完成这个任务吗？

非常感谢您的帮助。对不起，这是个很长的邮筒。

Answer 1

识别重复项的明显工具是哈希表。除非您正在处理大量的文件，否则您可以这样做：

from collections import defaultdict

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

在此过程结束时，file_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可以使用MD5s；也可以像Ramchandra在上面的注释中建议的那样，简单地获取文件的第一个和最后一个字节；或者，它可以像上面注释中建议的那样使用文件大小。但后两种策略中的每一种都更有可能产生假阳性。你可以结合它们来降低假阳性率。

如果您正在处理大量的文件，您可以使用更复杂的数据结构，比如布卢姆滤波器。

Answer 2

@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)大小不是‘50000000’

您的原始代码在8192 (8 KiB)增量中读取，这对于现代系统来说非常小。你可能会得到更好的表现，抓住更多在一次。1024*1024是1048576 (1 MiB)字节，只是一个合理的猜测。至于为什么我用一种奇怪的方式写它，1000 (十进制千字节)受到人们的喜爱，而1024 (二进制基字节)则被计算机和文件系统所喜爱。我有写some_number*1024的习惯，所以很容易看出我是在引用一个KiB增量。5000000也是一个合理的数字，但是您应该考虑5*1024*1024 (即5 MiB)，这样您就可以得到与文件系统很好地对齐的东西。

2)这个位到底是做什么的: size_map =defaultdict(列表)

它创建了一个“defaultdict”，它为一个普通的dict对象添加了功能。当KeyError异常被不存在的键索引时，常规dict会引发该异常。defaultdict创建一个默认值，并将该键/值对添加到dict中。在我们的例子中，size_map[some_size]说：“给我some_size文件的列表，如果没有，创建一个新的空列表”。

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.argv1 --我猜sys.argv1只是让python py.py ' filepath‘参数起作用了( argv1在哪里？)

是的，当您调用python脚本时，sys.argv是脚本的名称，sys.argv1：是命令行上给出的任何附加参数。在编写脚本时，我使用sys.argv1作为测试脚本的一种快速方法，您应该修改它以满足您的需要。

Answer 3

您要做的第一件事是在遍历文件时将h_md5保存到列表中。类似于：

h_md5=[]

在你浏览你的目录之前。和

h_md5.append(getFileHashMD5(fullname))

在你的圈子里。现在，您可以将散列列表与输出文件进行比较，而不是简单地在循环中创建最后一个哈希列表。

而且，很明显，使用当前代码，每次都会为每个文件找到一个匹配项，因为您将在列表中找到该特定文件本身的散列。因此，如果您想要查找重复项，则必须查找两个不同匹配项的实例。

编辑:上面的答案@senderle是一个更好的方法，如果你愿意改变你的代码。