È necessario leggere ogni singolo byte per verificare se un file copiato è identico all'originale?

Il calcolo dei CRC (o, meglio, sha1sums) su entrambi i file richiede comunque la lettura di ogni byte. Se esegui un confronto byte per byte, puoi uscire non appena vedi una mancata corrispondenza e non devi preoccuparti di due file diversi che hanno lo stesso checksum (anche se è incredibilmente improbabile per sha1sum) . Quindi, se stai facendo il confronto localmente, un confronto byte per byte sarà almeno veloce come un confronto di checksum (a meno che tu non abbia già calcolato i checksum comunque).

D'altro canto, i confronti del checksum sono utili quando si confrontano file che non si trovano sulla stessa macchina; i checksum possono essere calcolati localmente e non è necessario trasferire l'intero contenuto sulla rete.

Sono possibili anche approcci ibridi. Ad esempio, è possibile calcolare e confrontare i checksum dei due file un blocco alla volta, il che può evitare di leggere l'intero file ( se sono diversi) evitando al contempo di trasmettere l'intero file attraverso la rete. Il protocollo rsync fa qualcosa del genere.

Si noti che l'utilizzo di un semplice CRC offre una buona probabilità di collisione, come ha detto Dave Rager nella sua risposta. Usa almeno sha1sum, o anche qualcosa di più recente. (Non tentare di inventare il proprio algoritmo di hashing, le persone che hanno sviluppato sha1sum sanno molto più su questa roba di noi due.)

Per quanto riguarda la probabilità di collisione, se usi un hash decente come sha1sum, non devi preoccuparti di questo, a meno che qualcuno non stia deliberatamente e costoso costruendo file i cui sha1sum si scontrano (generando tali collisioni erano non fattibili quando ho scritto per la prima volta questo, ma progress è in corso ). Citando "Pro Git" di Scott Chacon , sezione 6.1 :

Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

Riepilogo:

Il confronto byte per byte è utile per i confronti locali. sha1sum è utile per il confronto remoto e non presenta alcuna possibilità significativa di falsi positivi.

Ecco un altro modo per pensarci.

Se non ci sono possibilità che due file diversi abbiano lo stesso CRC, quindi per estensione significa che ogni file può essere rappresentato da un CRC univoco. Se il CRC fosse più piccolo del file originale, rappresenterebbe una forma di senza perdita di dati compressione. In caso contrario, farebbe altrettanto bene confrontare i file originali in quanto dovresti confrontare lo stesso numero di byte.

In teoria è possibile utilizzare la compressione senza perdita di entrambi i lati del confronto per ridurre il numero di byte necessari nel confronto, ma è una commissione errata perché si sprecano più cicli e si deve leggere ogni byte di entrambi i file per fare la compressione. Cioè, per codificare ogni byte (e il suo ordine) in uno schema di compressione senza perdita, dovresti prima leggerlo e inserirlo nell'algoritmo, giusto? Game over.

Ecco un'analogia:
Se si desidera un modo per determinare rapidamente se due documenti stampati erano identici senza confrontare lettera per lettera, è possibile confrontare il conteggio delle lettere su ciascuna riga dei documenti. Se i conteggi sono tutti uguali, le probabilità migliorano in modo sostanziale che i documenti sono identici, tuttavia nessuno sosterrebbe che si possa essere certi che ogni lettera sia la stessa con questo approccio.

L'unico modo perfetto per verificare la presenza di file identici è il confronto byte per byte. Un altro modo per avere una buona approssimazione è calcolare un hash come MD5 per i file e confrontarli. È possibile che ci possa essere una collisione hash ma non molto probabile.

Immagino che il byte per il confronto dei byte sia più veloce del calcolo dell'hash su entrambi i file al momento del confronto. Tuttavia, se l'applicazione esegue il calcolo preliminare dell'hash e memorizza i metadati relativi ai file, il confronto degli hash sarà notevolmente più rapido.

Il CRC probabilmente non è la soluzione giusta perché è solo un meccanismo di rilevamento degli errori, non un hash. (o un hash povero con molte possibili collisioni)

