Algoritmo per testare l'equivalenza dei file

Sembra che tu stia cercando di ottimizzare il confronto dei file perché potrebbe essere un'operazione potenzialmente costosa:

1. Se due file hanno dimensioni diverse, devono essere file diversi.
2. Se il primo e l'ultimo 4K di hash di due file su valori diversi, devono essere file diversi. La prima parte controllerà cose come un identificatore di file comunemente incluso nei primi pochi byte, mentre l'ultimo aiuterà a individuare i casi in cui un file viene aggiunto (ad esempio un file di registro), simile a quanto tail controlla.

Successivamente dovresti confrontare l'intero file solo per essere sicuro. A questo punto potrebbe essere opportuno memorizzare più valori hash (MD5 se la sicurezza non è un problema, SHA2, ecc.). Dovresti essere in grado di trovare un modo per leggere il file una volta e inviarlo a più algoritmi hash. Quindi memorizzi una struttura dati con tutti gli hash, che puoi confrontare molto velocemente con altre strutture dati per altri file.

Se passano tutti questi test (file probabilmente ma non necessariamente uguali), potrebbe essere necessario eseguire un confronto completo dei file.

Penso che il tuo algoritmo sia ragionevole e ritengo che le mie aggiunte minori possano aiutarti.

Sulla base dei chiarimenti nella domanda, penso che il tuo approccio funzionerà. Le probabilità che i file di registro siano della stessa dimensione e il primo e l'ultimo hash delle porzioni uguali sono estremamente bassi. Se si utilizza un algoritmo di hash strong con una dimensione di output elevata (rispetto a MD5), la possibilità è ancora più bassa: con SHA-512 , lo stato interno e l'intervallo di uscita sono ginormi. Dato che stiamo parlando di file di log che molto probabilmente avranno timbri data / ora all'inizio di ogni riga, l'input dovrebbe avere abbastanza entropia per rendere questo un non-problema.

Il tuo approccio è buono ... se i file hanno dati completamente casuali. Ecco alcuni aspetti da considerare:

1. Quanto è grave se ci sono collisioni? Se hai bisogno di una garanzia mission critical (ad esempio quegli astronauti dell'ISS moriranno se si verifica una collisione), il tuo algoritmo potrebbe non essere abbastanza buono, anche se ci sono 10 ^ 38 possibili hash MD5. Le persone vincono la lotteria occasionalmente, dopo tutto, anche se per dati casuali questo è probabilmente sicuro.
2. Questo è il più importante: se i file sono tutti generati allo stesso modo, hanno una formattazione simile, record, informazioni di intestazione / piè di pagina, ecc. allora è possibile che questi file inizino e finiscono esattamente allo stesso modo - e quindi avranno lo stesso hash - anche se non sono uguali.

Quindi, stai abbaiando nell'albero giusto, ma sicuramente presti attenzione ai dettagli reali del tuo caso d'uso per assicurarti di non trascurare qualcosa di ovvio.

La deduplicazione dei dati viene spesso chiamata anche "link linkage", quindi puoi volerlo usare anche come termine di ricerca quando fai ricerche su questo.

C'è un articolo sul blog di ingegneria di Eventbrite che spiega come potresti ridurre notevolmente il numero di confronti tra file usando Hashing sensibile alla localizzazione multi geografica . In breve, si crea un tipo speciale di valore hash per cui documenti simili avranno valori hash vicini. È quindi possibile confrontare i byte di documenti potenzialmente simili per byte in quanto il numero di documenti da confrontare è un set molto più piccolo.

Elaborando un po 'la risposta di Snowman, penso che andrei per una gerarchia di valori hash su (in modo esponenziale) aumentando sottoinsiemi del file, calcolati su richiesta ogni volta che si verificano collisioni e memorizzati in una struttura dati adatta (tabella hash, ma anche un semplice albero di prefisso farebbe) per un rapido accesso futuro. Ciò dovrebbe garantire un fallimento rapido in caso di "quasi identità" e mantenere la complessità del caso peggiore (fino a un fattore log) e ottenere una buona complessità della media.

Sarebbe come segue in pseudo-Python , prendendo come input un file f , un insieme di file D e un dizionario H (di nuovo, si potrebbe fare meglio qui , ma non dovrebbe importare troppo) agendo come una cache per i valori hash precedentemente calcolati:

collisions = [fc for fc in D if size(fc)==size(f)]
size_hash = 4*1024
while (len(collisions) > 0) and (size_hash<=size(f)):
  H[(f,size_hash)] = md5(f,size_hash)
  for fc in collisions:
    if (fc,size_hash) not in H:
      H[(fc,size_hash)] = md5(fc,size_hash)
  collisions = [fc for fc in collisions if H[(fc,size_hash)]==H[(f,size_hash)]]
  size_hash *= 2
for fc in collisions:
  # Painstakingly read and compare content to that of f...

Complessità peggiore: Nel peggiore dei casi, tutti i file hanno uguale lunghezza n , e hanno contenuti MD5 identici (sfortunati!) diversi, quindi uno finisce per calcolare gli hash MD5 per pezzi di dimensioni 4k, 8k, 16k ... n in ciascuno dei file, solo per leggerli completamente dopo.

In termini di tempo, i primi 4k di ciascun file vengono letti per calcolare il primo hash, quindi il primo 8k per il secondo, 16k per il terzo ... quindi l'intera dimensione n. Il calcolo di un MD5 può essere eseguito in tempo lineare, quindi il consumo totale di tempo è (fino a una costante) 4k + 8k + 16k + ... + n < 2n operazioni, cioè rimane nell'ordine di grandezza del confronto finale (inevitabile) dei file.

In termini di memoria, log (n) valori hash MD5 (uno per 4k, uno per 8k ...), ciascuno di dimensioni costanti sarà memorizzato, quindi l'overhead dovrebbe essere ragionevole.

Complessità nella media dei casi: non specificherò l'analisi (le matematiche non sono comunque consentite dal sistema di markdown :)), ma anche assumendo un numero elevato di file di uguali dimensioni, il il numero previsto di valori hash calcolati dovrebbe essere costante in media, quindi questo algoritmo non leggerà parti significative dei file, né coagulerà la memoria.

Senza una certa conoscenza della natura dei file non si può essere sicuri senza eseguire l'hashing dell'intero file. Il controllo della dimensione del file e l'hashing di una parte del contenuto del file sono sufficienti solo se è possibile garantire che i contenuti siano univoci nelle porzioni con hash.