Finden von doppelten Dateien

Immer wieder habe ich das Problem, daß ich von allen doppelten Dateien in einem Verzeichnis jeweils nur eine einzige behalten möchte.
Das muß automatisch gehen. Da weder ein apropos duplicate noch ein eix duplicate sinnvolle Ergebnisse geliefert hat, programmiere ich das halt schnell selber in Python3.

Wer sich nur schnell das Programm kopieren möchte, ganz am Ende ist es nochmal komplett. Verantwortung für unabsichtlich gelöschte Dateien übernehme ich natürlich nicht.

Die Anforderungen:

Ohne Parameter soll im aktuellen Verzeichnis gesucht werden
Wird ein Parameter angegeben, so muß dies ein Verzeichnis sein und es werden alle Dateien in dem Verzeichnis überprüft
Werden mehrere Parameter angegeben, so sind dies die Dateien, die gegeneinander geprüft werden sollen.

Im ersten Schritt sollen nur Informationen über die geprüften Dateien angegeben werden.

Im zweiten Schritt sollen, schaltbar per Kommandozeilenoption, alle Duplikate gelöscht werden.

Ein Duplikat wird über die Dateigröße und einen berechneten Hash-Wert geprüft.

Hash

Ein Hash (in diesem Fall auch Checksumme oder Prüfsumme) ist ein Wert, der einen größeren Datensatz (eine Datei) verkürzt. Ähnlich wie die Quersumme einer Zahl. Der ursprüngliche Datensatz kann natürlich nicht wieder hergestellt werden und es existieren normalerweise beliebig viele Anordnungen von Zeichen in einer Datei, die den gleichen Hash-Wert erzeugen. Siehe auch in der Wikipedia: Hashfunktion.
Eine gute Hashfunktion zeichnet sich dadurch aus, daß leicht unterschiedliche Daten (ein einzelnes entferntes, hinzugefügtes oder geändertes Zeichen oder zwei vertauschtete Zeichen) auf jeden Fall unterschiedliche Hashes liefern. Soll über ein solchen Hash-Wert sichergestellt werden, daß eine Änderung an den dazugehörigen Daten erkannt wird, wie z.B. bei einer digitalen Unterschrift zu einem Text, so kommen noch einige weitere Forderungen dazu, welche mich in diesem Fall jedoch nicht interessieren.
Daher verwende ich in diesem Fall MD5, auch wenn dieser als kryptographischer Hash nicht mehr zu verwenden ist.

Also los:
Ein Hash kann über die hashlib in Python berechnet werden. Eine Funktion, um einen Hash einer Datei zu berechnet sieht daher so aus:

1
2
3
4
5
6
7
8

import hashlib
def computeHash (fn, hash_fkt = 'md5'):
h = hashlib.new (hash_fkt)
f = open (fn, 'rb')
for l in f:
h.update (l)
f.close ()
return h

Als Hashfunktion benutze ich hier MD5. Der ist zwar nicht sicher, aber relativ schnell und ich rechne nicht damit, daß mir jemand Dateien unterschiedlichen Inhalts mit gleicher Größe und gleichem MD5-Hash unterschiebt. Wenn man das als Möglichkeit ansieht sollte man wohl einen anderen Hashing-Algorithmus verwenden oder bei gleichem Hash die Dateien nochmal byteweise vergleichen.

Die Funktion, welche die Dateien überprüft bekommt eine Liste von Dateien übergeben. Für jede Datei wird zuerst die Größe bestimmt und die Dateien werden dann anhand der Größe sortiert:

1
2
3
4
5
6
7
8
9
10
11

import os

def findDuplicateFiles (files):
duplicates = {}
f_sizes = []
for f in files:
st = os.stat (f)
size = st.st_size
f_sizes.append ( (size, f))

f_sizes.sort ()

In dieser Reihenfolge kann ich nun die Dateien einfach durchlaufen. Hat eine Datei eine unterschiedliche Größe als die vorhergehende, so ist diese Datei definitiv kein Duplikat. Einen Hash benötige ich von dieser Datei noch nicht.
Erst, wenn ich eine weitere Datei der gleichen Größe habe, muß für beide der Hash berechnet werden.
Hier die Fortsetzung der Funktion findDuplicateFiles:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