Per essere sicuri al 100% due file sono identici, è davvero necessario controllare i byte.

Perché? Hash collisioni, ecco perché! A seconda dell'algoritmo utilizzato per l'hashing, la collisione potrebbe essere più o meno probabile, ma non è comunque possibile. Seguendo questi passaggi:

1. Controlla le dimensioni del file
2. Controlla i tipi di mime
3. Controlla hash
4. Controlla alcuni offset casuali e confronta i bit

Ti garantirai con certezza assoluta che i due file sono uguali, tuttavia c'è una (molto) piccola possibilità che tu abbia una collisione tra le tue mani. La scelta di quanto lontano vuoi andare con i tuoi confronti sarà dettata dalla situazione.

Come altri hanno già detto è più veloce fare un confronto byte per byte se i due file si trovano sullo stesso sistema. Se stai cercando di confrontare un gruppo di file, raggiungerai il punto in cui l'hashing è la risposta migliore se i file sono in memoria di rotazione.

L'hashing brilla davvero quando non hai tutti i dati facilmente disponibili. Ad esempio, i file si trovano su macchine diverse. Consente inoltre di salvare i risultati dei calcoli e di consultarli in seguito. (Questo rapporto è lo stesso di quello vecchio? Quando fai il rapporto, salva un hash di esso. Quando fai il prossimo puoi semplicemente confrontare gli hash. Non solo non hai bisogno di leggere quello vecchio in te don ' t ho anche bisogno di avere una copia disponibile.)

Penso che dovresti usare l'utilità di confronto dei file fornita con il tuo sistema operativo o usare uno strumento per confrontare i file (vedi: file wiki confronta gli strumenti ) per confrontare i contenuti DOPO aver controllato le proprietà del file delineate da @Glenn Nelson.

Non penso che CRC sia preciso al 100% e penso che la sua precisione diminuisca con la lunghezza del file. Inoltre, non ti suggerisco di scriverlo da zero in quanto potrebbe richiedere molti test.

È necessario leggere ogni singolo byte per verificare se un file copiato è identico all'originale? SÌ per essere sicuro al 100%

È necessario leggere ogni singolo byte per verificare se un file copiato NON è identico all'originale? NO

Quindi, per determinare rapidamente la non identità, prima controlla i metadati come le dimensioni del file e qualsiasi tipo di checksum / CRC o MIME che il sistema operativo / archivio / archivio potrebbe già mantenere . Dal momento che sono precalcolati da quel sistema, non pagherai questo costo al momento del confronto.

Se il test viene superato, è comunque necessario confrontare ogni singolo byte se è necessario essere sicuri al 100%, MA NOTA: nelle moderne CPU pipeline e utilizzando più thread e probabilmente più processori / CPU, facendo confronti di blocchi di file di grandi dimensioni è REALMENTE veloce ed efficiente perché il processo è altamente parallelizzabile . Molto più veloce di QUALSIASI tipo di calcolo matematico che coinvolge ogni byte (anche se alcuni algoritmi sono forse anche parallelizzabili, ma forse non così facilmente o così bene). Questo perché le CPU che sono pipeline possono eseguire operazioni di confronto a blocchi di memoria in microcodice o anche hardware (molto veloce) e sottosistemi disk-to-memory sono altamente ottimizzati per portare enormi blocchi di file alla / dalla memoria, tutto fatto in parallelo e con hardware. Se la tua applicazione fa questo genere di cose regolarmente, ed è un noto collo di bottiglia delle prestazioni, sarebbe saggio implementarlo in un codice multithread ben scritto che sfrutta le funzionalità di parallelizzazione del tuo sistema operativo e hardware (forse usa un linguaggio progettato per questo).

Solo se si desidera elaborare ciascun file una volta e fare più confronti in un secondo momento (dove si ricorda ["cache"] il risultato dell'analisi sintetizzato, o "compresso" [come JohnFX]), ci sarà un beneficio significativo per facendo così, e anche allora, solo per dimostrare la differenza (probabile); per dimostrare l'identita ', avresti ancora bisogno di fare il confronto byte per byte.