Schrift
[thread]7056[/thread]

Doppelte Dateien erkennen



<< >> 7 Einträge, 1 Seite
Strat
 2005-06-19 01:27
#55539 #55539
User since
2003-08-04
5246 Artikel
ModeratorIn
[Homepage] [default_avatar]
Hallo Leute,

ich stehe gerade vor dem Problem, doppelte Dateien moeglichst effizient zu finden. Ich glaube, ich habe einen recht effizienten Algorithmus gefunden; faellt euch vielleicht was effizienteres ein?

Mir ist dabei folgender Algorithmus eingefallen:
Quote
Lese alle Dateien und speichere sie in einem Hash mit der folgenden Struktur:
Code: (dl )
1
2
3
%hash = ( -s $file1_0 => [ $file1_0, $file1_1, $file1_2, ...],
-s $file2_0 => [ $file2_0, $file2_1, ...],
...);

und dann den hash durchlaufen und wenn irgendwo mehr als ein Element im Value ist, dann auf doppelte vergleichen.

Es handelt sich um etwa 400000 Dateien, alle so zwischen 10kb und 300kb gross, und es ist sehr unwahrscheinlich, dass eine Datei oefter als 2x vorkommt... Falls sehr viele Dubletten vorkommen koennen, waere vielleicht das hashing mit Digest::MD5 eine interessante Alternative.



Habe mal auf die Schnelle den folgenden Code zusammengebastelt. wegen der Fortschrittsanzeige verwende ich einen thread... (war da nicht gerade mal ein RDW?); da da die Festplatte das Nadeloehr ist, duerfte der thread kaum ins Gewicht fallen...
Code: (dl )
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
#! /usr/bin/perl
use warnings;
use strict;
use threads;
use threads::shared;

use File::Find ();
use File::Compare ();

use vars qw(@RootDirs %Files);

