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][1] [site][2] and on [SO][2], 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))
[1]: https://codereview.stackexchange.com/questions/159569/group-duplicate-files-part-3
[2]: https://codereview.stackexchange.com/questions/132927/identify-files-within-folder-structure-that-have-common-file-sizes
[3]: https://stackoverflow.com/questions/748675/finding-duplicate-files-and-removing-them