2

我知道之前有人问过这个问题,并且我已经看到了一些答案,但是这个问题更多的是关于我的代码和完成这项任务的最佳方式。

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

我看到这不是一个好方法而且它不起作用。“匹配”只是打印出最后一个处理的文件。

我怎样才能让这个脚本真正找到重复项?有人可以告诉我完成这项任务的更好/更简单的方法。

非常感谢您的帮助。对不起,这是一个很长的帖子。

4

3 回答 3

5

识别重复项的明显工具是哈希表。除非您正在处理大量文件,否则您可以执行以下操作:

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;或者它可以像 Ramchandra Apte 在上面的评论中建议的那样简单地获取文件的第一个和最后一个字节;或者它可以简单地使用上面评论中建议的文件大小。不过,后两种策略中的每一种都更有可能产生误报。您可以将它们结合起来以降低误报率。

如果您正在处理大量文件,则可以使用更复杂的数据结构,例如Bloom Filter

于 2013-09-10T16:51:54.427 回答
3

@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 KiB) 为增量读取,这对于现代系统来说非常小。通过一次抓取更多,您可能会获得更好的性能。1024*1024 是 1048576 (1 MiB) 字节,只是对合理数字的猜测。至于为什么我写得这么奇怪,1000(十进制千字节)被人们所喜爱,而1024(二进制千字节)却被计算机和文件系统所喜爱。我有写作的习惯,some_number*1024所以很容易看出我指的是 1 KiB 增量。5000000 也是一个合理的数字,但您应该考虑 5*1024*1024(即 5 MiB),以便获得与文件系统完美对齐的东西。

2)这个位究竟做了什么: size_map = defaultdict(list)

它创建了一个“defaultdict”,它将功能添加到常规 dict 对象。当一个普通的字典被一个不存在的键索引时,它会引发一个 KeyError 异常。defaultdict 创建一个默认值并将该键/值对添加到 dict 中。在我们的例子中,size_map[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.argv[1] 我猜 sys.argv[1] 只是让 python py.py 'filepath' 参数起作用(文件路径是 argv[1] 吗?

是的,当您调用 python 脚本时,sys.argv[0] 是脚本的名称,而 sys.argv[1:](arg 1 及以下)是命令行中给出的任何附加参数。我在编写脚本时使用 sys.argv[1] 作为测试脚本的快速方法,您应该更改它以满足您的需要。

于 2013-09-10T17:23:57.643 回答
0

您要做的第一件事是在循环浏览文件时将 h_md5 保存到列表中。就像是:

h_md5=[]

在你遍历你的目录之前。和

h_md5.append(getFileHashMD5(fullname))

在你的循环里面。现在您有了一个哈希列表来与您的输出文件进行比较,而不仅仅是您在循环中创建的最后一个。

此外,显然,使用您当前的代码,您每次都会为每个文件找到一个匹配项,因为您会在列表中找到该特定文件本身的哈希值。因此,如果您想查找重复项,您将不得不查找找到两个不同匹配项的实例。

编辑:如果您愿意更改代码,@senderle 上面的答案是一种更好的方法。

于 2013-09-10T16:45:23.700 回答