1

我正在使用 python 来复制大量文件（超过 20000 个）文件。总计约 300 MB

当前的方法是使用 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()
4

4 回答 4

3

部分答案，但一个明显的优化是只比较大小大致相同的文件。同样比较文件 a 和文件 b 与比较 b 和 a 相同：20000 个文件给出 20000 * (20000-1)/2 次比较。300 MB 不是很大，你可以先尝试读入所有文件。

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

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

不幸的是，我想不出任何方法可以完全准确和正确地分解（部分）所做的事情，difflib.SequenceMatcher因为它正在动态比较输入文件的所有可能块。

于 2012-02-29T08:20:39.453 回答
0

正如这里提到的，我将首先比较大小相对接近或 MIME 类型相似的文件。

然后我会继续比较一小部分数据以立即排除大多数情况。一个好的算法将从一小部分文件开始，比较它，如果足够相似，将大小增加 2 倍（或更多），依此类推，直到您完成所有比较，或直到任何阶段相似因子太低。

这意味着前 1-2 次迭代可能会排除大多数文件。

于 2012-02-29T08:30:16.320 回答
0

如果您处理大型收藏，并且您不仅希望在基于文本的文件（PDF、DOC、HTML 等）中找到重复项，而且还希望找到接近重复项，您可能需要考虑以下内容： http://softcorporation .com/products/neardup/ 它是基于 Java 的，因此可以在不同的平台上工作，您可以免费下载。

于 2013-04-07T19:48:01.127 回答
0

首先，您应该知道您的程序是否尽可能快。

  • Time 比较两个文件所需的平均执行时间。只是比较它们，不要使用多处理，不要索引任何内容，不要写入 csv 任何内容。
  • 乘以20000 x 10000 / 4（因为你有 4 个工人）
  • 将您获得的结果与当前 25 小时的结果进行比较。

我相信这是一个非常重要的测试，因为它将显示您当前的比较算法是否还有改进的空间。

如果还有改进的余地，那就开始吧！因为一旦您有了优化的程序，您就可以继续前进并开始寻找更好的比较解决方案。

如果您想就如何做到这一点寻求帮助，您必须提供一个更具可读性的代码示例（并且简短），因为您现在无法处理现有的内容。

于 2012-03-01T15:55:42.327 回答