0
$\begingroup$

I'm writing a duplicate file finder application, and I do not want to have to read every byte of every file to determine which files are duplicates.

Hard drive storage is segmented into clusters of X number of bytes. For example, on Windows, the average cluster size is 4096 Bytes (or 4K).

Therefore, my current algorithm first groups all the files by size. Then for each same-size-file-set, I calculate the total number of clusters, then randomly select 5 of these clusters and calculate a hash for each file in that set.

Q1: Five 4K bytes equals a sample size of 20,480. Assuming we can have very large files (i.e., the population size?), how confident can I be that all the files within this set, which have the same hash value are identical?

What I have tried:

Using 2 different online Sample Size calculators, I've calculated the following:

  • For a Confidence Level of 99.5%, Margin of Error of 1.15%, Population Proportion of 50%, and unlimited population size, I need 20,462 samples, which is very close to the 20,480 samples I'm taking.

  • The other site, CL: 99%, CI: 0.893, Population: 1 Million; states I need: 20,441 samples.

But these sites talk about taking surveys.

Q2: But do these numbers apply in my case?

Q3: If so, how should I read and apply them?

Q4: Or am I doing some wrong and if so what should I be doing instead?

Improve this question
$\endgroup$
3
  • $\begingroup$ Imagine there were three people sitting at a table with you to discuss this: a mathematical purist, an engineering pragmatist, and a tired old clown. The purist will say that you can prove they aren't the same by looking at a subset of the file, but you can only prove they are the same by looking at every bit. The pragmatist might say that if enough is similar then often all is the same. The clown is going to say that drive health requires checksums so many times the OS has done at least some of the work for you and has already touched every bit. $\endgroup$
    – EngrStudent
    Sep 20, 2022 at 13:13
  • $\begingroup$ @EngrStudent and this help me how? $\endgroup$
    – Kabua
    Sep 20, 2022 at 13:42
  • $\begingroup$ they are three valid, separate, answers. A mathematical purist will say you have to test every bit, or you cannot prove they are the same. There is a good-enough state where you can be 99% sure they are the same without sampling all the bits. There is also a good chance that the OS has already touched the files for you and created a checksum just having them on the disk, especially if there is striping or error-correcting-codes for storage, so there may be a programmatic way to access that checksum and not have to touch any of the bits to get confirmation of duplication. $\endgroup$
    – EngrStudent
    Sep 21, 2022 at 18:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.