Voglio creare un database con i file. E, per cercare facilmente questi file, voglio usare una specie di tecnica di hashing. Tuttavia, non voglio solo trovare file ESATTAMENTE uguali, ma anche controllare se parti dei file sono uguali (vale a dire che i file sono simili). in altre parole, file simili dovrebbero avere hash simili.Come creare un hash simile per un input simile?
Ciò significa che questo tipo di hash non è davvero un hash crittografico, perché non ci dovrebbe essere un 'effetto valanga' (effetto valanga significa che ogni bit di dati riguarda tutti gli altri bit di altri dati.)
altro La cosa è che l'hash non ha bisogno di essere a senso unico, poiché non è usato per scopi di sicurezza ma per il confronto dei file.
Quindi, in sostanza, sono alla ricerca di un algoritmo in grado di creare un hash univoco per ogni ingresso unico che:
Ha (quasi) senza collisione
Crea un output simile per input simili
È più corto del file originale (altrimenti sarebbe più veloce confrontare semplicemente i file originali).
Stavo pensando a qualcosa come l'aggiunta i primi due personaggi insieme, poi aggiungere il 3 ° e 4rth insieme, ecc, tuttavia, questo ha una quantità enorme di collisione dal "1 + 4" è lo stesso di " 2 + 2 ", ecc.
Non ho davvero idea di come iniziare. Qualcuno potrebbe illuminarmi per favore? :)
Questo è probabilmente molto difficile. Esaminare http://en.wikipedia.org/wiki/Agrep –
se il lavoro è trovare i file con byte comuni, [ssdeep] (http://ssdeep.sourceforge.net/), è grandioso. –
Dovresti creare un algoritmo di compressione, seguito da un ordinamento. Dovresti utilizzare le stesse tabelle di frequenza per tutti gli input compressi in modo da rendere le cose deterministiche. – sehe