Doppelte Dateien finden!?

[Foobar]

Hallöle,

angeregt durch einen (uralten) Forenpost hier im Board und weil ich es für mein aktuelles Programm ganz gut gebrauchen kann, möchte ich eine Programm schreiben, welches doppelte Dateien aufspüren kann.

Soweit ist dies auch schon geschehen und ich war mal so frei und hab einige Anregungen und Ideen aus dem verlinkten Forenpost übernommen (das Ergebnis dürft ihr euch auf Github anschauen, falls Interesse besteht. Ihr dürft natürlich auch gern heftig kritisieren ).

Die Frage die für mich bleibt: Aus dem Forenpost habe ich u.a. auch übernommen, dass ich (nachdem ich Dateigröße verglichen hab), den md5-Hashwert der Dateien vergleiche (blockweise). Ich frage mich nur, warum man eigentlich den md5-Hashwert der Dateien vergleicht? Um den md5-Hash zu bekommen, muss ich die Datei ja eh öffnen und wenn ich an diesem Punkt angelangt bin, warum nicht gleich byte für byte vergleichen sondern stattdessen den md5-Wert? Macht das trotzdem irgendwie Sinn?

Gruß, Micha

[cofi]

Ja, so, wie du es gemacht hast, macht ein Hashwert natuerlich keinen Sinn.

Der Punkt ist, dass man den Hash _nicht_ blockweise vergleicht, sondern den Hash blockweise aufbaut und die Hashes der kompletten Datei vergleicht. Hashes zu benutzen macht hier weit mehr Sinn, da man den Hash jeder Datei speichern kann und so Aequivalenzklassen aufbaut (zb als Dictionary von Hash zu einer Liste von Dateien) .. statt paarweise zu vergleichen.
Du hast hier naemlich eine wunderbare quadratische Komplexitaet, statt der eigtl nur noetigen Linearen: 1000 Dateien fuehren zu 1 Million Vergleichen statt den noetigen 1000. Das wuerde ich nicht auf eine kleine Fotosammlung loslassen

Zum Code an sich: Dateien oeffnet man mit `with`, du brauchst den File pointer nicht selbst zu manipulieren, das macht `read()` schon.

Code: Alles auswählen

for index in range(len(self._files)):

Puh. Du baust hier eine extra Liste auf, die du genauso wie `index` nie benutzt. Benutze direkt die Listen Eintraege und veraendere die Liste nicht unnoetig. Wenn du es doch machen willst, benutze eine `while` Schleife.

[Foobar]

Hallo Michael,

vielen Dank für deine Antwort! Hab den Quellcode nun ein bisschen umgebaut: Die Befehle zum Datei-öffnen hab ich nun mit 'with'-Statement umgesetzt und die angesprochene for-Schleife sieht nun so aus:

(kompletter Quellcode auf Github einsehbar)

Code: Alles auswählen

for competitor in self._files:
    duplicates_ = self._compare(competitor, self._files[self._files.index(competitor)+1:])
    # [...]

Das mit den Hashes hab ich aber immer noch nicht verstanden? :K

Der Punkt ist, dass man [...] den Hash blockweise aufbaut und die Hashes der kompletten Datei vergleicht.

Was heißt "Hash blockweise aufbauen"?
"Die Hashes der kompletten Datei vergleicht"? Kann es sein, dass da "Dateien" stehen sollte? Sollte man erst aus allen Dateien einmalig Hashwerte bilden und diese dann untereinander vergleichen? Wobei dadurch die Anzahl an Vergleichen nicht abnimmt (obwohl die Geschwindigkeit sicher zunimmt), was dann mit deiner Aussage über quadratische und lineare Komplexität nicht so ganz zusammen passt!? Und bleibt die Frage, was du mit "Hash blockweise aufbauen" meinst?

Ein herzliches Dankeschön auf jeden Fall schon mal
schönen Sonntag wünsch ich,
Gruß, Micha

[Sirius3]

@Foobar: Den Hashwert jeder Datei kann man wunderbar als Key in ein Dictionary verwenden und braucht damit nicht mehr jede Datei mit jeder sondern nur noch n*log(n) vergleiche des Hashwertes und nur bei Kollisionen den Vergleich der ganzen Datei.
Blockweise meint natürlich Blockweise:

Code: Alles auswählen

md5_hash = hashlib.md5()
with open(filename,'rb') as stream:
    while True:
        data = stream.read(BLOCKSIZE)
        if not data:
            break
        md5.update(data)
    digest = md5.hexdigest()

[BlackJack]

@Foobar: Hashes machen relativ wenig Sinn. Ich würde das erst einmal komplett ohne umsetzen. Grundsätzlich geht es ja erst einmal um Gruppen von Dateien mit der gleichen Grösse. Bei Dateien mit unterschiedlichen grössen kann man trivialerweise annehmen, dass sie nicht gleich sind.

Bleibt die Frage wie man `n` Dateien mit gleicher Grösse vergleicht. Man könnte nun natürlich von jeder der `n` Dateien erst einmal den Hashwert berechnen und wüsste dann welche ungleich sind. Welche mit gleichem Hashwert kann man streng genommen *nicht* einfach als gleiche Dateien ansehen, denn Hashwerte können ja kollidieren. Für den Hashwert der gesamten Datei muss man die gesamte Datei lesen. Für den direkten inhaltlichen Vergleich von zwei Dateien braucht man beide nur bis zu dem Punkt lesen an dem sie nicht mehr übereinstimmen. Das kann also durchaus schneller sein, auch wenn man mehr Vergleiche machen muss. Nur wenn man viele Dateien hat die gross und gleich sind, wird es ineffizient, weil man die immer bis zum Ende lesen muss.

