Duplicates and similar images
Two analyses run on a scanned tree. Exact duplicates are a proof of equality (SHA-256, then a byte comparison
before removal). Similar images are a perceptual judgement and are never treated as equal. Sources:
DuplicateDetection/DuplicateFinder.swift, ImageSimilarity/SimilarImageFinder.swift.
Exact duplicates
Pipeline
flowchart TD
Tree[ScanTree regular files] --> Filter[drop empty, dataless, package contents, below minimum size]
Filter --> Links[names of an already counted inode are attached to it, not compared]
Links --> BySize[group by logical size, keep groups of 2 or more]
BySize --> Small{file larger than 48 KiB}
Small -->|no| Full
Small -->|yes| Sample[SHA-256 of three 16 KiB windows: head, middle, tail]
Sample --> Bucket[regroup by size and sample digest]
Bucket --> Full[streaming SHA-256 of the whole file]
Full --> Groups[groups of equal size and digest]
Groups --> Verify[byte-for-byte comparison in the deletion engine before any removal]
- Candidates by size.
tree.forEachFilecollects regular files of at leastminimumSizebytes (default 1; the application uses megabytes chosen by the user). Dataless files are skipped. Files inside packages are skipped unlessincludePackageContentsis set. A node flaggedhardLinkDuplicateis recorded under its file id as another name of the same inode and is not compared. - Sampled hash. For files larger than three sample windows,
sampleHashreads 16 KiB at the head, the middle and the tail withpreadand hashes them. This only splits size groups cheaply; it never decides. - Full hash.
fullHashstreams the file in 1 MiB chunks through CryptoKitSHA256. It opens withO_NOFOLLOW, requires a regular file, and returns nil if the size differs from the scanned size before or after reading, so a file that changed since the scan drops out. - Groups. Files with the same size and digest form a
DuplicateGroup, with members sorted by path and groups sorted by redundant content. - Verification at removal. A duplicate
CleanupItemcarriesverifyAgainst, the path of the copy that stays.DeletionEnginecallsidenticalContents(twopreadstreams andmemcmp) immediately before moving the item, and skips it if the copies differ, if the kept copy is gone, if the kept copy is also selected, or if both paths are the same inode.
Both hashing functions set F_NOCACHE on the descriptor so that hashing a large tree does not fill the unified
buffer cache.
Data structures
| Type | Content |
|---|---|
DuplicateFile |
node index, path, modification date, allocated size, private size, file id, mayShareBlocks, clone id, hardLinkPaths |
DuplicateGroup |
hexadecimal digest, logical size, files; redundantLogical, sharesStorage, recoverable(removing:) |
DuplicateResult |
groups, candidate count, bytes hashed, duration, unreadable paths, cancelled |
DuplicateProgress |
stage (grouping, sampling, hashing, done), files done and total, bytes hashed |
redundantLogical is logicalSize * (count - 1): content held by the extra copies, not space that would be
freed. sharesStorage is true when two members have the same non-zero clone id or any member may share
blocks; the interface then says that removing a copy frees little. recoverable(removing:) returns a range
per the rules in storage-accounting.md.
Concurrency
parallelMap starts up to workers dedicated threads at .utility quality of service. The default is half
the active processor count, clamped between 2 and 6. Workers pull indexes from a shared cursor and write
results into preallocated slots.
Measured on the sample folder: 685 MB hashed in 0.069 s with 6 threads. This is a warm-cache figure: the files had just been written and were in memory. A cold run is bound by the read speed of the disk, not by SHA-256.
Invariants
- Two files are in the same group only if their full SHA-256 digests and sizes are equal. The sampled hash
cannot create a group (test
collisionsInThePreliminaryFilterDoNotCreateFalseGroupsforces every sample to collide). - Hard links of one inode are one file, never a duplicate pair, and are not offered for removal.
- A cancelled run returns no groups.
- The engine never removes the last copy of a group: the kept copy must exist, differ in inode and be identical at removal time.
Failure handling
| Situation | Result |
|---|---|
| File cannot be opened or read | Dropped from its group; path listed in DuplicateResult.unreadable |
| File changed size since the scan | Full hash returns nil; file dropped |
| Sample read fails | File dropped before full hashing |
| Symlink in place of the file | Refused by O_NOFOLLOW |
| Cancel | Workers stop at the next file or chunk; empty result with cancelled == true |
Not handled
- Duplicate folders as units; only files are compared.
- Files inside packages by default (parts of an application or a photo library are not independent files).
- Dataless files: comparing them would download them.
- Automatic choice of the copy to keep in the application; the user chooses with "keep only". In a workflow the first path of each group, in path order, is kept.
- Link names are attached by file id alone, which is sufficient within one device.
Similar images
Method
A 64-bit difference hash is the prefilter and Vision feature prints confirm. Clusters are built around a representative image; similarity is not chained.
flowchart TD
Files[Image files by extension, 8 KiB or more, not dataless, not in packages] --> Thumb[ImageIO thumbnail, 448 px maximum, orientation applied]
Thumb --> Hash[9 by 8 grey bitmap, 64-bit difference hash]
Hash --> Pairs{Hamming distance of each pair}
Pairs -->|4 bits or fewer| Strong[accepted on structure]
Pairs -->|5 to 12 bits| Vision[Vision feature print distance]
Pairs -->|more than 12 bits, fast mode| Drop[not similar]
Pairs -->|more than 12 bits, thorough mode| Crop[Vision distance 0.25 or less]
Vision -->|0.36 or less| Accept[accepted]
Vision -->|more| Drop
Crop --> Accept
Strong --> Score[scored pairs, best first]
Accept --> Score
Score --> Cluster[join a cluster only if similar to its representative]
Cluster --> Groups[SimilarGroup with confidence]
- Fingerprint.
fingerprintcreates a thumbnail withCGImageSourceCreateThumbnailAtIndex, draws it into a 9 by 8 grey context and compares each pixel with its right neighbour, giving 64 bits. Pixel dimensions come from the image properties, swapped for rotated orientations. Fingerprints are computed in parallel. - Vision.
VNGenerateImageFeaturePrintRequestruns on the same thumbnail with.scaleFill; the distance is the Euclidean distance between the float vectors, computed withvDSP_distancesq. In fast mode the vector is computed lazily, only for images that appear in a pair needing it. In thorough mode it is computed for every image and every pair is judged, which also finds crops; thorough mode is limited to 3,000 images and falls back to fast above that (SimilarResult.modereports the mode actually used). - Clustering. Accepted pairs are sorted by score. The first pair founds a cluster with one image as representative. Another image joins only if it has an accepted score with that representative. "A is like B and B is like C" does not put A and C together.
- Confidence. The weakest link score in the cluster, clamped to 0 through 1. The structural score is
1 - bits / 32; the perceptual score is1 - distance / 0.72.
Supported extensions: jpg, jpeg, png, heic, heif, tiff, tif, gif, bmp, webp. Measured in fast mode on the sample folder: 31 images in 0.21 s, about 150 images per second.
Rules in the application
- Nothing is preselected.
AppModel.toggleSimilarrefuses to select the last remaining image of a group. - A selected image is a
review-risk item whose reason states that similar is not identical. - There is no byte verification for similar images: they are different files by definition.
Failure handling
- An image that cannot be decoded is counted in
SimilarResult.unreadableand ignored (testcorruptImagesAreCountedNotCrashed). - If Vision returns no vector for an image, pairs that need it are rejected.
- A cancelled run returns no groups.
Not handled
- RAW formats, videos, Live Photo pairs and bursts as such.
- Images inside photo libraries and other packages.
- Pair comparison is quadratic in the number of images; there is no index structure.
- Thresholds were chosen on generated test pictures and the sample folder, not on a labelled photo corpus.