Identify Duplicate Files

Question

A friend of mine has the following issue. He has a nearly-full 1TB hard drive on which he keeps copies of all the pictures from his digital camera(s). However, he knows that he has copied the entire contents of the camera to this drive multiple times, with slightly similar--but mostly identical--contents every time. He would like to able to find out which files (mostly pictures) are duplicates.

While I started writing this for his application, I would like this to be a general-purpose script for my own use as well. Here is what I came up with.

Main Ideas

Building on the ideas of some posts on this site and on SO, I create a hash (albeit non-integer) for each file, consisting of (a) the size of the file, (b) some bytes read from the start of the file, and (c) an incrementable counter. This enables me to quickly check that two files are not identical, and then only compare the entire contents if the hashes are equivalent. In the case that two dissimilar files have the same hash, I increment the counter and try again.

• I realize that it may seem wasteful to open, read, and close every file when a simple size comparison might be initially sufficient; but I have found that this is generally not the case. In situations where there are many different similar-sized files, the algorithm approaches \$O(n^2)\$ where one must walk through all previous same-size files for each new one. Granted, these situations only arise in special cases (usually when traversing program files), but hitting one on accident tremendously slows down the program. Thus, taking the time initially to read some bytes can really pay off later. (YMMV, but if you use Chromium, ~/.cache/chromium/Default/Cache clearly demonstrates this principle.) Of course, nothing is set in stone, and different hash functions may be used depending on the situation. In addition, other methods (see end of Feedback section), can be used to attempt to circumvent this issue.

The full-file comparison is done by filecmp, which is very fast, although slight modification could make it faster (e.g. a larger cache, or skipping some initial checks which we already know).

Feedback

1. Of course, the main concern for this kind of program is speed. Is my algorithm efficient? Can it be improved? Are there edge|special-cases that I have overlooked?

   • I considered that my hash method of using tuples may not be efficient, especially since very many look-ups need to be performed. However, I did not find a significant difference in speed using an equivalent integer hash method. (I tried a few things, but calling the built-in hash on the 3-tuple was the most straightforward.)

2. I am not an expert Python programmer. Is this program written and implemented well? Are there any code-smells or bad practices? Do I make good use of Python structures and idioms? What could I do better? What have I done well?

   • One in particular, I am not fond of the large try block. However, due to the fact that there would have to be two nearly-identical try blocks very close to each other (around fhash = hash_by_tuple(...) and if filecmp.cmp(...)), I thought it was better to pull it out around both.

3. Any other feedback.

I think there are certainly things that can improve the usability the code. For example, adding support for a list of directories, files, or even regex matches to ignore would allow us to skip certain expensive searches, like ~/.local and ~/.cache. Or, conversely, a regex to include only certain kinds of files (e.g., r'[.]png$'). However, this seems relatively straight-forward to implement, and it would clutter the code that I would really like to present, so I have not included it.

Code

import filecmp
import os
from time import time

def head (fpath, nbytes, offset=0):
    """ Read `nbytes` from the beginning of a file, starting at
        `offset`.
        If there are less than `nbytes`, return whatever is there
        (may be empty).
        If there is not enough room for the `offset`, move back so
        that we still return `nbytes` number of bytes.
    """
    size = os.stat(fpath).st_size
    with open(fpath,'rb') as f:
        if size <= nbytes:
            pass
        elif size < offset+nbytes:
            f.seek(-nbytes,2)
        else:
            f.seek(offset)
        head = f.read(nbytes)
    return head


def hash_by_tuple (fpath, nbytes=4, offset=16):
    """ Create a 3-tuple hash of the file at `fpath`, consisting of
        the file size, `nbytes` read from the file, and an
        incrementable counter. Start reading the bytes at some
        `offset` so that common headers (e.g. png/pdf) are not
        included. The counter is always initially 0, and is intended
        to be incremented on hash collisions to create a new, unique
        hash.
    """
    return os.stat(fpath).st_size, head(fpath,nbytes,offset), 0