last_size = None
last_f = None
last_hash = None

for size, f in f_sizes:
if size != last_size:
# Die Datei hat eine andere Größe als die vorhergehende, es ist definitiv kein Duplikat.
if last_size != None and last_hash == None:
# Wurde für die vorherige Datei noch keine Zeile ausgegeben da kein Hash berechnet wurde,
# so wird das hier nachgeholt.
# Die aktuelle Datei soll hier noch nicht ausgegeben werden. Es könnte ja eine weitere Datei
# mit gleicher Größe existieren. Dann möchte man für diese Datei nicht nur die Größe sondern
# auch die Hash-Summe ausgeben.
print (last_size, last_f)
last_size = size
last_f = f
last_hash = None
else:
# Die gleiche Dateigröße wie die vorangegangene Datei, die MD5-Summen müssen überprüft werden
if last_hash == None:
# Die MD5-Summe der letzten Datei wurde noch nicht berechnet, hier nachholen und eintragen
last_hash = computeHash (last_f)
duplicates[size] = {}
duplicates[size][last_hash] = [last_f]
print (last_hash.hexdigest (), last_size, last_f)

h = computeHash (f)

Die entsprechenden Variablen werden vor der Schleife mit dem Wert None initialisiert, damit kann ich sicher gehen, daß die erste Datei eine andere Größe hat als in last_size gespeichert ist.

Es können mehr als zwei Dateien gleicher Größe existieren und es ist natürlich nicht sichergestellt, daß die Dateien mit gleicher Prüfsumme auch hintereinander abgearbeitet werden. Daher müssen hier die Hashes aller Dateien gemerkt und verglichen werden.

Netterweise kann man ja bei einer map recht einfach prüfen, ob ein Eintrag mit gleichem Wert bereits existiert. Dementsprechend kann man schnell sehen, ob die aktuelle Datei ein Duplikat oder bisher noch einzigartig ist.

1
2
3
4
5
6
7
8
9

if not h in duplicates[size]:
print (h.hexdigest (), size, f)
duplicates[size][h] = [f]
else:
print (h.hexdigest (), size, f, "Duplikat")
duplicates[size][h].append (f)

last_hash = h
last_f = f

Zu guter Letzt muß nach der Schleife über alle Dateien evtl. noch eine Zeile für die letzte Datei ausgegeben werden, falls für diese keine Prüfsumme berechnet wurde:

1 2	if last_size != None and last_hash == None: print (last_size, last_f)

Jetzt noch eine Funktion, die aus einem übergebenen Verzeichnis alle regulären Dateien raus sucht und unsere Funktion mit dieser Liste füttert:

1
2
3

def findDuplicateFilesInDirectory (dir):
entries = [ os.path.join (dir, e) for e in os.listdir (dir) if os.path.isfile (os.path.join (dir, e)) ]
findDuplicateFiles (entries)

Und zum Abschluß noch der Hauptteil des Programms. In erster Fassung ohne Parsen von Parametern und es wird einfach das aktuelle Verzeichnis übergeben:

1
2
3

if __name__ == "__main__":
dir = "."
findDuplicateFilesInDirectory (dir)

Soweit so gut.
Leider funktioniert es so noch nicht!
Das Objekt, welches den Hash speichert hat zwar eine Methode __hash__ implementiert, welche für die Benutzung als Schlüssel in einer map notwendig ist, jedoch ist die Methode __eq__ nicht entsprechend überladen. Zwei Instanzen der Klasse liefern hier ein False zurück, obwohl sie den gleichen Hashwert speichern.
Um das zu umgehen baue ich mir eine kleine Wrapper-Klasse:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Hash:
def __init__ (self, fkt = 'md5'):
self.h = hashlib.new (fkt)

def update (self, data):
self.h.update (data)

def hexdigest (self):
return self.h.hexdigest ()

def __hash__ (self):
return self.h.digest ().__hash__ ()

def __eq__ (self, other):
if not isinstance (other, Hash):
return False

