portal Ola

One of the most inconvenient problems occuring on a typical workstation is the problem od duplicate files.

From time to time I copy something somewhere temporarily, or download the same thing many times to different locations.

Such duplicate files can have different names and lie in different directories, but they contain the same data and eat up disk space unnecessarily.

Unfortunately, I didn't manage to find a ready-made utility to effectively detect and reduce such files. And the task is very simple algorithmically.

Actually one needs toproceed along the following scheme:

• traverse a directory tree recursively
• for each given file, store its name in a hash table that's indexed with file sizes
• beforehand, check the hash table if we didn't stubmle upon a file with the same size (tylko pliki o tym samym rozmiarze mogą mieć tę samą zawartość)

• if we had seen a file with the same size, compute checksums of both files (e.g. MD5). If those are identical, we've found a dupe.
• we process the dupe according to our judgment - I, for example, apply a non-destructive approach, that is, I don't destroy any useful information; so in this case I remember the duplicate file's name temporarily, delete it, and replace it with a symlink to the original file, named the same as the dupe. This way, no information gets lost and the storage space occupied by the dupe gets freed.

After conceiving this algorithm (although I don't suppose to be the first one to come up with it) I've implemented it in the form of two Perl scripts:

• dupes_symlink_single_dir.pl eliminates duplicates in a single directory tree (the first file that is found stays untouched, but all its following dupes get substituted with symlinks)
• dupes_symlink_two_dirs.pl operates on two directories. It searches for original files in the first supplied directory subtree, and eliminates all matching dupes from the second supplied subtree.

The scripts are available for download below.

(Update 2008-06: it seems that there's already a program that does this plus more: http://fslint.googlecode.com/svn/trunk/doc/FAQ. The algorithm they use is the same, but it additionally checks whether the duplicate files arent hardlinks of each other and uses SHA1 checksum in addition to MD5. The program has a nice GUI. In short, I recommend checking it out too!)

 Jednym z bardziej uciążliwych problemów zdarzających się na domowej stacji roboczej jest dla mnie problem zduplikowanych plików.

Czasami coś się dokądś tymczasowo skopiuje, czasem dwa razy ściągnie to samo z sieci.

Takie duplikatowe pliki mogą mieć zupełnie różne nazwy i leżeć mogą w różnych katalogach, lecz zawierają to samo i zżerają niepotrzebnie miejsce.

Niestety nie znalazłem gotowego narzędzia, pozwalającego skutecznie takie pliki wykryć i zredkować. A zadanie jest bardzo proste algorytmicznie.

Otóż wystarczy postąpić według następującego schematu:

• przejść rekursywnie po drzewie katalogów
• dla każdego napotkanego pliku zapisać jego nazwę do tablicy haszowej indeksowanej rozmiarem pliku
• uprzednio sprawdzić w tej tablicy, czy nie natknęliśmy się na plik o takim samym rozmiarze (only files with the same size can contain the same data)
• jeśli był już plik o takim rozmiarze, to liczymy sumy kontrolne (n.p. MD5) obu plików. Jeśli są zgodne, to wykryliśmy duplikat.
• z duplikatem postępujemy wedle uznania - ja stosujępostępowanie niedestrukcyjne, t.j. nie niszczę żadnej użytecznej informacji; tak więc w tym przypadku zapamiętuję nazwę duplikatowego pliku, usuwam go, a w jego miejsce tworzę dowiązanie symboliczne (symlink) do oryginału o takiej nazwie, jaką miał duplikat. W ten sposób żadna informacja nie ginie, a miejsce zajmowane przez duplikat zostaje zwolnione.

Po wymyśleniu algorytmu (chociaż nie sądzę, abym był pierwszy, który wpadł na ten pomysł) wcieliłem go w życie w postaci dwóch skryptów w języku Perl:

• dupes_symlink_single_dir.pl wykonuje eliminację duplikatów w pojedynczym drzewie katalogów (pierwszy napotkany plik o danej zawartości pozostaje, kolejne - jego duplikaty - zostają zastąpione symlinkami)
• dupes_symlink_two_dirs.pl operuje na dwóch katalogach. Wykonuje eliminację duplikatów plików z pierwszego katalogu, znajdujących się w katalogu drugim.

Skrypty do ściągnięcia poniżej: