0
$\begingroup$

Let $d_j \in \mathbb{Z}_{\ge 0} =$ jth duplicate unearthed by a freeware de-duplicator (like AllDup1).
$t_j >0 =$ time taken to unearth the jth duplicate.
$f \in \mathbb{N} =$ total number of files being searched.
$f_j =$ number of files already searched by de-duplicator at $t_j$. Plainly, $\uplus_j \; f_j = f$.

My questions

  1. At some $t_j$ for some j, isn't it faster if you stop the search in AllDup, delete all $f_1, \dots, f_j$, then restart the search on AllDup?

Then you save electricity and time! Why? AllDup doesn't need to pair up all the $d_j$ with the other files. In other words, you spare AllDup from analyzing $d_j \times (f - f_j)$?

  1. As a corollary, can it be swifter to de-duplicate each subset of $f$ separately first? Rather than de-duplicating the whole of $f$?

  2. As a corollary, can it be quicker to search for all duplicate pictures, then duplicate video files, duplicate audio files — before searching for all duplicate files regardless of file type?

1 NON-AFFILIATION DISCLAIMER — I have no affiliation or financial, commercial or ownership interest.

$\endgroup$
4
  • $\begingroup$ I don't know what you mean by "stop the search in AllDup, delete all $t_1, \dots, t_j$, then restart the search on AllDup"; you'll probably have to explain more clearly. Also, something seems wrong with that statement; the $t_j$'s are times, so I don't know why we'd save them or delete them or how that would affect anything or be relevant. You might have to tell us how the algorithm AllDup works too. Please ask only one question per post. $\endgroup$
    – D.W.
    Feb 6, 2022 at 21:03
  • $\begingroup$ @D.W. Thanks. I fixed that typo. I'll try improving my post in the morning. $\endgroup$
    – user132114
    Feb 6, 2022 at 21:21
  • $\begingroup$ Lets say you have files $a,b,c$ do I understand correctly that if your deduplicator finds that $a = b$ and it checks $c$ that it shouldn't check $a = b$ and $b = c$ because it already knows that $a = b$? So if you remove $a$ you save time? Is this what you are asking? $\endgroup$
    – plshelp
    Feb 7, 2022 at 1:16
  • $\begingroup$ @plshelp Yes. I think you understand me! $\endgroup$
    – user132114
    Feb 7, 2022 at 7:32

1 Answer 1

2
$\begingroup$

I think you're imagining that deduplicators compare every file to every previously scanned file. That would be too slow to be usable. They actually maintain a cache of known properties of already-scanned files, and use it to decide which comparisons are needed.

For example, they might do something like this:

  • Scan all files and assign them to bins by size. Discard bins that contain only one file at the end of the scan.

  • Group the files of each remaining bin into sub-bins based on a checksum of the first 4K of the file, then discard sub-bins that have only one file.

  • Group into sub-sub-bins based on a checksum of the rest of the file (if any), then discard sub-sub-bins that have only one file.

  • Group into sub-sub-sub-bins based on the actual file contents. Any groups with more than one file are duplicates.

In the last step, if there are $n$ files $d_1,\ldots,d_n$ in the ss-bin, and all are duplicates, then first $d_1$ will be placed in a sss-bin by itself, then $d_2$ will be compared to it and added to the same bin, then $d_3$ will be compared with some representative of the bin, i.e., with $d_1$ or $d_2$, etc. In total only $n-1$ pairwise comparisons happen. If the files are all different then $n(n{-}1)/2$ comparisons are needed, but that case happens very rarely if the checksum is any good.

The last step may not even be necessary if the checksum is good enough. The chance of two different files having the same BLAKE2b-256 checksum is so small that it's senseless to worry about it (a false positive is much more likely to be due to a cosmic ray), and storing 256-bit checksums of 1 million files takes only 32 MB.

$\endgroup$

Your Answer

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