[gull] Petit problème de maths, pour créer de liens

[Leopoldo Ghielmetti]

Il giorno gio, 01/05/2008 alle 17.03 +0200, Sebastien Chassot ha
scritto:
> Salut,
> 
> tout d'abord j'espère avoir à peu près compris ton problème et n'ayant
> pas de très bonne connaissance dans ce domaine, je lance juste deux
> trois idées.
> 
> premièrement tu parles de gagner du temps en ne vérifiant qu'un
> pourcentage des fichiers dans la phase deux. Est-ce que ce ne serait pas
> mieux de le faire dans la phase un (en sortant un md5 sur qqs block
> seulement) puisque tu risques au pire d'avoir plus de fichiers à
> tester ? Le gains de temps est peut-être faible mais au moins sans
> risque.
> 
> Avant de comparer l'intégrité de deux fichiers j'imagine que tu ne le
> feras que pour des fichiers qui se ressemblent "beaucoup" et que tout
> les testes plus rapides et qui éliminent les faux doublons auront été
> effectués (taille,...)
> 
> Pour ce qui est du hashage c'est vrai que que le risque que deux
> fichiers différents aillent la même taille, la même somme,... est
> statistiquement nul. Il n'y a pas beaucoup de sens à avoir une certitude
> sur l'intégrité de tes données si le risque de perte par défaillance du
> matériel est infiniment plus grand.
> 
> Finalement concernant le hashage (encore une fois je n'y connais pas
> grand chose.) Tu peux tester la ressemblance entre deux fichiers.
> Calculer la somme md5 depuis le début et aller plus ou moins loin dans
> le fichier (10%, 20%, 50%,...) en allant jusqu'à 100% tu as la certitude
> que les fichiers bloc à bloc identique. Mais pour qu'une somme md5 soit
> identique alors que les fichiers ne le sont pas il faut que les deux
> fonctions de hashage soient les mêmes à partir d'un certain nombre de
> blocs et que les blocs qui suivent soient identiques pour les deux
> fichiers. Mon avis est qu'il vaut sans doute mieux chercher des
> différences plutôt que la similitude. Je pense (je n'ai pas calculé) que
> la probabilité que les 10% des deux fichiers soient les mêmes au début
> est plus grande que la probabilité d'avoir 10% identique sur des
> portions prises au hasard. De prendre une partie au début, une au milieu
> et une à la fin offrirait une meilleur probabilité que les fichiers
> soient identiques. Encore une fois la différence est à mon avis
> théorique mais pas significative.

Ça dépend, imagine un fichier .c qui serait corrigé pour changer juste
une lettre quelque part dans le fichier. Si on compare juste un petit
morceau (au début, au milieu ou à la fin) on n'est pas du tout sûr de
tomber sur le byte qui a été corrigé. On risque donc de croire que les
deux fichiers sont identiques.
Je pense que ce test partiel peut être utilisé pour dire que deux
fichiers sont différents, mais pas du tout pour supposer qu'ils sont
identiques. Pour cela il faut calculer la md5 complète des deux
fichiers, voir faire un diff.

> Si tu as plus de chance de gagner 1000 fois d'affilée au loto que
> d'avoir 2 fichiers avec 1% de ressemblance et une somme md5 identique,
> tu peux prendre le risque.

ciao, Leo