The docstring in group_equivalent_files should be self-explanatory for what I'm trying to do. I'm specifically trying to group by equivalent files as opposed to just finding pairs of equivalent files.
Filesystem with only hello1.txt and hello2.txt equivalent:
ls ./ hello1.txt foo.txt dir_one ls ./dir_one hello2.txt bar.txt
Pointing out any potential improvements or errors would be really appreciated. I'm most hesitant about my implementation of group_by_equality. The files could be compared in chunks, and I'm thinking that the File class might be unnecessary.
import collections import hashlib import itertools import os import os.path def group_equivalent_files(): """ Overview: Find all groups of files under pwd whose byte contents are exactly equivalent. pwd is understood to be directory from which this script was run. The filenames of equivalent files are printed to stdout. Algorithm: group_equivalent_files attempts to successively group files. First by file size. Then by a hash of each file's first 100 bytes. The remaining, possibly equivalent files are then checked byte by byte for equivalency. The goal is to generally minimize the total number of bytes read and compared. Assumptions: - the combined size of all the files under pwd can fit into RAM Example: Filesystem with only hello1.txt and hello2.txt equivalent: ls ./ hello1.txt foo.txt dir_one ls ./dir_one hello2.txt bar.txt Expected Output: [['./hello1.txt', 'dir_one/hello2.txt'] """ def walk_files(): """ Recursively walk through and process every file underneath pwd. Also group processed files by file size. Return a dictionary of all the files, with file size as the key and a list of filenames with the associated size as the value """ files_by_size = collections.defaultdict(list) for root, _, files in os.walk("."): for filename in files: full_filename = os.path.join(root, filename) files_by_size[os.path.getsize(full_filename)].append( full_filename) return files_by_size def get_n_bytes(filename, n): """ Return the first n bytes of filename in a bytes object. If n is -1 or greater than size of the file, return all of the file's bytes. """ in_file = open(filename, "rb") file_contents = in_file.read(n) in_file.close() return file_contents def group_by_hash(files_by_size): """ files_by_size is a dictionary with file size as key and a list of associated full filenames as value Group by the files referred to in files_by_size according to hash of file's first 100 bytes. Return dictionary with file hash as key and list of associated files as value. """ def get_hash(file_contents): return hashlib.sha256(file_contents).digest() files_by_hash = collections.defaultdict(list) for file_size, files in files_by_size.items(): for filename in files: file_hash = get_hash(get_n_bytes(filename, 100)) files_by_hash[file_hash].append(filename) return files_by_hash def group_by_equality(files_by_hash): """ files_by_hash is a dictionary with file hash as key and list of associated files as value. Group the files referred to in files_by_hash according to byte equality. Return list of lists of filenames whose entire byte contents are exactly equivalent. """ class File(): def __init__(self, filename, file_contents): self.filename = filename self.file_contents = file_contents def __eq__(self, other): return self.file_contents == other.file_contents files_by_equality = list() for file_hash, filenames in files_by_hash.items(): files = [ File(filename, get_n_bytes(filename, -1)) for filename in filenames] for i, g in itertools.groupby(files): equal_files = list(g) if len(equal_files) >= 2: files_by_equality.append([f.filename for f in equal_files]) return files_by_equality files_by_size = walk_files() files_by_hash = group_by_hash(files_by_size) equal_files = group_by_equality(files_by_hash) print(equal_files) group_equivalent_files()