What's the most efficient way to check for duplicate data between multiple files?

user_10549143 0
Viewed 888

Say you have a folder with hundreds or thousands of .csv or .txt files that presumably contain different information, but you want to make sure that joe041.txt doesn't actually contain the same data as joe526.txt by accident.

Rather than loading everything into one file – which could be troublesome if each file has thousands of lines –, I've taken to using a Python script to essentially read each file in the directory and calculate a checksum that you can then compare between your thousands of files.

Is there a more efficient way to do this?

Even using filecmp for this seems to less efficient since the module only has file vs file and dir vs dir comparisons but no file vs dir commands – which means that to use it you'd have to iterate through x² times (all files in dir against all other files in dir).

import os
import hashlib

outputfile = []

for x in(os.listdir("D:/Testing/New folder")):
    with open("D:/Testing/New folder/%s" % x, "rb") as openfile:
        text=openfile.read()
        outputfile.append(x)
        outputfile.append(",")
        outputfile.append(hashlib.md5(text).hexdigest())
        outputfile.append("\n")

print(outputfile)

with open("D:/Testing/New folder/output.csv","w") as openfile:
    for x in outputfile:
        openfile.write(x)
checksum python
1 Answers

Inspired by @sɐunıɔןɐqɐp comment, you could try an iterating approach that performs cheap operations first on all the files (get the file size), and then makes more in depth comparissons on those files that have equal sizes.

This code compares first the size, then the first lines of the files and finally the md5 hash of the whole file. You can adapt it anyway you see fit for your use case.

I use long variable names to make it explicit; do not get distracted by that.

import os
import hashlib

def calc_md5(file_path):
    hash_md5 = hashlib.md5()
    with open(file_path, 'rb') as f:
        for chunk in iter(lambda: f.read(4096), b''):
            hash_md5.update(chunk)
    return hash_md5.hexdigest()

def get_duplicates_by_size(dir_path):
    files_by_size = {}

    for elem in os.listdir(dir_path):
        file_path = os.path.join(dir_path, elem)
        if os.path.isfile(file_path):
            size = os.stat(file_path).st_size

            if size not in files_by_size:
                files_by_size[size] = []
            files_by_size[size].append(file_path)

    # keep only entries with more than one file;
    # the others don't need to be kept in memory
    return {
        size: file_list
        for size, file_list in files_by_size.items()
        if len(file_list) > 1}

def get_duplicates_by_first_content(files_by_size, n_chars):
    files_by_size_and_first_content = {}

    for size, file_list in files_by_size.items():
        d = {}
        for file_path in file_list:
            with open(file_path) as f:
                first_content = f.read(n_chars)

            if first_content not in d:
                d[first_content] = []
            d[first_content].append(file_path)

        # keep only entries with more than one file;
        # the others don't need to be kept in memory
        d = {
            (size, first_content): file_list_2
            for first_content, file_list_2 in d.items()
            if len(file_list_2) > 1}
        files_by_size_and_first_content.update(d)

    return files_by_size_and_first_content

def get_duplicates_by_hash(files_by_size_and_first_content):
    files_by_size_and_first_content_and_hash = {}

    for (size, first_content), file_list in files_by_size_and_first_content.items():
        d = {}
        for file_path in file_list:
            file_hash = calc_md5(file_path)

            if file_hash not in d:
                d[file_hash] = []
            d[file_hash].append(file_path)

        # keep only entries with more than one file;
        # the others don't need to be kept in memory
        d = {
            (size, first_content, file_hash): file_list_2
            for file_hash, file_list_2 in d.items()
            if len(file_list_2) > 1}
        files_by_size_and_first_content_and_hash.update(d)

    return files_by_size_and_first_content_and_hash

if __name__ == '__main__':
    r = get_duplicates_by_size('D:/Testing/New folder')
    r = get_duplicates_by_first_content(r, 20)  # customize the number of chars to read
    r = get_duplicates_by_hash(r)

    for k, v in r.items():
        print('Key:', k)
        print('  Files:', v)
user_92256710
Related