Hier könnte man jetzt als Optimierung anfangen mit Hashwerten zu arbeiten, und zwar auf Blöcken der Datei, die man im Speicher cached. Wenn man dann eine Datei erneut lesen muss, kann man das erst einmal lassen und die Hashwerte von den Blöcken vergleichen bevor man tatsächlich die Werte liesst. Wenn die Hashwerte von den Blöcken nicht übereinstimmen, dann braucht man die Blöcke nicht noch einmal lesen.

[Foobar]

Danke für eure vielen Ideen und Anregungen!

Den Hashwert jeder Datei kann man wunderbar als Key in ein Dictionary verwenden

Damit ich das richtig verstehe: Keys im Dict sind wie Set-Werte einmalig, du würdest also ein Dictionary aufbauen, dass für jeden hash-Wert eine Liste aller passenden Dateien speichert? edit: Ah, ich glaub, das hat cofi gestern auch gemeint... jetzt macht das alles langsam Sinn
Was ist der Vorteil der blockweisen Hash-Wert-Bestimmung? Ist es weniger RAM-Verbrauch, weil nicht mehr ganze Dateien in den Arbeitsspeicher geladen werden?

Grundsätzlich geht es ja erst einmal um Gruppen von Dateien mit der gleichen Grösse

Die Dateigröße wird in meinem Programm berücksichtig Wobei ich die Größe bei jedem Vergleich prüfe, vllt. wäre es schneller, wenn ich zunächst gleich große Dateien gruppiere? Mhh...

Nur wenn man viele Dateien hat die gross und gleich sind, wird es ineffizient

Hauptzweck meines Programms wird sein, ein Bild mit einem Bilder-Ordner zu vergleichen und zu prüfen, ob das Bild bereits im Ordner existiert. Im schlimmsten Fall geht es dabei um den Bilderordner meines Benutzeraccounts, also gehe ich erst mal von sehr vielen sehr großen Dateien aus, aber wenige identische.
Komplizierter wird es, wenn der Bilderordner schlecht organisiert ist und durch "Import- und Kopier-Unfälle" viele Duplikate enthält. Dieses Problem soll mein Programm als Nebeneffekt auch lösen können, indem es die Duplikate findet und ggf. löscht.

Danke an alle für die vielen Anregungen! Die Umsetzung der Ideen wird wohl etwas dauern, aber wenn es Updates gibt, meld ich mich und freu mich auf weiteres Feedback

Liebe Grüße, Micha

[BlackJack]

@Foobar: Das blockweise lesen verhindert das der ganze Arbeitsspeicher mit Daten gefüllt wird die eigentlich gar nicht benötigt werden aber alles andere aus dem Speicher in die Auslagerungsdatei verdrängt. Auch wenn Arbeitsspeicher auf Desktopsystemen heute nicht mehr so knapp bemessen ist — DVD-Images oder Festplatten-Images von VMs können auch solche Systeme noch in die Knie zwingen oder zumindest unnötig ausbremsen.

Ich würde gleich grosse Dateien erst einnal gruppieren. Entweder in einem Wörterbuch das Grösse auf Liste mit Dateien abbildet, oder in dem man die Gesamtliste nach Dateigrösse sortiert und dann mit `itertools.groupby()` arbeitet. Für ersteres bietet sich ein `collections.defaultdict` an.

Die zu testenden Kombinationen von Datei-Paaren kann man in jeder Grössengruppe dann ganz mit `itertools.combinations()` durchgehen.

*Eine* Datei mit vielen anderen zu vergleichen ist aber ein anderes Problem was man einfacher Lösen kann als generell Duplikate zu finden. Da würdest Du mit dem Programm irgendwie mit Kanonen auf einen Spatz schiessen.

[Sirius3]

Ich habe mal testweise einen Doppeldateienfinder auf ein Verzeichnis losgelassen. Bei knapp 50.000 Dateien waren 10.251 mehrfach vorhanden. Wurden alle gleichgroßen Dateien miteinander verglichen, waren 130.000 Vergleiche zweier Dateiinhalte nötig, wurde zusätzlich ein Hash der ersten 1024 Bytes berechnet, mußten nur noch 6762 Dateien komplett verglichen werden, bei 4k-Hash 6694 Dateien. Ohne Hash dauerte die Suche 5.9s mit Hash 2.8s.
Die Dateien haben eine Gesamtgröße von 55GB.

Hier das Testprogramm:

Code: Alles auswählen

import os
import hashlib
import collections
from itertools import imap
import operator

class ComparableFile(object):
    BLOCKSIZE = 1024
    
    def __init__(self, filename):
        self.filename = filename
        with open(filename, 'rb') as data:
            md5 = hashlib.md5(data.read(self.BLOCKSIZE))
            self.hash = (os.path.getsize(filename), md5.digest())
        
    def __hash__(self):
        return hash(self.hash)
    
    def __eq__(self, other):
        if self.hash != other.hash:
            return False
        with open(self.filename, 'rb') as f1, open(other.filename, 'rb') as f2:
            iter1 = iter(lambda: f1.read(self.BLOCKSIZE), '')
            iter2 = iter(lambda: f2.read(self.BLOCKSIZE), '')
            return all(imap(operator.eq, iter1, iter2))

def main():
    equal_files = collections.defaultdict(list)
    for path, _, filenames in os.walk('/'):
        for filename in filenames:
            filename = os.path.join(path,filename)
            if os.path.isfile(filename):
                equal_files[ComparableFile(filename)].append(filename)
    for filenames in equal_files.values():
        if len(filenames)>1:
            print filenames

if __name__ == '__main__':
    main()