def find_dups (top_dir, **hashkwargs):
    """ Group duplicate files recursively in and below `top_dir`.
        Returns a 6-tuple with the main return value and some metadata
        as follows:
            (0) The main dictionary of all files, with the hash value
                from `hash_by_tuple` as the keys, and a list of the
                file paths with identical content as the values.
            (1) The total number of files included in the dict.
            (2) The number of files skipped for various reasons.
                Usually broken symlinks that are listed by `os.walk`,
                but are not `os.stat`-able.
            (3) The total size, in bytes, of all files in the dict.
            (4) The `top_dir` input, for output formatting.
            (5) The time it took to run the function, in seconds.

        Optional `hashkwargs` can be passed to modify the behavior of
        `hash_by_tuple`.

        Note 1: The output of this function is best viewed using the
        complementary function `format_find_dups_output`.

        Note 2: All empty files are considered "identical" and are
        mapped to `(0, b'', 0)`.
    """
    t0 = time()
    top_dir = os.path.abspath(os.path.expanduser(top_dir))
    dups = {}
    numfiles = numskipped = totsize = 0
    for dirpath,_,fnames in os.walk(top_dir):
        for fname in fnames:
            fpath = os.path.join(dirpath,fname)
            try:
                fhash = hash_by_tuple(fpath,**hashkwargs)
                while True:
                    if fhash not in dups:
                        # a new, unique file has been found.
                        dups[fhash] = [fpath]
                        break
                    # file is a duplicate, or hash collision occured.
                    if filecmp.cmp(fpath,dups[fhash][0],shallow=False):
                        # duplicate.
                        dups[fhash].append(fpath)
                        break
                    # hash collision on actually different files; rehash.
                    fhash = (fhash[0], fhash[1], fhash[2]+1)
            except OSError:
                numskipped += 1
                continue
            numfiles += 1
            totsize += fhash[0]
    return dups, numfiles, numskipped, totsize, top_dir, time()-t0


def format_find_dups_output (output, min_dups=1):
    """ Return a human-readable formatted string directly from the
        6-tuple `output` from `find_dups`. It can then either be
        `print`-ed, or written to a file and read.
        Set `min_dups` (default=1) to control the minimum number of
        duplicates a file must have to be included in the returned
        string. 0 will print every file found.
    """
    dups, numfiles, numskipped, totsize, top_dir, runtime = output

    header = ( 'In "{}", {} files were analyzed, totaling {} bytes, taking '
             + '{:.3g} seconds.\n'
             + '{} files were skipped because they failed analysis (typically '
             + 'broken symlinks).\n'
             + '{} unique files were found, with {} duplicates, averaging '
             + '{:.3g} duplicates per unique file.\n\n'
             + 'There are {} unique files with >= {} duplicates. In some '
             + 'particular order:\n\n' )

    main_str = ''
    numuniq_printing = 0
    for fhash,fpaths in sorted(dups.items()):
        if len(fpaths) > min_dups:
            numuniq_printing += 1
            if len(fpaths) == 1:
                main_str += ( 'The following file, with the signature {}, '
                            + 'is unique:\n    ' ).format(fhash)
            else:
                main_str += ( 'The following {} files, with the signature {}, '
                            + 'are identical:\n    ' ).format(len(fpaths),fhash)
            main_str += '\n    '.join(fpaths) + '\n\n'

    main_str += 'Done.'

    header = header.format( top_dir, numfiles, totsize, runtime, numskipped
                          , len(dups), numfiles-len(dups)
                          , (numfiles-len(dups))/len(dups)
                          , numuniq_printing, min_dups )

    return header+main_str



if __name__ == '__main__':
    dups_output = find_dups('/a/path/with/maybe/1000/files/for/testing')
    print(format_find_dups_output(dups_output,min_dups=1))

Answer 1

Others are better equipped than I to talk about the quality of the Python, but I can tell you that seeks are expensive, that all random reads cost about the same as long as you're reading less than a block, and that read+stat is worse than reading two sequential blocks, because the stat reads a directory and not the file.

I see about a 10% speedup if you hash the first 4k and use that as your key; another 5% from not computing total size (the only thing stat is needed for, once you drop size from the key):

def find_dups (top_dir, **hashkwargs):
    t0 = time()
    top_dir = os.path.abspath(os.path.expanduser(top_dir))
    dups = {}
    numfiles = numskipped = totsize = 0
    for dirpath,_,fnames in os.walk(top_dir):
        for fname in fnames:
            fpath = os.path.join(dirpath,fname)
            try:
                with open(fpath,'rb') as f:
                    fhash = hash( f.read(4096) )
                while True:
                    if fhash not in dups:
                        # a new, unique file has been found.
                        dups[fhash] = [fpath]
                        break
                    # file is a duplicate, or hash collision occured.
                    if filecmp.cmp(fpath,dups[fhash][0],shallow=False):
                        # duplicate.
                        dups[fhash].append(fpath)
                        break
                    # hash collision on actually different files; rehash.
                    fhash += 1
            except OSError:
                numskipped += 1
                continue
            numfiles += 1
    return dups, numfiles, numskipped, totsize, top_dir, time()-t0