使用Multi-processing和ssdeep Python对类似文件进行分组时出现问题

Question

我正在尝试使用deephash（SSDEEP）http://code.google.com/p/pyssdeep处理超过130万个文件

它的作用是，。它生成散列（在3-6分钟内生成130万），然后相互比较以获得相似性结果。比较速度很快，但仅仅运行一个进程并不能产生效果结束。所以我们加入了Python多处理模块来完成任务。在

结果是130万个文本文件在30分钟内完成。使用18核（四核至强处理器，。总共24个CPU）

以下是每个过程的工作原理：

• 生成SSDEEP和。在
• 把这些总数分成5000组。在
• 比较18个过程中的每个块1和5000:18个迭代的总和。在
• 根据相似性得分对结果进行分组（默认值为75）
• 已删除为下一次迭代检查的文件。在
• 从下一个文件开始，下一个组的分数为<；75%
• 重复上述步骤，直到所有小组都完成。在
• 若有未包含的文件（与任何文件不相似），则将它们添加到剩余列表中。在

当所有处理完成后，剩余的文件将被合并并递归地相互比较，直到没有结果。在

问题是，当文件列表被分成更小（5000）个文件时。有些文件包含在前5000个块中，但未包含在另一个组中，从而使组不完整。在

如果我在不分块的情况下运行，那么循环需要很长时间才能完成。超过18小时而未完成，。不知道多久。在

请告诉我。在

使用的模块：多处理.池，深Python

def ssdpComparer(lst, threshold):
    s = ssdeep()
    check_file = []
    result_data = []
    lst1 = lst
    set_lst = set(lst)

    print '>>>START'
    for tup1 in lst1:
        if tup1 in check_file:
            continue
        for tup2 in set_lst:
            score = s.compare(tup1[0], tup2[0])
            if score >= threshold:
                result_data.append((score, tup1[2], tup2[2])) #Score, GroupID, FileID
                check_file.append(tup2)
        set_lst = set_lst.difference(check_file)
    print """####### DONE #######"""
    remain_lst = set(lst).difference(check_file)

    return (result_data, remain_lst)



def parallelProcessing(tochunk_list, total_processes, threshold, source_path, mode, REMAINING_LEN = 0):
    result = []
    remainining = []
    pooled_lst = []
    pair = []
    chunks_toprocess = []

    print 'Total Files:', len(tochunk_list)

    if mode == MODE_INTENSIVE:
        chunks_toprocess = groupWithBlockID(tochunk_list) #blockID chunks
    elif mode == MODE_THOROUGH:
        chunks_toprocess = groupSafeLimit(tochunk_list, TOTAL_PROCESSES) #Chunks by processes
    elif mode == MODE_FAST:
        chunks_toprocess = groupSafeLimit(tochunk_list) #5000 chunks

    print 'No. of files group to process: %d' % (len(chunks_toprocess))
    pool_obj = Pool(processes = total_processes, initializer = poolInitializer, initargs = [None, threshold, source_path, mode])
    pooled_lst = pool_obj.map(matchingProcess, chunks_toprocess) #chunks_toprocess
    tmp_rs, tmp_rm = getResultAndRemainingLists(pooled_lst)
    result += tmp_rs
    remainining += tmp_rm

    print 'RESULT LEN: %s, REMAINING LEN: %s, P.R.L: %s' % (len(result), len(remainining), REMAINING_LEN)
    tmp_r_len = len(remainining)

    if tmp_r_len != REMAINING_LEN and len(result) > 0 :
        result += parallelProcessing(remainining, total_processes, threshold, source_path, mode, tmp_r_len)
    else:
        result += [('','', rf[2]) for rf in remainining]

    return result

def getResultAndRemainingLists(pooled_lst):
    g_result = []
    g_remaining = []

    for tup_result in pooled_lst:
        tmp_result, tmp_remaining = tup_result
        g_result += tmp_result
        if tmp_remaining:
            g_remaining += tmp_remaining

    return (g_result, g_remaining)

Answer 1

第一条建议：在您的情况下，没有必要让check_fileas list=>；将其更改为set（）-那么它应该更好（在末尾解释）。在

如果你需要块，也许这样的程序就足够了：

def split_to_chunks(wholeFileList):
    s = ssdeep()
    calculated_chunks = []
    for someFileId in wholeFileList:
        for chunk in calculated_chunks:
            if s.compare(chunk[0], someFileId) > threshold:
                chunk.append(someFileId)
                break
        else: # important: this else is on 'for ' level
            # so if there was no 'break' so someFileId is a base for new chunk:
            calculated_chunks.append( [someFileId] )
    return calculated_chunks

之后，您可以过滤结果： 组=过滤器（λx:len（x）>1，结果） 剩余=过滤器（λx:len（x）==1，结果）

注意：这个算法假设chunk的第一个元素是“base”。结果的好坏很大程度上取决于ssdeep的行为（我可以想象出一个奇怪的问题：ssdeep有多少是可传递的？）如果这种相似性，那么它应该是。。。在

最坏的情况是如果任何一对s.compare（fileId1，fileId2）的分数不满足阈值条件（那么复杂度是n^2，所以在您的例子中是1.3mln*1.3mln）。在

没有简单的方法来优化这个案例。让我们想象一下这样的情况：s.compare（file1，file2）总是接近于0，那么（据我所知），即使您知道s.compare（A，B）非常低，而s.compare（B，C）非常低，那么您仍然不能说s.compare（A，C）=>；所以您需要进行n*n个操作。在

另一个注意事项：假设您使用了太多的结构和列表，例如：

^{pr2}$

此指令create new set（），并且set_lst和check_file中的所有元素都必须至少接触一次，因为check_file是一个列表，因此无法优化“difference”函数，因此它具有复杂性：len（check_file）*log（len（set_lst））

基本上：如果这些结构在增长（130万，差不多），那么你的计算机需要执行更多的计算。如果使用check_file=set（）而不是[]（list），那么它的复杂性应该是：len（set_lst）+len（check_file）

检查元素是否在python的列表（数组）中也是一样：

if tup1 in check_file:

因为check_fileis list->如果tup1不在列表中，您的cpu需要将tup1与所有元素进行比较，因此复杂性为len（check_file） 如果您将check_file更改为set，那么复杂度大约为log2（len（check_file）） 让差异变得更直观，假设len（*check_file*）=1mln，您需要多少比较？？在

集合：log2（1mln）=log2（1000000）~20

列表：len（check_file）=1mln