Identische Dateien auf dem Computer finden mit Perl

Vor kurzem stand ich vor dem Problem, daß auf einem von mir betreuten Webserver der Speicherplatz aufgebraucht war.
Nach etwas herumsuchen stellte ich dann fest, daß es daran lag, daß viel Speicherplatz verschleudert wurde, weil viele identische Dateien mehrmals vorhanden waren.

Was lag also näher, als ein kleines Perl-Programm zu schreiben, das doppelte (identische) Dateien findet?

Doppelt (identisch) bedeutet in diesem Fall:
Gleicher Inhalt, Datei größer als 0 Byte und Datei kleiner als 64 Mio. Byte.

Also, dann mal los:
Zuerst stellte sich die Frage, wie man Dateien überhaupt miteinander vergleicht, und zwar so effektiv wie möglich, d.h. mit möglichst wenig Speicherlast und guter Performance.

Die simpelste Methode (die man natürlich nicht nehmen sollte!)
Man öffnet eine Datei, liest den Inhalt ein, nimmt den Dateinamen als key eines Hashes, den Inhalt als Value

# dirty code, nur als demo gedacht
$datname="test.txt";

open (in,$datname);
while (<in>){$inhalt.=$_;}
close in;

$datei{$datname}=$inhalt;

So, wie gesagt, sollte man es NICHT machen! Hier wird Speicherplatz verballert ohne Ende und das Finden von Dupletten kann schon mal ne Ewigkeit dauern.

Wie also dann?
Ein anderer Ansatz kommt der Sache wohl schon eher näher:
Man öffnet eine Datei, bildet eine Checksumme, also einen eindeutigen Bezeichner, des Inhaltes, legt ein Skalar an und schiebt pro Checksumme den Dateiname in das Skalar.
Etwas verwirrend, also wieder etwas Code zur Verdeutlichung:

# nur Democode zur Veranschaulichung
$datname="test.txt";

open (in,$datname);
while (<in>){$inhalt.=$_;}
close in;

$checksumme=generiere_checksumme($inhalt);
$files{$checksumme}.="$datname\n";

Was daraus resultiert ist ein Skalar, das Einträge zu allen Dateien, aufgesplittet nach den Checksummen, enthält.
Dateien mit den gleichen Checksummen sind der Wert, also das value, eines Hash-Elements, getrennt durch ein \n, bzw. einen Zeilenumbruch.

Wenn man nun nach allen Hash-Elementen sucht, die mehr als ein \n enthalten, hat man alle Dateien, die identisch sind. Klingt einfach, ist es auch... nur: wie krieg ich nun so eine Checksumme?
Dafür gibts das wunderbare Modul Digest::MD5!

Dieses Modul wandelt einen übergebenen Wert in eine solche Checksumme. Diese Checksumme hat eine interne Länge von 128 Bit, sollte also ausreichend sein.

So, genug gequatscht, hier der Code:

use Digest::MD5 qw(md5);
use strict;

my %files=();
my %dateien;
my @nulllength=();
my @dateisize=();
my @dateien=get_all_files('c:/htdocs/',1,'.shtml');

print "Es wurden ".@dateien." Dateien gefunden\n";

## Dateilänge holen und merken
foreach (@dateien){
my $size=-s $_;
# Dateiname + Größe in Skalar schreiben
push (@{$dateien{$size}},"$_\|$size]");
}

@dateien=();
foreach (keys %dateien){
my @dats=@{$dateien{$_}};
next if @dats<2; # wenigstens 2 Filename müssen da sein
push (@dateien,@dats);
}

%dateien=();
print "Es wurden ".@dateien." mögliche Dateien gefunden\n Generiere Checksummen\n";

foreach (@dateien){
get_checksum($_);
}

print qq~Dateien mit Nulllaenge:\n~;
print join("\n",@nulllength);

print qq~\n\nIdentische Dateien:\n~;
foreach (keys %files){
print "$files{$_}\n\n" if (split('\n',$files{$_}) >1);
}

exit;

