Data duplication optimization

Question

I am working in python3 cleaning data. I have a large number of midi files scraped from a variety of sources using beautiful soup. Many of the files may be duplicate musical pieces. I can change the the keys of the midis so that they are the same and change the instrument to piano (they are monophonic files).

So, then it should be possible to check if the song content (in terms of the midi encoding) is similar. It is particularly pressing as some of the files only have numbers as names on them. So, to be clear, it is the content of the files that I have to check for duplication. Also, I am not looking for exact matches I am just looking for percent similarity.

My current approach is to use SequenceMatcher from Difflib. I am checking if a buffer of 600 on each seperate file has a SequenceMatcher ratio >.9 Then, I am flagging them so I can compare the duplicates by listening to them.

This approach works in test scenarios with songs in midi format. However, it is extremely slow. So, I am wondering if there is anyone who has faced this issue before. Can anyone offer any insight on optimizing this algorithm for comparing the files or paralleling the code to gain speed or any other approach aside from hashing (I am not looking for exact file matches). Any help would be appreciated.

Here is my code:

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

If you are looking for only for identical copies for files, then you can calculate a hash like md5sum on each file and compare that, which is much faster than analysing the content.

If you’re looking for a similarity metric then I think you should be able to use a faster algorithm than the one that SequenceMatcher uses, which finds the longest exactly matching sequence, which takes quadratic time on average. I suggest you look at other similarity metrics, such as Levenshtein or Hamming distance, which will be faster to compute.