Porovnávání adresářů

[Jirka Kosina]

On Sat, 6 Sep 2003, Oak wrote:

> už dlouho se trápím různýma složitýma postupama na vyhledávání duplicit 
> souborů nebo celých adresářů. Vyzkoušel jsem několik programů, jako je 
> Kompare (používá diff), ale ty slouží ke hledání _odlišností_ v přibližně 
> shodných soubrech či adresářích, zatímco já bych potřeboval hledat _shody_ 
> v naprosto odlišných adresářích či celých soub. systémech (opak :-).
> Neexistuje něco šikovnýho? Za šikovnost bych považoval třeba porovnání 
> obsahu (např. přes MD5), pokud se nějaké soubory shodují názvem, případně 
> velikostí.

Pokud byste nejdriv chtel testovat ze se soubory shoduji ve velikosti a v 
nazvu, a pak z nich pocital md5, mate to neoptimalne napriklad timto 
zpusobem:

; vygenerovat pro oba adresare seznamy souboru s jejich velikostmi
find /nejaka/cesta -exec wc -c {} 2>/dev/null \; > FIRST
find /jina/cesta -exec wc -c {} 2>/dev/null \; > SECOND

; jednim while cyklem (v shellu) cist obsah souboru FIRST (napriklad)
; a v souboru SECOND k nemu hledat odpovidajici zaznamy. Neoptimalne
; treba pomoci grepu
cat FIRST | while read SIZE FNAME; do
        BASE=`basename "$FNAME"`
        echo "Hledam $BASE o velikosti $SIZE v SECOND"
        RESULT=`grep "$SIZE .*$BASE" SECOND`
        if [ -z "$RESULT" ]; then
                echo "Neni tam"
        else
                echo "Je tam"
        fi
done

Ve vetvi "Je tam" si pak jen spocitate MD5 soucty souboru $FNAME a 
souboru, jehoz plne jmeno je druhy sloupec promenne $RESULT (ktere z teto 
promenne vytahnete napriklad pomoci programu cut nebo awk), a hned vite, 
jestli se jedna o stejne soubory nebo ne.

Toto se vyplati, pokud predpokladate, ze soubory jsou dostatecne velike a 
nevyplatila by se na to ta uplne nejtupejsi metoda - tedy si spocitat 
md5ky vsech souboru v obou porovnavanych adresarich, a pak je jen timto 
zpusobem porovnat.

Navic je tento mnou navrhovany postup kvadraticky, co se tyce casove 
slozitosti - pro kazdou radku souboru FIRST se znova prochazi (grepem) 
soubor SECOND. Slo by to vylepsit, kdyby se vystupy setridily napriklad 
podle velikosti (sort to udela v O(n*log(n))), a pak by se kandidati na 
shodnou dvojici souboru hledaly a-la slevaci postup pri mergesortu, tedy v 
O(n).

-- 
JiKos.