数据复制优化

Question

我在python3的清洁数据工作。我有大量的midi文件使用beautiful soup从各种来源中抓取。许多文件可能是重复的音乐作品。我可以改变midis的键，使它们是相同的，并将乐器转换为钢琴(它们是单声道文件)。

因此，应该可以检查歌曲内容(在midi编码方面)是否类似。它特别紧迫，因为有些文件上只有数字作为名称。因此，要明确的是，我必须检查文件的内容是否重复。另外，我不是在寻找精确的匹配，我只是在寻找百分之几的相似性。

我目前的方法是使用Difflib中的SequenceMatcher。我正在检查每个单独文件上600的缓冲区是否有一个SequenceMatcher比率>9，然后，我标记它们，这样我就可以通过听它们来比较它们。

这种方法适用于midi格式歌曲的测试场景。然而，它是极其缓慢的。所以，我想知道是否有人曾经面对过这个问题。除了散列(我不是在寻找确切的文件匹配)之外，还有人能提供任何关于优化这个算法的洞察力来比较文件或并行代码以获得速度或任何其他方法吗？任何帮助都将不胜感激。

这是我的代码：

import sys
import os
import hashlib
from difflib import SequenceMatcher

def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

count=0
for dirName, subdirs, fileList in os.walk('path to my directory of files'):
    print('Scanning %s...' % dirName)
    for filename in fileList:
        path = os.path.join(dirName, filename)
        in_file = open(path, 'rb')  # Provide a path to disk or ISO image
        data = in_file.read(600)
        in_file.close()
        for filename2 in fileList:
            path = os.path.join(dirName, filename2)
            in_file2 = open(path, 'rb')
            data2 = in_file2.read(600)
            in_file2.close()
            if filename==filename2:
                pass
            else:
                s=similar(data,data2)
                if s>0.9:
                    print(filename +filename2+" "+str(s))

`

Answer 1

如果您只为文件寻找相同的副本，那么您可以在每个文件上计算像md5sum这样的散列并进行比较，这比分析内容要快得多。

如果您正在寻找一个相似性度量，那么我认为您应该能够使用比SequenceMatcher使用的算法更快的算法，该算法找到最长的精确匹配序列，平均需要二次匹配时间。我建议您查看其他的相似性度量，例如Levenshtein或Hamming距离，这将更快地计算。