Analyse probabiliste

Principe

Malgré les avantages et qualités évoqués précédemment, la recherche par blocs telles qu'elle a été décrite présente un inconvénient significatif : on examine l'ensemble du support de stockage. Autant une clé USB de 16Go sera traitée relativement rapidement, autant un disque de 2To demandera beaucoup plus de temps.

Si l'on garde présent à l'esprit que l'identification d'un seul bloc discriminant sur le support prouve le transit du fichier associé à ce bloc, la notion d'une recherche par échantillonnage prend tout son sens. Cependant, dès lors que l'on n'examine pas l'intégralité du support de stockage, il faut bien calibrer l'échantillonnage du disque, au risque sinon d'un faux négatif (non détection alors que le fichier recherché a bel et bien été présent sur le support). Nous appellerons probabilité d'échec la probabilité de conclure, de façon erronée, que le fichier n'a pas transité sur le support examiné. La probabilité d'échec ne peut être annulée que par une analyse exhaustive du support.

Supposons que

• on prend un support de stockage de 1,5 Tio, soit 3 x 10⁹ blocs de stockage (512 octets chacun),
• le fichier recherché fait 100 Mio, soit 2 x 10⁵ blocs de stockage,
• l'échantillon contient un seul bloc.

Dans ce cas, la probabilité de succès (le bloc choisi au hasard est l'un des 2 x 10⁵ associés au fichier) est de (2 x 10⁵/3 x 10⁹), soit 6.66 x 10^-5. Autant dire que ce n'est pas très élevé. La probabilité d'échec est de (3 x 10⁹ - 2 x 10⁵)/3 x 10⁹, soit environ 99.993%.

D'une manière plus générale, si l'on prend un support composé de D blocs de stockage, un fichier recherché utilisant R blocs de stockage et un échantillonnage de n blocs sur le support, la probabilité d'échec (aucun des blocs du fichier n'est identifié) est égale à

Calculs de probabilités

Si l'on prend un support de 1To et un fichier recherché de 10 Mo, les probabilités de passer à côté du fichier alors qu'il est présent, en fonction de la taille de l'échantillon, sont les suivantes :

Taille échantillon	Proba échec
1	0.999990	99,999%
100	0.999000	99,900%
1000	0.990050	90,004%
10000	0.904837	90,484%
100000	0.367868	36,787%
200000	0.135320	13,532%
300000	0.049775	4,977%
400000	0.018308	1,831%
500000	0.006733	0,673%

La recherche d'un fichier de 10Mo sur un support de 1To peut être réalisée par la lecture de 500000 blocs seulement, avec une probabilité d'échec de 0,6%.

Toujours sur un support de 1To, avec un échantillonnage sur 10000 blocs, les probabilités d'échec en fonction de la taille du fichier recherché sont :

Taille fichier	Proba échec
10 Mo	0.904837	90,484%
50 Mo	0.606522	60,652%
100 Mo	0.367860	36,786%
150 Mo	0.223104	22,310%
200 Mo	0.135308	13,531%
250 Mo	0.082059	8,206%
300 Mo	0.049764	4,976%
400 Mo	0.018301	1,830%
500 Mo	0.006729	0,673%

Sur un support de 1To et avec un échantillon de 10000 blocs, il y a environ 8% de risque de passer à côté d'un fichier de 250 Mo, et moins de 0,7% de risque de rater un fichier de 500 Mo.

Mesures de performances

Mesures théoriques

Sur un disque de 2 To connecté en USB2, avec un débit soutenu de 40 Mio/s (soit la lecture 82000 blocs de stockage par seconde) et un fichier recherché de 100 Mo, on devrait obtenir les performances suivantes :

• la lecture de l'intégralité du disque dur prendra 794 minutes (13 heures 14 minutes et 43 secondes). La probabilité d'échec est nulle.
• la lecture d'un échantillon de 10000 blocs prendra moins d'une seconde. Probabilité d'échec : 60,65%.
• la lecture d'un échantillon de 50000 blocs prendra moins d'une seconde. Probabilité d'échec : 8,20%.
• la lecture d'un échantillon de 100000 blocs prendra une seconde et demie. Probabilité d'échec : 0,67%.

Mesures réelles

Nous avons procédé à des mesures réelles, avec un disque de 2 To connecté en USB2 et un fichier recherché de 100 Mio ayant été effacé :

• intégralité du disque lue en 963 minutes (probabilité d'échec nulle).
• échantillon de 1000 blocs lu en 13 secondes (probabilité d'échec de 95,12%).
• échantillon de 10000 blocs lu en 79 secondes (probabilité d'échec de 60,65%).
• échantillon de 100000 bolcs lu en 712 secondes (11 minutes 52 secondes), probabilité d'échec de 0,67%.

Les mesures montrent que les performances du support sont déterminantes pour la durée de la recherche. L'essentiel du temps d'attente est lié au temps de recherche d'un bloc sur le disque. La vitesse de transfert (USB2, USB3, Sata) n'a que peu d'impact.

Nous avons procédé à 100 recherches par échantillonnage, avec un échantillon de 100000 blocs. Sur ces 100 recherches, 72 ont renvoyé un résultat positif (fichier présent) et 28 un résultat négatif (fichier absent), soit un taux d'échec de 38,8%, proche du taux théorique.