Y a-t-il un moyen fiable de déterminer si deux fichiers sont identiques ou non? Par exemple, deux fichiers avec la même taille et le même type peuvent être ou ne pas être le même binarilly (oui, je sais que ce n'est pas vraiment un mot). Je suppose que comparer une ou deux checksums des fichiers aidera, mais je me demande:
Des idées, des suggestions ou des pensées sont appréciées!
P.s. Le code pour cela est en cours d'écriture dans Java en cours d'exécution sur un système Nix, mais une entrée agnostique générique ou la plate-forme est la plus utile.
4 Réponses :
1) Very reliable 2) Not theoretically 3) SHA-1
Ne devrait-il pas 2) être "pas dans la pratique" ou "théoriquement"? La fiabilité augmente certainement de la théorie.
Ah, tu veux dire qu'il voulait dire plusieurs sommets? Comme avoir un SHA1 et MD5?
@ZAF: Oui, au moins j'espère qu'il voulait dire ça :).
@Ivlad je suppose que "pas théoriquement" s'applique toujours alors;)
@IVLAD est correct, il y a une petite chance deux fichiers pourraient avoir la même somme de contrôle et utiliser plusieurs checksums diminue de la probabilité, de sorte que, de manière théoriquement, qui augmenterait la fiabilité. Les checksums sont si fiables dans la pratique, cependant, que cela n'est pas nécessaire. De plus, CRC32 constitue un meilleur choix pour cette application: nous ne sommes pas concernés par une contribution malveillante, et c'est beaucoup plus rapide que SHA1.
@Blueraja: Lorsque vous utilisez CRC32, la probabilité de deux fichiers aléatoires ayant la même somme de contrôle est de 1 à 4294967296. Lors de l'utilisation de SHA-1, il est supérieur à 1 à 1,46 * 10 ^ 48. Si vous comparez les checksums CRC32 de tous les fichiers que vous avez jamais vus ou verrez dans votre vie, au moins deux fichiers auront la même somme de contrôle. Pour SHA-1, vous ne vivez pas assez longtemps pour que cela se produise ;-) Cependant, la même chose serait vraie pour le MD5 déjà et MD5 est un peu plus rapide que SHA-1.
@BLUERAJA: Exécutez un programme pour supprimer tous les doublons à l'aide de CRC32 dans un énorme ensemble de fichiers et vous pouvez embrasser vos données au revoir.
@Mecki et @longpoke: lorsque cela faisait cela dans le monde réel, vous utilisez CRC32 pour trouver des doublons; C'est ce qui est fait pour. Non seulement calculer un CRC32 nettement plus rapide que le calcul d'un hachage SHA1, mais comparer deux sorties CRC32 (que vous devrez faire beaucoup ) est également de manière significative plus rapide, puisque CRC32 S'adapte à (sur la plupart des processeurs) un registre unique. Cependant, vous ne reposez pas uniquement sur la somme de contrôle, lorsque vous utilisez CRC32 ou SHA1 ou quoi que ce soit d'autre: à l'occasion rare que deux fichiers ont la même somme de contrôle, vous devez toujours effectuer une comparaison d'octets par octets des fichiers.
@Blueraja: Pourrait-il être coincé dans le 90ème? ;-) Chaque application que je sais qui a été écrite ce siècle utilise au moins MD5 à cette fin. Considérant qu'un processeur moderne peut être un deuxième MC 500 Mo de données une seconde (à l'aide d'un seul noyau uniquement!), La plupart des disques durs ne peuvent même pas lire que beaucoup de données une seconde. Le MD5 a également une meilleure répartition du bit que CRC, cela signifie qu'il est beaucoup plus probable que deux fichiers soient considérés comme différents après seulement comparer les deux premiers octets d'une somme de contrôle MD5 qu'à une somme de contrôle de la CRC. Une somme de contrôle de CRC ne peut être différente que lors du dernier octet.
Un algorithme de contrôle standard comme MD5 vous donnera un test fiable, pour la plupart des scénarios de vie réels. Si vous avez besoin d'une fiabilité encore plus, allez SHA. http://fr.wikipedia.org/wiki/cryptography_hash_function#cryptographic_hash_algorithms
Il est impossible de savoir avec certitude si deux fichiers sont identiques ou non à moins que vous ne les comparez à des octets d'octets. Il est similaire à la manière dont vous ne pouvez pas garantir qu'une collection ne contient ou ne contient pas d'objet donné que si vous vérifiez chaque article de la collection.
Les checksums sont fondamentalement un hachage. S'ils sont suffisamment bons pour vos besoins dépend de la manière dont votre application est critique. Il est certainement possible de créer une fonction de hachage avec un faible risque de collision; Après tout, les mots de passe sont hachés, même dans des situations où ils protègent les données sensibles et vous ne voudriez pas avoir un deuxième mot de passe valide sur votre compte. Sauf si vous écrivez un code pour, dites, une banque, un algorithme de contrôle fort devrait fournir une très bonne approximation.
L'utilisation de plusieurs checksums augmentera la fiabilité si et uniquement si les différents algorithmes de contrôle utilisent des fonctions de hachage dissemblables.
Votre troisième question a déjà été prise en charge par la réponse de LeonBloy; MD5 et SHA-1 sont courants.
Les checksums sont fondamentalement un hachage. C'est l'inverse - les hachages sont essentiellement des checksums, mais avec des exigences plus strictes. Il est certainement possible de créer une fonction de hachage avec un faible risque de collision Les hachages sont conçus pour avoir un risque de collision aussi faible que possible. Toute autre chose n'est tout simplement pas un hasch. Un algorithme de somme de contrôle forte devrait fournir une très bonne approximation [d'un hachage] Les hachages et les checksums sont des bêtes similaires à des fins très différentes. CRC32 est une bonne somme de contrôle, mais un hachage moche. Bcrypt est un grand hash, mais une somme de contrôle moche (c'est trop lent).
+1 pour équilibrer "la confusion claire" de Blueraja. Si vous en pensez une fonction de contrôle et une fonction de hachage sont identiques, la seule différence est la manière dont vous utilisez le résultat.
Aucune explication de Foire, Blue Raja n'était pas là il y a 2 minutes lorsque j'ai commencé le commentaire précédent. Maintenant, en réponse, votre critique n'est pas essentielle à ce qu'est un checksum ou un hachage. Plutôt, vous dites que seules les bonnes fonctions de hachage sont des hachages et de bonnes checksums sont des checksums.
@Blueraja, nous entrons en sémantique. C'est parfaitement légal, bien que stupide, d'écraser la méthode de Java pour renvoyer la même valeur pour chaque objet. Aux fins de cette question, je pense qu'il est raisonnable de définir le hasch comme une manipulation des données d'entrée dans un résultat unique, probablement unique. Semblable au commentaire de Ukko.
@Lord: Ah, je vois, nous utilisons deux définitions distinctes de "hachage" - je parlais de cryptographique Hays (qui est devenu la signification courante du terme "hachage"), alors que vous parliez du " codes de hash " utilisé par les tables hachables (et al.). Je suis tellement habitué à discuter des hachages cryptographiques (autres réponses mentionnées SHA1 et MD5, par exemple), j'ai dû perdre ma tête. Si vous modifiez votre réponse, je supprimerai le bowvote.
@Blueraja, édité. J'étais assez confus au début, parce que je n'ai pas de fond crypto; Il est intéressant de lire que vous avez amitié directement m'a conduit. Merci!
Toute somme de contrôle vous donnera un faux positif pour un très petit nombre de cas. Si vous pouvez vivre avec ça, bien. Sinon, le moyen de faire cela est de faire la comparaison de la somme de contrôle en premier, et si les checksums sont égaux à un test d'octet par octet. Le test d'octet-byte sera effectué très rarement, de sorte que les coûts en moyenne sur beaucoup de comparaisons seront très petits. Cependant, ce n'est pas le cas lorsque la plupart de vos comparaisons devraient renvoyer «vrai».
Cela dépend également du nombre de fichiers différents que vous testez. Calculer une somme de contrôle de fiabilité élevée est presque aussi coûteuse que la comparaison - si chaque fichier est comparé à environ une fois, il peut être moins coûteux de faire les comparaisons.
Nourriture supplémentaire pour la pensée ... Je travaillais sur quelque chose de similaire à la radiation de fichiers en double et a constaté que faire des sommes partielles ont considérablement augmenté le processus. Compute SHA-1 sur le premier 4k. S'ils sont les mêmes, effectuez tout le fichier. Vous pouvez également comparer directement les premiers 4k octets, baiser sur la première différence. Tout dépend de votre but final.