###################
# Parameter
# Startdir ohne abschließendes /, aktuelles Verzeichnis = .
# Unterverzeichnisse durchsuchen? 1: ja, 0: nein
# Dateitypen in form .txt.htm.html , also direkt hintereinander, aber nur wenn nötig
# ansonsten wird alles gezeigt
#############################################
sub get_all_files{
my $startdir=shift;
my $include_subdirs=shift;
my $endings=shift;
my %endings=();
$endings=~ s/\s//g;
my @endings=split('\.',$endings);
shift @endings;

my $endings=0;
$startdir=~ s/\/$//;

if (@endings != 0){
$endings=1; # wenn Endungen angegeben
foreach (@endings){
$endings{$_}=1;
}
}
@endings=();

my @dateien=();
push (my @all_directories,$startdir);

foreach my $akdir(@all_directories){
local *in;
opendir (in,$akdir);
my @all=readdir(in);
closedir in;

foreach my $akdatei (@all){ next if ($akdatei eq '..' || $akdatei eq '.');
if (-d "$akdir/$akdatei") {
if ($include_subdirs == 1){
push (@all_directories,"$akdir/$akdatei");
next;
}
} else {
if ($endings==0){
push (@dateien,"$akdir/$akdatei");
} else {
my @endung=split('\.',$akdatei);
my $endung=$endung[-1];
if ($endings{$endung} == 1){
push (@dateien,"$akdir/$akdatei");
}
}
}
}
}
return @dateien;
}

######################
# generiert Checksumme einer Datei
#############################################
sub get_checksum{

my $data='';
(my $dateiname, my $dateilaenge)=split('\|',shift);

if ($dateilaenge < 1){
push(@nulllength,$dateiname);
} else {
return if $dateilaenge > 64000000; # Wenn Datei > als 64 Mio. Byte
open (my $IN,'<'.$dateiname);
binmode($IN);

my $checksum = Digest::MD5->new->addfile(*$IN)->b64digest;
close $IN;
$files{$checksum}.="$dateiname\n";
}
}

Wie Sie sehen, wird auch noch gleich ein Array angelegt, das alle Dateien enthält, die eine Länge von 0 Bytes haben.

Ich habe übrigens auch wieder die Subroutine get_all_files verwendet, da ich gemerkt habe, daß mir das Modul File::Find etwas zu unflexibel war.
Was geschieht hier nun?
In der Zeile
my @dateien=get_all_files('c:/',1,'.txt');
startet das Script die Suche nach allen Dateien mit der Endung .txt auf dem Laufwerk C: inklusive Unterordner.

Danach wird für jede Datei die Checksumme gebildet

######################
# generiert Checksumme einer Datei
#############################################
sub get_checksum{

my $data='';
(my $dateiname, my $dateilaenge)=split('\|',shift);

if ($dateilaenge < 1){
push(@nulllength,$dateiname);
} else {
return if $dateilaenge > 64000000; # Wenn Datei > als 64 Mio. Byte
open (my $IN,'<'.$dateiname);
binmode($IN);

my $checksum = Digest::MD5->new->addfile(*$IN)->b64digest;
close $IN;
$files{$checksum}.="$dateiname\n";
}
}

und schließlich in den Zeilen

foreach (keys %files){
print "$files{$_}\n\n" if (split('\n',$files{$_}) >1);
}

die Elemente gesucht, die mehr als einen Filenamen enthalten, also identisch sind.

Ich hoffe, ich konnte das Verfahren deutlich machen. Viel Spaß damit!

Kleiner Nachschlag
Ich hab mir das ganze nochmal durch den Kopf gehen lassen und mir fiel noch ein:
Effektiver wäre das Ganze, wenn nur dann eine Checksumme gebildet wird von den Dateien, deren Länge mindestens 2 mal auftaucht, oder anders gesagt: Wenn die Datei test.txt die einzige ist, die 20 Byte lang ist, muß sie nicht weiter geprüft werden.
Also hab ich den Code oben also dahingehend erweitert.

Man sieht am Anfang jetzt eine Prüfung der Dateigrößen. Nur wenn eine Dateigröße mehr als einmal auftaucht wird weiter grprüft. Das spart nochmal gehörig Rechenzeit und Ressourcen.
Um ein doppeltes Prüfen der Dateigröße zu vermeiden wird die Dateigröße an den Filenamen angehängt und in der Routine get_checksum wieder per Split abgelöst.

Ich glaub, mir fallen zu dem Thema noch ein paar Kleinigkeiten ein, ... ich werd da mal am Ball bleiben und morgen gehts dann weiter.

Nachtrag
So gut das Script inzwischen auch läuft, so ein ungutes Gefühl habe ich eben doch noch dabei. Für jede Datei eine Checksumme erstellen, nur um zu sehen, ob diese zweimal auftaucht... hört sich nach viel unnötiger Rechnerei an!