@RootDirs = ('H:\test\');

print STDERR "Reading Files and sorting them...\n";
my $filesCount = 0;
File::Find::find(sub {
if (-f $_) {
push (@{ $Files{-s _} }, $File::Find::name);
if ($filesCount and $filesCount % 5000 == 0) {
print STDERR "$filesCount files read\n";
} # if
$filesCount++;
} # if
}, @RootDirs);
print STDERR "$filesCount files read and sorted\n\n";

my $compareCount : shared = 0;
my $doubleCount : shared = 0;
my $finished : shared = 0;

print STDERR "Comparing files...\n";
my $thread = threads->create(\&CompareFiles);
while ($finished == 0) {
sleep(5);
printf STDERR "%2d%%\t$compareCount/$filesCount => $doubleCount\n", $compareCount*100/$filesCount;
} # while

$thread->join();
# ------------------------------------------------------------
sub CompareFiles {

foreach (keys %Files) {
my @items = @{ $Files{$_} };
my $count = $#items;
$compareCount += $count+1;

next if $count == 0;
for my $i (0..$#items-1) {
for my $j ($i+1..$#items) {
my $cmp = File::Compare::compare($items[$i], $items[$j]);
if ($cmp == 0) {
$doubleCount++;
print "$doubleCount\tA:\t$items[$i]\n";
print "$doubleCount\tB:\t$items[$j]\n\n";
} # if
} # for
} # for
} # foreach

print STDERR "Compared: $compareCount files: 2*$doubleCount Duplicates\n";

$finished = 1;
} # CompareFiles
# ------------------------------------------------------------
\n\n

<!--EDIT|Strat|1119130106-->
perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/
esskar
 2005-06-19 06:47
#55540 #55540
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
kommt drauf an...
wenn das etwas ist, dass genau einmal läuft, ist es wohl schnell...
falls das ding öfers läuft, würde ich für jede datei einen digest berechnen und <dateiname><modifiedtime> => <digest> abspeichern und beim nächsten lauf aktualisieren und vergleichen...
kabel
 2005-06-19 19:45
#55541 #55541
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
cat /dev/brain:

[s]- dateien können nur gleich sein, wenn sie die gleiche größe haben.[/s]edit: macht der code schon ...
- die vielen dateien nicht gleichzeitig bearbeiten, sondern in größenklassen einteilen und die dann bearbeiten (zielt auf parallelisierung)
- eine in C geschriebene compare funktion benutzen.\n\n

<!--EDIT|kabel|1119196102-->
-- stefan
Rambo
 2005-06-19 19:45
#55542 #55542
User since
2003-08-14
803 Artikel
BenutzerIn

user image
jep hier ist was über verlaufsanzeige
RDW 02/05

was mein code teil betrifft setze ich diesen sehr gerne bei grossen copy und unzip dateien ein.

fürti rambo
Dubu
 2005-06-20 01:58
#55543 #55543
User since
2003-08-04
2145 Artikel
ModeratorIn + EditorIn

user image
Sowas habe ich mir auch mal geschrieben, um Ordnung auf meiner Festplatte zu halten. Es macht aber keinen tatsaechlichen Dateivergleich, sondern vergleicht nur die MD5-Digests.
Code: (dl )
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
#!/usr/bin/perl
# finddupes - find duplicate files by MD5 digest
#
use strict;
use warnings;
use File::Find;
use Digest::MD5;

my %FilesBySize;

# default: current directory
@ARGV = qw/./ unless @ARGV;

# find all files
find ({wanted => \&add_file, no_chdir => 1}, @ARGV);

find_duplicates();

exit 0;

###########################################

sub add_file {
   return unless -f $_;
   my $size = -s _;
   return unless $size;
   push @{$FilesBySize{$size}}, $File::Find::name;
}

sub find_duplicates {
   for my $s (sort {$a <=> $b} keys %FilesBySize) {
       next unless @{$FilesBySize{$s}} > 1; # more than 1 file?

       my %md5s = ();
       for my $f (@{$FilesBySize{$s}}) {
           my $md5 = calc_md5 ($f);
           push @{$md5s{$md5}}, $f;
       }
       for my $md5 (keys %md5s) {
           if (@{$md5s{$md5}} > 1) {
               print "Identische MD5-Summe (mit $s Bytes): \n";
               print "\t$_\n" for @{$md5s{$md5}};
           }
       }
   }
}

sub calc_md5 {
   my $file = shift;
   open(FILE, $file) or warn "can't open '$file': $!\n";
   binmode(FILE);
   my $md5 = Digest::MD5->new;
   while (<FILE>) {
       $md5->add($_);
   }
   close(FILE);
   return $md5->b64digest;
}
esskar
 2005-06-20 02:21
#55544 #55544
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
[quote=Dubu,19.06.2005, 23:58]Es macht aber keinen tatsaechlichen Dateivergleich, sondern vergleicht nur die MD5-Digests.[/quote]
dann hättest du wohl eine von diesen beiden dateien gelöscht:

Code: (dl )
1
2
http://www.cits.rub.de/imperia/md/content/magnus/letter_of_rec.ps
http://www.cits.rub.de/imperia/md/content/magnus/order.ps


;)\n\n

<!--EDIT|esskar|1119219729-->
Strat
 2005-06-20 13:35
#55545 #55545
User since
2003-08-04
5246 Artikel
ModeratorIn
[Homepage] [default_avatar]
[quote=kabel,19.06.2005, 17:45]- die vielen dateien nicht gleichzeitig bearbeiten, sondern in größenklassen einteilen und die dann bearbeiten (zielt auf parallelisierung)
[/quote]
Grundsaetzlich waere sowas ueber %Files problemlos moeglich; ich sehe jedoch nicht, was das an Geschwindigkeit bringen soll, weil das Nadeloehr die Festplatte ist. Und auch sonst bringt eine parallelisierung (ausser vielleicht bei mehreren CPUs oder Abfragen auf verschiedene oder externe Systeme) fast nie einen Laufzeitgewinn, sondern macht ein Programm insgesammt langsamer, auch wenn es durch schnellere Reaktionen zunaechst schneller erscheint.

Und weil das Teil moeglichst portabel sein soll, habe ich mich auch zu threads entschieden und verwende kein fork.

[quote=kabel,19.06.2005, 17:45]
- eine in C geschriebene compare funktion benutzen.[/quote]
das koennte was bringen.
perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/
<< >> 7 Einträge, 1 Seite



View all threads created 2005-06-19 01:27.