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

[Sebastien Chassot]

On Mon, 2008-05-05 at 21:22 +0200, Leopoldo Ghielmetti wrote:
> Il giorno gio, 01/05/2008 alle 17.03 +0200, Sebastien Chassot ha
> scritto:

> > 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.

Si on ne veut tester qu'un partie du fichier, il ne faut pas chercher
"au début". Une différence peut se trouver n'importe où et c'est pour ça
que je proposais de chercher tout azimut plutôt que par le début. On
trouvera plus vite une différence même si on ne serait sûr qu'il n'y en
avait pas qu'à la toute fin.

> 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.

Oui, je disais ça pour résoudre de manière plus rapide et plus sûr le
problème posé. Prendre deux, trois somme partiel permet très rapidement
d'avoir une liste plus restrictive que basée sur la taille seulement.
Puisqu'au début on parlait de calculer un md5 par fichier pour générer
une liste.

A partir de cette liste je pense que faire une vérification approfondie
est important et puisqu'il y a controverse sur md5 n'utiliser que diff
me paraît aussi bien. D'autant plus que pour le hashage, il faut faire
plusieurs opérations sur chaque block du fichier ( "mixer" un bloc,
faire un OU avec le bloc précédent, stocker,...) et qu'en plus certain
ne semblent pas rassuré par la méthode. Une comparaison bit à bit est
sans doute plus rapide (j'en sais rien remarque) et plus sûr (il y a eu
une remarque intéressante de Yves Martin qui proposait d'optimiser en
comparant N fichiers "semblables" d'un coup plutôt que N*diff). Dans la
mesure ou il faut être capable de déceler comme tu le relève la moindre
différence, la question se résume à mon sens à : Quel est le moyen de le
faire le plus rapidement possible ? Quand on traque un bit la
probabilité de passer à côté dépend de la taille du fichier et est bien
plus grande qu'une collision md5. Je crois qu'on est d'accord,
"survoler" à un moment ou un autre toute la surface du fichier est le
seul moyen pour ne pas avoir de problème (le risque de confusion entre
deux fichiers est grand), le faire deux fois n'apporte rien et le faire
avec diff ou md5 offre la même sécurité (risque de collision
négligeable).


Au début du fil la question était :

On Wed, 2008-04-30 at 22:58 +0200, Félix Hauri wrote:
> Ma question:
> Si plutot que de comparer l'intégrité des fichiers lors de la deuxième passe,
> à partir de quel pourcentage de fichier comparé, je peux considérer que les
> deux fichiers sont identique, s'ils ont le même md5?
> 
Je dirais 0%, si deux fichiers ont le même md5, ils sont identique. 
Alors ne pas calculer les md5 en première phase (trop lourd) alors
qu'il va de toutes façons falloir faire une vérification approfondie
par la suite (incontournable).