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

[Daniel Cordey]

On Tuesday 06 May 2008, Sebastien Chassot wrote:

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

L'utilisation de md5* est interessante a partir du moment ou l'on va 
regulierement effcetuer cette operation de comparaison. En conservant les 
valeurs des md5, pour les fichiers non-modifies apres, on peut se contenter 
de ne recalculer les md5 que pour les fichiers dont le contenu a change. 
C'est valable seulement si le nombre de nouveau fichiers ou les chamgements 
ne sont pas tres nombreux. En fait, c'est une affaire de compromis.

Par contre, partant du principe qu'un md5 va de toute facon lire l'integralite 
de chaque fichier, en consacrant en plus du temps CPU au calcul, cela est 
forcement plus lent qu'une simple lecture... Donc, si le taux de changement 
est important, la comparaison byte/byte sera sans doute plus efficace. Dans 
ce cas, j'ecrirais un programme en C, charge de prendre N fichiers de taille 
identique, avec un algorithme de comparaison progressif. La seule restriction 
est que cela ne sera pas efficace si l'on a trop de fichiers de la meme 
taille (et cela depend aussi de la taille des fichiers). Un 
algorithme "progressif" permettra d'eliminer tres vite les fichiers qui 
different en arretant leur lecture des detection de difference. Il ne s'agit 
pas d'un "diff" mais d'un "Ndiff" un peu special. Et... dans ce cas, ecrire 
le code en C laissera sur place tout autre langage sans aucune discussion 
possible :-)

Je vais en discuter avec Felix tout-a-l'heure. SI jamais il part dans cette 
voei, comme le code n'est pas tres difficile a ecrire, je lui ferai cette 
fleure :-)

dc