This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a new post.
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.
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
My major idea:
- To avoid reading full content for each file, I generate a hash code for a piece of a file (in my example, I define the piece of file to be the
10bytes of a file)
- Each time after reading the next 10 bytes, I will hash the content of the next 10 bytes, and combine the hash value (of the next 10 bytes) with existing hash value of a file
- Each time I see there is no common hash value for a file, I will stop reading this file from next piece (
- The whole algorithm complete when all files are read
hash_next_n_bytes, I will return -1 if file already reached end (EOF), but sure if there is any better way to represent it, since I think -1 may conflict with some valid hash value -1?
Source code in Python 2.7
from collections import defaultdict def group_duplicate_files(files): # open all filee file_handle_map = defaultdict(file) file_hash_map = defaultdict(int) for f in files: file_handle_map[f] = open(f, "r") while True: terminate = True group_map = defaultdict(list) for file_name, file_handle in file_handle_map.items(): h = hash_next_n_bytes(file_handle, 10) if h != -1: terminate = False file_hash_map[file_name] = hash(file_hash_map[file_name]+h) group_map[file_hash_map[file_name]].append(file_name) remove_list =  for h, file_list in group_map.items(): if len(file_list) == 1: remove_list.append(file_list) for f in remove_list: del file_handle_map[f] if terminate: break for h in file_handle_map.values(): h.close() return group_map def hash_next_n_bytes(f,n): x = f.read(n) if x: return hash(x) else: return -1 if __name__ == "__main__": files = ["1.txt", "2.txt", "3.txt", "4.txt", "5.txt", "6.txt"] print group_duplicate_files(files)