Dotaz: Duplicitni soubory

[martin]

Zdravím,
Zrovna včera jsem se rozhodl že si už konečně udělám pořádek ve fotkách.
Mám milion adresářů s fotkama některé samozřejmě i 3x.
Celkem to dělá asi něco kolem 5k kousků.
Pustil jsem na to jeden nejmenovaný komerční soft ale po 3 hod jsem už byl docela grogy.
Výstupní adresář obsahoval něco kolem 2k fotek a ještě hafo zbývalo.
Přečetl jsem tu ted nějaký příspěvek na téma
Nejlepší hashovací fce a napsal toto

#encoding: utf-8
'''Programek na rychlou detekci duplicitnich souboru v adresari
'''
import os, hashlib

class DupFinder(object):
    def __init__(self, adresar):
        self.database = {}
        self.__get_all_files(adresar)
        print len(self.database)
        del(self.database)
        
    def __get_all_files(self, adresar):
        dupe = 0
        for root, adresar, soubory in os.walk(adresar):
            for soubor in soubory:
                with open(os.path.join(root, soubor), 'rb') as f:
                    hashfile = hashlib.sha224()
                    hashfile.update(f.read())
                    newhash = hashfile.hexdigest()
                    if newhash not in self.database:
                        self.database[newhash] = os.path.join(root, soubor)
                    else:
                        dupe += 1
        print ('NR Dupes in directory: %d' % dupe)
        
if __name__ == '__main__':
    a = DupFinder('/home/martin/Fotky')

Celkový čas něco kolem 10min[mám tam dopsaný přesun atd].
Opravdu se tomu dá věřit že to najde duplikáty na 100% ?.
Díky za jiné návrhy, třeba třídění podle spektrální analýzy atd :).

Odpovědi

[Filip Jirsák]

Pokud použijete hash z binárních dat souboru, duplicitní soubory (tj. ty, které jsou na bit stejné) tím určitě odhalíte, s nízkou pravděpodobností se může stát, že jako shodné budou označeny dva různé soubory – ale myslím, že není problém ty soubory se stejným hashem porovnat bit po bitu.

[martin]

Díky to jsem potřeboval vědět. Jen mě zajímá jestli i tato malá pravděpodobnost se dá
obejít jiným druhem použitého hashe třeba sha1, sha512, md5.
BTW a nebylo by to prolomení klíče kdyby 2 rozdílné soubory měly
stejný hash ?

[Filip Jirsák]

Oebjít se to nedá, ta pravděpodobnost bude vždy nenulová. Hashovací funkce vždy přiřazuje nekonečně mnoho různých vstupů na konečně mnoho výstupů, takže vždy existují výstupy, kterým odpovídá nekonečně mnoho vstupů.

Kdyby dva různé soubory měly stejný hash, jde o nalezení kolize – pro hashovací funkci to není žádný problém, ty s přítomností kolizí počítají (jak jsem psal v předchozí větě), jejich síla spočívá v tom, že ke známému hashi nedokážeme rychle najít nějaký vstupní dokument, případně že nejde snadno vytvořit dva různé vstupy, které mají stejný hash.

Jinak pro hledání duplicitních souborů mi kryptografické hashovací funkce připadají jako trochu silný nástroj, podle mne by stačil třeba obyčejný CRC, který spočítáte rychleji, a u stejných otisků pak stejně soubory porovnáte bit po bitu.

[oroborus]

BTW Pred par tyznami som rozmyslal, ze by som naprogramoval program na vyhladavanie duplicitnych suborov. Myslim, ze si teraz najdem na to cas :)