Finding duplicate files using md5sum Unix command

Question

This is an exercise from Think Python: How to Think Like a Computer Scientist

Here's its description:

In a large collection of MP3 files, there may be more than one copy of the same song, stored in different directories or with different filenames. The goal of this exercise is to search for duplicates.

1. Write a program that searches a directory and all of its subdirectories, recur‐ sively, and returns a list of complete paths for all files with a given suffix (like .mp3). Hint: os.path provides several useful functions for manipulating fileand path names.
2. To recognize duplicates, you can use md5sum to compute a “checksum” for each files. If two files have the same checksum, they probably have the same contents.
3. To double-check, you can use the Unix command diff.

Here's my solution:

import os

def run_command(cmd):
    """Runs a command in a shell.

       cmd: a string specifies a Unix command.

       Returns: a string specifies the result
       of executing the command.
       """
    filepipe = os.popen(cmd)
    result = filepipe.read()
    status = filepipe.close()

    return result

def md5_checksum(filepath):
    """Returns a string specifies the MD5 checksum of
       a given file using md5sum Unix command.

       filepath: a string specifies a file.
       """
    command = 'md5sum ' + filepath

    return run_command(command)

def md5_checksum_table(dirname, suffix):
    """Searches a directory for files with a given
       file format (a suffix) and computes their
       MD5 checksums.

       dirname: a string specifies a directory.

       suffix: a file format (e.g. .pdf or .mp3).

       Returns: a dictionary mapping from string
       works as a MD5 checksum to list of strings
       work as pathes of files have this checksum.
       """
    table = {}

    for root, sub, files in os.walk(dirname):
        for file in files:
            if file.endswith(suffix):
                filepath = os.path.join(root, file)
                checksum, filename = md5_checksum(filepath).split()
                table.setdefault(checksum, []).append(filename)

    return table

def are_identical(files_names):
    """Returns whether files in files_names
       are identical using diff Unix command.

       files_names: a list of strings specify pathes of files.
       """
    index = 1

    for filename1 in files_names:
        for filename2 in files_names[index:]:
            command = 'diff %s %s' % (filename1, filename2)
            result = run_command(command)

            if result:
                return False

        index += 1

    return True


def print_duplicates(checksums):
    """Prints pathes of files have the same MD5 checksum.

       checksums: a dictionary mapping from MD5 checksum (string) to
       list of pathes of files (strings) have share this checksum.
       """
    for checksum, filepathes in list(checksums.items()):
        if len(filepathes) > 1:
            print('Files have the checksum %s %s' % (checksum, 'are: '))

            for filepath in filepathes:
                print(filepath)

            if are_identical(filepathes):
                print('\nThey are indentical. \n')

def main():
    table = md5_checksum_table('/media/sf_Shared/', '.pdf')
    print_duplicates(table)

if __name__ == '__main__':
    main()

How can it be refactored and optimized?

Notes:

• It wasn't like that, but it worked. After reading the author's solution I refactored it and edited a lot of it.

• I'm no expert at MD5, just got the basic idea.

• I'm no expert at Unix or Linux. I use Windows, and I've tested this script using a virtual machine running Ubuntu.

• I'm a hobbyist and beginner in Python and programming.

Answer 1

Well this was a very satisfying problem, thanks for sharing!

First of all, calling external resources is expensive, there for not optimized, which you ask for. Else wise, calling external resources can be preferable if the external resource is something like shell on a platform you have control over. That's the reasons I removed them and substituted them with python built-ins. It's pretty much the only reason this code is slightly faster then yours.

I found one small error in your code. What if a file you try to hash has spaces? The problem occurs when you split the return from md5_checksum, it splits to as many values as there are white spaces.

The most time consuming function of both our code is walk. It's easy to check these where cpu-time went with profilers. And python has a builtin I like, but there are many. It's the cProfiler, check my code for usage.

The biggest change was refactoring the function are_identical for

if any(cmp(x, y) for x in paths for y in paths if y != x):
                print('\nThey are identical\n')

They do the same thing, but the any() builtin, is.. as well faster, then iterating over lists.

I did remove your function comments, as they can be substituted for good function names and annotations. Do you agree?

from os import walk
from os.path import join
from hashlib import md5
from filecmp import cmp
from base64 import b64encode
from time import time
import cProfile


def md5_checksum(file_path: str) -> (bytes, str):
    """ Returns the raw MD5 bytes here used as checksum a given files content """

    with open(file_path, "rb") as f:
        file = f.read()
    m = md5()
    m.update(file)
    return m.digest(), file_path


