/blog/perl


substr() in Perl
[127908 mal gelesen]
foreach in Perl
[116785 mal gelesen]
Arrays in Perl - Besonderheiten
[109927 mal gelesen]
open() - Dateien öffnen in Perl
[98187 mal gelesen]
split() in Perl - Zeichenketten teilen
[89818 mal gelesen]
chomp() in Perl
[84894 mal gelesen]
grep - Listen durchsuchen in Perl
[82184 mal gelesen]
push in Perl
[79221 mal gelesen]
sleep in Perl - Das aktuelle Script warten lassen
[61788 mal gelesen]
print in Perl
[50029 mal gelesen]


Arrays
Dateien
HTPC
Hashes
Leistungsoptimiert
PHP
Perl
RegEx
Schleifen
Script
Skalare
Sonstiges
System
Webserver
Zur Startseite


Mittwoch, 25.4.2007, 11:15:37 Uhr

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 8805 mal gelesen.

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

Kommentar schreiben  Druckansicht  Seitenanfang 
Beurteilen 






 Zufällige Beiträge im /blog/perl

Leitrechner steht auf 0

while in Perl

Uhrzeit und Datum bestimmen in Perl

Neue Suchfunktion - die 2.

Dateiendung herausfinden mit Perl

Gruppenbildung in Perl

read() - Bestimmte Anzahl Zeichen aus Datei einlesen

push in Perl

Mein HTPC - Weitere Erfahrungen



0.0182511806488037 sec. to build



...Blogsoftware in pure Perl - Powered by a lot of Coffee...


SSD-Festplatte - Wassn das???
Die Transliteration - Nur ein Zeichen in einem Skalar ersetzen
Select - Case in Perl
Windows 7 XP Mode – Wo finde ich den XP-Modus unter Windows 7?
Mac-Adresse beim Apple Macintosh herausfinden
SGN-Funktion für Perl
truncate - Dateigröße verändern in Perl
Eigene IP herausfinden mit Perl
Epoche live in Datum umwandeln
Firefox 3 - Exe-Files downloaden


Von: Fabian
Kommentar:
Hallo zusammen,
ich suche schon etwas im Internet und bin bisher nicht fündig geworden.
Zum Beitrag


Von: Schorschel eastcoast
Kommentar:
Danke. Das hat mir weitergeholfen.
Zum Beitrag


Von: Jessica
Kommentar:
Kann man auch zwei Datein parallel einlesen?

Zum Beitrag


Von: Xtravaganz
Kommentar:
Für

Zum Beitrag


Von: Xtravaganz
Kommentar:
Für

Zum Beitrag



Gesamtverzeichnis
Februar 2010
Dezember 2009
Oktober 2009
Januar 2009
Dezember 2008
November 2008
September 2008
August 2008
Juli 2008
Juni 2008
Mai 2008
April 2008
Januar 2008
Dezember 2007
November 2007
Oktober 2007
September 2007
August 2007
Juni 2007
Mai 2007
April 2007
März 2007
Februar 2007
Januar 2007
Dezember 2006


Mister Wong

RSS-Feed

Heute ist der
19.9.2018

Es ist
3:50:57 Uhr

Ihre IP:
54.198.52.82

Blog-Einträge: 186

Die letzten 24 Stunden im Überblick


Gelesene Beiträge insgesamt:
3713530


Webseiten vergleichen
Kalender mit Feiertagen - 2028
Links finden und testen
Menschliche Datumsangaben
IP zu Domain herausfinden
Time live in Datum umwandeln
Perl für Windows



Mo Di Mi Do Fr Sa So
12
3456789
10111213141516
17181920212223
24252627282930

Impressum