# Group duplicate files

Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice on code bugs and code style are also appreciated.

Problem statement:

I am given a list of files e.g. ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]. I want to group all files which have the exact same content. Suppose in this example, file "1.txt", "2.txt", "3.txt" are the same, file "4.txt", "5.txt", "6.txt" have common header, but "4.txt", "6.txt" are exactly the same whole content. Then, the output should be two groups "1.txt", "2.txt", "3.txt" and "4.txt", "6.txt".

My major idea:

1. To avoid reading full content for each file, I generate a hash code for a file header (in my example, I define the file header to be the first two bytes of a file)
2. If more than 2 (>=2) files have the same header, I will read the full content and see if they are the exact same whole content

from collections import defaultdict
import itertools
def group_duplicate_files(files):
hash_buf = defaultdict(list)
for f in files:
result = []
for file_list in hash_buf.values():
if len(file_list) < 2:
continue
for file_pair in itertools.combinations(file_list,2):
if compare_full_content(file_pair[0], file_pair[1]):
n = set()
found = False
# try to merge with existing set
for i,r in enumerate(result):
if len(r.intersection(n)) > 0:
found = True
break
if found:
n = n.union(result[i])
result.remove(result[i])
result.append(n)
else:
result.append(n)
return result

f = open(filename, "r")
def compare_full_content(filename1, filename2):
file1 = open(filename1, 'r')
file2 = open(filename2, 'r')
i = 0
j = 0
while i < len(content1) and j < len(content2):
if content1[i] != content2[j]:
return False
i += 1
j += 1
if i < len(content1):
return False
if j < len(content2):
return False
return True

if __name__ == "__main__":
files = ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"]
print group_duplicate_files(files)

• In the Major idea part, you write the contradictory statement "If more than 2 (>=2) files have the same header". I assume it is meant to be "if at least 2 (>=2) ...". – Graipher Mar 20 '17 at 9:09
• @Graipher, yes, this is what I mean, thanks for the correction. – Lin Ma Mar 23 '17 at 20:29

As far as I can tell, your algorithm is something like $\mathcal{O}(n!)$, because you compare all possible pairs of files. It is possible to do this in $\mathcal{O}(n)$.

You just have to iterate over the files and order them into a hashmap (i.e. dictionary) based on their header hash. Then, resolve the possible conflicts of two files with the same header, but different content, which takes $\mathcal{O}(k)$, where $k$ is the number of files with the same header. So in the worst case (all files have the same header), this algorithm is $\mathcal{O}(2n)$.

from collections import defaultdict
import sys

def hash_content(file_name, length=-1):
with open(file_name) as f:

file_groups = defaultdict(list)
for file_name in file_names:
file_groups[hash_content(file_name, length=10)].append(file_name)
return file_groups

def group_by_content(*file_names):
for file_names in file_groups.values():
if len(file_names) > 1:
while file_names:
file_name = file_names.pop()
file_groups[hash_content(file_name)].append(file_name)
return filter(None, file_groups.values())

if __name__ == "__main__":
file_names = sys.argv[1:]
print group_by_content(*file_names)


This code has two caveats:

1. It assumes hash is collision-free (a fair assumption). We could pass the string content directly as a key and let python do the hashing. Then we would also get a strategy for the rare case that two strings have the same hash without being equal. But this way we avoid storing the possibly large file-contents as strings.

2. This uses the fact that dict.values() returns a list and not an iterator, so we can modify the dictionary in the loop here. This breaks in Python 3.x, but you specifically tagged this as Python 2.7. You can remedy this by introducing a new dictionary:

def group_by_content(*file_names):
content_hashs = defaultdict(list)

• @LinMa Because you do for file_pair in itertools.combinations(file_list,2) when comparing with fullcontent. – Graipher Mar 23 '17 at 20:30
• @LinMa you could do file_groups[open(file_name).read(10)].append(file_name), but as I said this would be big in memory if you also did it for the fulltext... – Graipher Mar 23 '17 at 20:34
• @LinMa When comparing coe by content you have the advantage that you can stop as soon as you find a difference. On the other hand, you have to compare all combinations of pairs, which could possible be a lot of file reads and also a large number of comparisons. (Imagine n long files with the same header, all different only by the last character. You would have to read all files completely before knowing if they are different). – Graipher Mar 24 '17 at 14:22
• @LinMa After thinking some more, I realized that combinations with length 2 will only generate binom(n+1, 2) = 0.5*(n^2 + n) comparisons. But this is still O(n^2). – Graipher Mar 24 '17 at 14:24