Discussion :

[cquilgars]

Bonjour,

Ma problématique est la suivante : ma future architecture logicielle doit collecter plusieurs milliers de fichiers par jour au fil de l'eau.
Je désire mettre en place une solution qui permettre de s'assurer qu'un fichier est collecté pour la 1ère fois (à la connaissance d'un historique de 7J).
Dans le cas d'une collecte répétée sur un fichier, mes contraintes sont les suivantes :

1. La conservation du nom du fichier n'est pas garantie
2. La structure du contenu n'est ni déterminée ni constante
3. Le contenu est évidemment identique !

J'ai pensé à exploiter le CRC (Contrôle de redondance cyclique) comme clé d'unicité. Ce CRC peut être obtenu sous UNIX ou LINUX par la commande suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cksum fichier

Je me suis documenté sur la sujet pour répondre à la question suivante : Est-ce que la probabilité d'obtenir un CRC identique sur deux fichiers différents est nulle ? Dans la cas contraire, est-elle infinitésimale ?

Je n'ai pas trouvé de réponse précise. Avez-vous un avis ?

Merci de vos réponses

Christophe

[khayyam90]

bien le bonjour,

un CRC est plus petit (en nombre de bits utilisés) que le fichier qu'il représente. Sauf dans le cas des fichiers d'à peine quelques octets. Le CRC est donc une application surjective de l'ensemble des fichiers dans l'ensemble des fichiers de 32 bits. (bien qu'on puisse aussi calculer un CRC plus grand).

Donc, cet argument seul permet de dire que plusieurs fichiers peuvent avoir le même CRC. Mais la probabilité est très faible.

Ce que tu cherches à obtenir est une empreinte d'un fichier, un hash. Le CRC est un moyen. Tu peux aussi prendre un hash md5 ou sha1.
Un hash md5 ou sha1 se fait sur plus de bits qu'un simple CRC, c'est donc logiquement encore plus unique.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

md5sum fichier

[cquilgars]

un CRC est plus petit (en nombre de bits utilisés) que le fichier qu'il représente. .../... Le CRC est donc une application surjective de l'ensemble des fichiers dans l'ensemble des fichiers de 32 bits.

Je te remercie pour cette remarque. Elle a le mérite de me faire garder les pieds sur terre : le fichier lui-même est la seule clé d'unicité absolue... (ou un CRC de sa taille !!)

Donc, cet argument seul permet de dire que plusieurs fichiers peuvent avoir le même CRC. Mais la probabilité est très faible.

As-tu une idée de cette probabilité ?

[khayyam90]

As-tu une idée de cette probabilité ?

mmm ... je dirais 2^32 / 2^taille du fichier en bits

[Matthieu Brucher]

La probabilité que plusieurs fichiers (2^32) aient le même CRC est de 1.
La probabilité que 2 fichiers aient le même CRC sous l'hypothèse que les code CRC sont répartis équitablement est de 1/2^32, à mon avis.

[cquilgars]

mmm ... je dirais 2^32 / 2^taille du fichier en bits

La probabilité que plusieurs fichiers aient le même CRC si les fichiers ont une taille supérieure à 32bits est de 1.

Actuellement, j'ai logge le CRC (obtenu par cksum) sur 30000 fichiers. Ils sont tous uniques. Les fichiers ont une taille moyenne de 2Mo (avec des pointes à 40Mo).

je ne suis pas sûr de vos propositions (auquel je n'étais pas foutu d'arriver !)
Dois-je jouer au loto ce soir ?!

[Matthieu Brucher]

Effectivement, j'ai raconté en partie n'importe quoi. Il faut au moins 2^32 fichiers pour être sûr d'avoir un doublon - logique, d'ailleurs -.
Avec 2 fichiers, la proba d'avoir un doublon est de 1/2^32
Pour 3 fichiers, la proba d'avoir au moins 1 doublon est de 1 - la proba de n'avoir aucun doublon, soit donc 1 - A(2^32, 3)/2^32 ! ou qqch du genre. le A(n,k), c'est un arrangement.

[khayyam90]

j'étais aussi à côté. la probabilité ne dépend pas de la taille du fichier, puisque pour chaque fichier, il y a potentiellement 2^32 CRC possibles.

2 fichiers parmi 30000, c(30000,2) ~= 450 millions.
2 CRC identiques, donc 2^32 * 2^32

proba = 450 millions / 2^64 ~= 2.4E-11

donc faudrait vraiment que t'aies pas de chance pour avoir 2 crc identiques

[cquilgars]

Merci à vous pour vos réponses...

J'ai bien fait de ne pas jouer au loto hier soir !!!

Christophe

[sovitec]

j'étais aussi à côté. la probabilité ne dépend pas de la taille du fichier, puisque pour chaque fichier, il y a potentiellement 2^32 CRC possibles.

2 fichiers parmi 30000, c(30000,2) ~= 450 millions.
2 CRC identiques, donc 2^32 * 2^32

proba = 450 millions / 2^64 ~= 2.4E-11

donc faudrait vraiment que t'aies pas de chance pour avoir 2 crc identiques

hmm, la probabilité que deux fichiers est le même crc n'est pas de 1/2^64 mais 1/2^32.

Ce problème est connu sous le nom de "paradoxe des anniversaires" (voir par exemple http://fr.wikipedia.org/wiki/Paradoxe_des_anniversaires ).

Du coup on s'apperçoit que la probabilité d'avoir une collision avec 30000 fichiers est proche de 0.2, ce qui est loin d'être négligeable.

[cquilgars]

Du coup on s'aperçoit que la probabilité d'avoir une collision avec 30000 fichiers est proche de 0.2, ce qui est loin d'être négligeable.

Actuellement, j'ai loggé le CRC (obtenu par cksum) sur des fichiers collectés sur les 7 derniers jours. Les fichiers ont une taille moyenne de 2Mo (avec des pointes à 40Mo).

J'ai fait plusieurs relevés la semaine dernière,hier avec précisement 29568 fichiers
A l'instant, j'ai réalisé la vérification sur 30958 fichiers.

Ils sont tous uniques !! avec 20% de (mal)chance de trouver un doublon

Est-ce le fait que la formule se base sur un tirage uniforme ?

La probabilité p(n) que, parmi n éléments de E, chaque élément étant tiré uniformement dans tout l'ensemble E, deux éléments au moins soient identiques vaut :

Comme la paradoxe de l'anniversaire... j'ai du mal à croire en ma chance

[sovitec]

Les fichiers ont une taille moyenne de 2Mo (avec des pointes à 40Mo).

La taille du fichier ne devrait avoir aucune influence sur la suite. Mais elle peut être utilisée en disant que deux fichiers sont différents si leur checksum est différent et leur taille est différente. J'ai déjà vu plusieurs programmes qui font comme cela.

A l'instant, j'ai réalisé la vérification sur 30958 fichiers.

Ils sont tous uniques !! avec 20% de (mal)chance de trouver un doublon

Est-ce le fait que la formule se base sur un tirage uniforme ?

Le checksum est construit pour essayer de donner une répartition uniforme, même à partir de fichiers proches. Mais de toute façon une répartition non uniforme ne ferait qu'augmenter la probabilité d'obtenir des doublons.

Mais il restait plus de 80% de chance de ne pas avoir de doublon, le test sur un seul tirage ne veut pas dire grand chose.

[cquilgars]

Bonjour à tous,

Tout d'abord merci de votre acharnement à me suivre dans mon périple !

Mais il restait plus de 80% de chance de ne pas avoir de doublon, le test sur un seul tirage ne veut pas dire grand chose.

Je voudrais être sûr de bien comprendre le sous-entendu, je reformule ta réponse :
Si je réalise 10 vérifications de doublon sur 10 logs de 30000 fichiers, il y aura en moyenne de 2 logs avec un doublon.
Ai-je bien compris ?

[sovitec]

Si je réalise 10 vérifications de doublon sur 10 logs de 30000 fichiers, il y aura en moyenne de 2 logs avec un doublon.
Ai-je bien compris ?

Oui

[cquilgars]

Je remonte cette discussion tel un Yorkshire déterrant son os au fond du jardin...

J'ai maintenant loggé un passif de 63000 CRC. Je n'ai toujours pas de doublon !!

J'ai poussé les tests en générant artificiellement un passif de 380 000 fichiers. A la lecture de l'article "Paradoxe des anniversaires", nous sommes dans une zone de probabilité très très proche de 100%.

Ci-dessous mon code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
#!/bin/ksh
I=0
while [ $I -lt 380000 ]
do
 echo "${I}AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" | cksum >> test.log
 I=`expr $I + 1`  
done
echo "Nombre de CRC : `wc -l test.log`"
echo "Nombre de CRC distincts : `cut -d" " -f1 test.log | sort -u | wc -l`

Résultat aucun doublon... C'est la paradis pour ma solution.

Mais vos critiques et mises en garde me semblent tellement raisonnables et raisonnées que je suis dans l'expectative.

Que devons-nous en penser ?

[Matthieu Brucher]

As-tu essayé avec un md5 par exemple s'il y avait une différence de comportement ?

[Jedai]

Tes fichiers sont trop "réguliers" pour en tirer une conclusion : ils sont très peu différents les uns des autres et suivent une sorte de progression. Il est alors très probable qu'un algorithme de hash leur trouve des clés différentes, puisque ça fait partie des propriétés très appréciées dans une formule de hash que pour deux fichiers très proches le résultat soit très différent.

--
Jedaï

[cquilgars]

Je viens de faire un test avec la commande "md5sum" sous Linux. Le résultat est identique sur 200 000 fichiers (ou équivalents).

Nous avons aussi réalisé un test en calculant les CRC (par "cksum") du logarithme des 100 000 1ers entiers.
Nous avons un doublon sur les résultats suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
echo "`log 58257`" | cksum
echo "`log 16645`" | cksum

où log est un binaire C écrit à la va-vite pour le besoin des tests...

Ouuff Les experts en probabilité sont maintenant rassurés.

Moralité, cette probabilité est fonction, d'une certaine manière, de la taille et du contenu des fichiers.

Merci encore à tous.
Le Yorkshire enterre son os tout au fond du jardin.

[Jean-Marc.Bourguet]

Je ne connais pas le contenu de tes fichiers reels, mais tes fichiers de tests sont loins d'etre uniformement distribues, ce qui doit expliquer sans problemes l'absence de doublons chez eux.

[cquilgars]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
echo "`log 58257`" | cksum
echo "`log 16645`" | cksum

où log est un binaire C écrit à la va-vite pour le besoin des tests...

Pour information, ci-dessous le code C du binaire log...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
#include <stdio.h>
#include <math.h>
int main(int argc, char * argv[])
{
  printf("%10.50f\n", log(atol(argv[1])));
}