def md5_checksum_table(dir_name: str, suffix: str) -> {bytes: [str]}:
    """
    Searches a directory for files with a given file format (a suffix) and
      computes their MD5 checksums.
    """
    table = {}
    for root, sub, files in walk(dir_name):
        for file in files:
            if file.endswith(suffix):
                checksum, filename = md5_checksum(join(root, file))
                table.setdefault(checksum, []).append(filename)
    return table


def print_duplicates(checksums: {bytes: [str]}):
    """ Prints paths of files have the same MD5 checksum and are identical. """

    for checksum, paths in checksums.items():
        if len(paths) > 1:
            print('Files have the checksum {0} are:\n {1}'.format(b64encode(checksum),
                                                                "\n".join(paths)))
            if any(cmp(x, y) for x in paths for y in paths if y != x):
                print('\nThey are identical\n')


def main():
    start = time()
    table = md5_checksum_table('/media/sf_Shared/', '.pdf')
    print_duplicates(table)
    print("Time {:.3f}s".format(time()-start))
    cProfile.run("md5_checksum_table('/home/cly/', '.pdf')")
    cProfile.run("print_duplicates({})".format(table))



if __name__ == '__main__':
    main()

That being said, they problem statement seems foggy. The MD5 function does not yield the same hash for two different sets of data, when concerned with these kinda problems. That is way it is called a hash function or a one way function. If the hashes is identical the content is identical.

The last thing I will say, is that even the very fast hash function MD5, is slower then a efficient comparing of the content. So I criticize the problem not your solution.

Thanks! Good work.

Answer 2

These lines of code…

command = 'md5sum ' + filepath

and

command = 'diff %s %s' % (filename1, filename2)

… should make you very suspicious. In general, you should use caution anytime you compose a string (whether by concatenation or interpolation) that will be interpreted by another computer system.

@Simon mentioned the possibility of failure if a filename happens to contain a space. The bug is actually far more insidious than that: you have an arbitrary command execution vulnerability. If a file has a hostile name that contains shell metacharacters, it can cause your program to read any file (subject to file permissions), write to any file, pipe input to/from a command… anything could happen!

The best way to avoid arbitrary command execution vulnerabilities would be to avoid executing external commands altogether. It's not difficult to use hashlib or to read and compare two files in Python. The next best strategy, though, would be to use subprocess.Popen(args), where args is list.

from subprocess import Popen, run, DEVNULL, PIPE

def are_identical(path1, path2):
    """Determine whether two files have identical contents
       using the diff Unix command."""
    return 0 == run(['diff', path1, path2], stdout=DEVNULL).returncode

def md5_checksum(path):
    """Obtain the MD5 checksum of a file (as a string of hex digits)
       using the md5sum Unix command."""
    with Popen(['md5sum', path], stdout=PIPE) as proc:
        for line in proc.stdout:
            return line.split()[0].decode('ASCII')

---

The md5_checksum_table function is pretty good. You could get greater flexibility for free with two tweaks:

• Make the checksum algorithm a parameter.
• Pass a glob pattern instead of a suffix.

import fnmatch
import os

def checksum_table(checksum_algorithm, dirname, pattern):
    table = {}
    for root, sub, files in os.walk(dirname):
        for file in fnmatch.filter(files, pattern):
            path = os.path.join(root, file)
            checksum = checksum_algorithm(path)
            table.setdefault(checksum, []).append(path)
    return table

---

The are_identical() function isn't quite right. Suppose you call are_identical([a, b, c]), where files a and b are identical, but c is different — what happens?

The problem is that the interface is logically flawed. You can't take more than two files and summarize the situation as a single boolean. diff can only work on pairs of files. (Well, GNU diff can do three-way diffs, but that won't help you here.)

def duplicates(paths):
    """Partition paths into sets whose contents are identical.  Files that
       are not identical with any other file are omitted."""
    prototypes = []
    for path in paths:
        for proto in prototypes:
            if are_identical(proto[0], path):
                proto.append(path)
                break
        else:
            prototypes.append([path])
    return [set(dup_set) for dup_set in prototypes if len(dup_set) > 1]

def main():
    table = checksum_table(md5_checksum, '/media/sf_Shared/', '*.pdf')
    for md5, dup_candidates in table.items():
        for dup_files in duplicates(dup_candidates):
            print("The following files are identical, with MD5 {}:".format(md5))
            for path in sorted(dup_files):
                print('    ' + path)