python - 对大量文件进行近乎重复检查的最佳方法或算法？

Question

我正在使用 python 来接近大量文件(超过 20000 个)文件。总计约300MB

当前的方法是使用 difflib 的 SequenceMatcher 进行近似重复检查，并使用 QuickRatio 获取结果。

使用 4 个工作进程需要 25 个小时才能完成工作，速度相当慢。

我还尝试了 Livenstheine，它提供了 C 基础的近乎欺骗检查，但它比 difflib 更慢且更不准确。

检查需要以这种方式完成:一个文件夹中有20000个文件。每次迭代时，每个文件都需要与文件夹中的 20000 个文件进行比较。所以将会有 20000 * 20000 次迭代。

我想到的是索引所有文件并比较索引，但我对索引很陌生，我不确定它是否有效。如果是这样的话，最好的索引选项是什么？

谢谢。

下面是代码:

import os,sys,chardet, csv,operator,time,subprocess
from difflib import SequenceMatcher
import threading
#from threading import Timer
import multiprocessing
from multiprocessing import Pool

OrgFile = ""
mark = int(sys.argv[2])

def init_logger():
    print "Starting %s" % multiprocessing.current_process().name

#----Get_Near_DupeStatus--------#
def Get_Near_DupeStatus(score):
    if score > 30 and score <= 50:
        return "Low Inclusive"
    elif score > 50 and score <= 75:
        return "Inclusive"
    elif score > 75 and score <= 85:
        return "Most Inclusive"
    elif score > 85 and score <= 99:
        return "Near-Dupe"
    elif score == 100:
        return "Unique"
    else: return "No Inclusive"

#----Write_To_CSV --- ALL-------#
def Write_To_CSV_All(List):
    writer = csv.writer(open('./TableList.csv','wb'),delimiter=';', quotechar=' ', quoting=csv.QUOTE_MINIMAL)
    writer.writerow(['Path/FileName(Source);'+'ID;'+'NearDupeID;'+'Similarity Score;'+'Near_DupeStatus;'+'NearDupeProcess(Y/N);'+'Encoding'])
    for i,li in enumerate(sorted(List, key=operator.itemgetter("NearDupeID"))):
        writer.writerow([li['Path/FileName(Source)']+";"+'ID00'+str(i+1)+";"+str(li['NearDupeID'])+";"+str(li['Similarity Score'])+";"+li['Near_DupeStatus']+";"+li['NearDupeProcess(Y/N)']+";"+li['Encoding']])

#Get Finish File List
def Finish_Files(List,count,id):
    finish_files = []
    for i,li in enumerate(sorted(List, key=operator.itemgetter("Similarity Score"), reverse=True)):
        if i < count:
            li['NearDupeID'] = id
            finish_files.append(li)
        if count == 0:
            li['NearDupeID'] = id
#            if li['Similarity Score'] > 50:
            finish_files.append(li)
    return finish_files

#----Search Files in Dir--------#
def GetFileListFrom_Dir(dir):
    FileList = []
    for root,dirs,filenames in os.walk(dir):
        for filename in filenames:
            realpath = os.path.join(root, filename)
            FileList.append(realpath)
    return FileList

#----Matcher--------#
def Matcher(realpath):
    junk = ["\t","\n","\r"]
    score = 0
    dict = {}
    MatchFile = ""
    dupe_Process = 'N'
    if os.path.isfile(realpath):
        MatchFile =  open(realpath).read()
        matcher = SequenceMatcher(lambda x: x in junk,OrgFile, MatchFile)
        score = int(matcher.ratio()*100)
        if score >= mark:
            encoding = chardet.detect(MatchFile)['encoding']
            if encoding == None: encoding = 'None'
            if score > 85: dupe_Process = 'Y'
            dict = {'Path/FileName(Source)':realpath,'Similarity Score':score,'Near_DupeStatus':Get_Near_DupeStatus(score),'NearDupeProcess(Y/N)':dupe_Process,'Encoding':encoding}
            return dict

#-------------Pooling--------------------#
def MatcherPooling(FileList,orgFile,process):
    global OrgFile
    OrgFile = open(orgFile).read()
    pool_obj = Pool(processes=process)
    #pool_obj = Pool(processes=process,initializer=init_logger)
    dict = {}
    DictList = []
    dict = pool_obj.map(Matcher,FileList)
    DictList.append(dict)
    pool_obj.close()
    pool_obj.join()
    return DictList

def Progress():
    p = "/-\\|"
#    global t
    for s in p:
        time.sleep(0.1)
        sys.stdout.write("%c" % s)
        sys.stdout.flush()
        sys.stdout.write('\b')
    t2 = threading.Timer(0.1,Progress).start()
#    t.start()


#----Main--------#
def Main():
    Mainls = []
    dictList = []
    finish_List = []
    BLINK = '\033[05m'
    NOBLINK = '\033[25m'
    dir = sys.argv[1]
    process = int(sys.argv[3])
    Top_rec = int(sys.argv[4])
    Mainls = GetFileListFrom_Dir(dir)
    bar = "*"
    # setup toolbar
    sys.stdout.write("%s" % BLINK+"Processing...."+ NOBLINK + "With "+ str(process) + " Multi Process...")#+" \n")
    if Top_rec != 0:
        charwidth = len(Mainls)/Top_rec
    elif Top_rec == 0: charwidth = len(Mainls)
    t = threading.Timer(0.1,Progress)
    t.start()
#    sys.stdout.write("[%s]" % ("-" * charwidth))
#    sys.stdout.flush()
#    sys.stdout.write("\b" * (charwidth+1)) # return to start of line, after '['

    #----------------------------------------------------------#
    for id,orgFile in enumerate(sorted(Mainls)):
        for dl in MatcherPooling(sorted(Mainls),orgFile,process):
            for dict in dl:
                if dict != None:
                    dictList.append(dict)

            #Append Finish Files List For CSV ALL(Write Once)
            fl = Finish_Files(dictList,Top_rec,id+1)
            if Top_rec != 0:
                for del_List in fl:
                    Mainls.remove(del_List['Path/FileName(Source)'])
                    Mainls.sort()

            finish_List.extend(fl)
            dictList = []

        sys.stdout.write("%s" % bar)
        sys.stdout.flush()

        #Exit Loop
        if len(Mainls) == 0:
            break
    #----------------------------------------------------------#
    Write_To_CSV_All(finish_List)
    #print os.system('clear')
    sys.stdout.write("%s" % " ")
    print "Finished!"
    t.cancel()
    print os._exit(99)

if __name__ == '__main__':
    Main()

Answer 1

部分答案，但一个明显的优化是仅比较大小大致相同的文件。此外，比较文件 a 和文件 b 与比较 b 和 a 相同:20000 个文件可进行 20000 * (20000-1)/2 次比较。300MB并不算大，你可以尝试先读入所有文件。

在索引方面，它只是用一个或多个数字来描述每个文件。大小为一。非空白、空白或换行符的数量可以是其他。如果文件都包含相同类型的数据，您可以解释数据以创建更有用的数字。此外，完全相同的文件将具有相同的 SHA-256 哈希值。仅当文件的很大一部分相同时这才会有帮助。

import hashlib
m = hashlib.sha256()
m.update(file_contents)
this_files_hash_value=m.digest()

不幸的是，我想不出任何方法可以完全准确且正确地对 difflib.SequenceMatcher 所做的(部分)分解，因为它动态比较输入文件的所有可能 block 。