Ich hab mir also spaßeshalber mal die md5-Routine vorgenommen und getestet, wie schnell oder langsam die so ist.
Also flugs mal ein Scriptchen geschrieben, das 10000 mal so ne Checksumme errechnet, mit einem Skalar von ein paar Byte länge. Und Bingo, das ging wirklich schnell, also < 1 Sekunde.
Und ich wollte gerade meine Versuche abbrechen, da kam ich auf die Idee, eine Checksumme aus einem Skalar von 100.000 x a zu erstellen, natürlich auch gleich 10.000 mal.
Und siehe da: das dauerte glatt über 30 Sekunden!!!
md5 ist also um so langsamer, um so länger der übergebene Wert ist! Und da man ja nie weiß, wie groß die einzelnen Dateien sind, aus denen man eine Checksumme erstellt, wird das je nach Datei den Computer sehr belasten und ausbremsen.

Also muß eine Lösung dahingehend her, daß man eine Checksumme wirklich nur dann errechnen läßt, wenn es wirlich nötig ist.

Ich kam dann also auf die Idee, von jeder Datei die ersten 100 Bytes einzulesen und miteinander zu vergleichen. Sollen bei einer Datei die ersten 100 Bytes einzigartig sein, braucht man keine Checksumme. Erst wenn zwei oder mehr Dateien die gleichen ersten 100 Bytes haben, wird eine Checksumme gebildet. Klar ist jedoch, daß dies dann vermehrt Festplattenzugriffe erzeugen wird.

Ich ändere mal eben das Haupt-Script und berichte dann weiter, wie viel Geschwindigkeitsvorteil das gebracht hat.

Also:
Ich habe das noch umgesetzt (Hier übrigens der Code), hatte dann aber zum Schluß doch eine Geschwindigkeitseinbuße von ca. 10%, es lag wohl daran, daß das Öffnen der Dateien und das Einlesen der ersten 100 Bytes unterm Strich mehr Zeit verbraten hat als die Einsparungen bei den Checksummen brachten. Ein Holzweg also!
Deswegen wird es bei dem obigen (nochmal aktualisierten) Script bleiben.

Danke übrigens für den Tipp mit dem direkten Einlesen der Datei in MD5, ist zwar nicht wirklich schneller, sieht aber schicker aus und vereinfacht den Code. Und die Codierung mit Base64 spart in dem Fall tatsächlich Speicherplatz im System.

Nachtrag
Den überarbeiteten Programmteil von get_all_files gibt es hier. Sie können ihn auf Wunsch natürlich anstatt der oben verwendeten Routine verwenden, er ist etwas schneller beim Einlesen der Verzeichnisse.

Kommentare zum Beitrag "Identische Dateien auf dem Computer finden mit Perl"

Kommentar von Guido Beckmann

Noch ein paar Anregungen:
Das MD5 Modul kennt eine Methode addfile. Du brauchst dir also nicht den ganzen Filecontent in ein String kopieren.
Die Datei sollte sicherheitshalber im binmode geöffnet werden.
Lass dir den MD5-Hash in Base64 zurückgeben, da die Darstellung so weniger Zeichen benötigt.

Kommentar von stderr

Das einlesen der ersten 100 Byte wuerde ich nicht so empfehlen. Meine Bedenken dabei:

Ich ahbe Dateien verschiedener Versionsstaende, die beide ihre Daseinsberechtigung haben. Beispielsweise Code, der nur anch den ersten 100 byte geaendert wurde. Somit sind die Dateien fuer Dein code gleich, weil der Bereich >100Byte ignoriert wird ... sehe ich als Fallstrick an ...

Ansonsten nice code ;)

Kommentar von Admin

Ja, das mit den ersten 100 Bytes war wohl nicht die tollste Idee von mir.
Aber man muß ja manchmal auch Sachen ausprobieren, die dann in der Tonne landen, weil bevor man es probiert, weiß man nicht immer, ob es besser ist oder nicht...
Ich hab's ja dann schließlich auch verworfen.

Kommentar von Struppi

Was ist denn an File::Find unflexibel?

Thema: Perl Dateien Script

Der Beitrag "Identische Dateien auf dem Computer finden mit Perl" wurde 10533 mal gelesen.

Es wurde 6 x über diesen Beitrag abgestimmt.
Die durchschnittliche Beurteilung liegt bei
1.5 (1 = sehr gut - 6 = grottenschlecht).