return self.h.digest () == other.h.digest ()

Nun muß nur noch die erste Zeile der Methode computeHash angepaßt werden und die Erkennung funktioniert:

1
2
3

def computeHash (fn, hash_fkt = 'md5'):
h = Hash (hash_fkt) #hashlib.new (hash_fkt)
...

Und hier nochmal der komplette Code jetzt inklusive Kommandozeilenparameter über argparse:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#

import os
import hashlib
import argparse

class Hash:
def __init__ (self, fkt = 'md5'):
self.h = hashlib.new (fkt)

def update (self, data):
self.h.update (data)

def hexdigest (self):
return self.h.hexdigest ()

def __hash__ (self):
return self.h.digest ().__hash__ ()

def __eq__ (self, other):
if not isinstance (other, Hash):
return False

return self.h.digest () == other.h.digest ()

def computeHash (fn, hash_fkt = 'md5'):
h = Hash (hash_fkt)
f = open (fn, 'rb')
for l in f:
h.update (l)
f.close ()
return h

def findDuplicateFiles (files, remove, verbose):
duplicates = {}
f_sizes = []
for f in files:
st = os.stat (f)
size = st.st_size
f_sizes.append ( (size, f))

f_sizes.sort ()
last_size = None
last_f = None
last_hash = None

for size, f in f_sizes:
if size != last_size:
# Die Datei hat eine andere Größe als die vorhergehende, es ist definitiv kein Duplikat.
if verbose and last_size != None and last_hash == None:
# Wurde für die vorherige Datei noch keine Zeile ausgegeben da kein Hash berechnet wurde,
# so wird das hier nachgeholt.
# Die aktuelle Datei soll hier noch nicht ausgegeben werden. Es könnte ja eine weitere Datei
# mit gleicher Größe existieren. Dann möchte man für diese Datei nicht nur die Größe sondern
# auch die Hash-Summe ausgeben.
print (last_size, last_f)
last_size = size
last_f = f
last_hash = None
else:
# Die gleiche Dateigröße wie die vorangegangene Datei, die MD5-Summen müssen überprüft werden
if last_hash == None:
# Die MD5-Summe der letzten Datei wurde noch nicht berechnet, hier nachholen und eintragen
last_hash = computeHash (last_f)
duplicates[size] = {}
duplicates[size][last_hash] = [last_f]
if verbose:
print (last_hash.hexdigest (), last_size, last_f)

h = computeHash (f)
if not h in duplicates[size]:
if verbose:
print (h.hexdigest (), size, f)
duplicates[size][h] = [f]
else:
if verbose:
if remove:
print (h.hexdigest (), size, f, "removed duplicate")
else:
print (h.hexdigest (), size, f, "duplicate")
else:
print (h.hexdigest (), size, f)
duplicates[size][h].append (f)
if remove:
os.remove (f)

last_hash = h
last_f = f

if verbose and last_size != None and last_hash == None:
print (last_size, last_f)

def findDuplicateFilesInDirectory (dir, remove, verbose):
entries = [ os.path.join (dir, e) for e in os.listdir (dir) if os.path.isfile (os.path.join (dir, e)) ]
findDuplicateFiles (entries, remove, verbose)

if __name__ == "__main__":
dir = "."
files = None

parser = argparse.ArgumentParser (description='Search for duplicate files using md5 sums.')
parser.add_argument ('file_name', nargs='*',
help='the directory where to check all files or file names to check')
parser.add_argument ('-r', dest='remove', action='store_true',
help='delete the duplicates instead of just print them')
parser.add_argument ('-v', dest='verbose', action='store_true',
help='print a line for every checked file, not only for the duplicates')

args = parser.parse_args()

if len (args.file_name) == 1:
dir = args.file_name[0]
elif len (args.file_name) > 1:
files = [ fn for fn in args.file_name ]

if files == None:
findDuplicateFilesInDirectory (dir, args.remove, args.verbose)
else:
findDuplicateFiles (files, args.remove, args.verbose)

Viel Spaß damit.

Schreibe einen Kommentar Antworten abbrechen