SPB Git

Repository Public License

duplicates.md 8.7 KB 159 lines markdown

1<!-- ORIX Clean / File: docs/architecture/duplicates.md / Author: Simon-Pierre Boucher / Contact: contact@spboucher.ai -->2# Duplicates and similar images34Two analyses run on a scanned tree. Exact duplicates are a proof of equality (SHA-256, then a byte comparison5before removal). Similar images are a perceptual judgement and are never treated as equal. Sources:6`DuplicateDetection/DuplicateFinder.swift`, `ImageSimilarity/SimilarImageFinder.swift`.78## Exact duplicates910### Pipeline1112```mermaid13flowchart TD14    Tree[ScanTree regular files] --> Filter[drop empty, dataless, package contents, below minimum size]15    Filter --> Links[names of an already counted inode are attached to it, not compared]16    Links --> BySize[group by logical size, keep groups of 2 or more]17    BySize --> Small{file larger than 48 KiB}18    Small -->|no| Full19    Small -->|yes| Sample[SHA-256 of three 16 KiB windows: head, middle, tail]20    Sample --> Bucket[regroup by size and sample digest]21    Bucket --> Full[streaming SHA-256 of the whole file]22    Full --> Groups[groups of equal size and digest]23    Groups --> Verify[byte-for-byte comparison in the deletion engine before any removal]24```25261. **Candidates by size.** `tree.forEachFile` collects regular files of at least `minimumSize` bytes (default 1;27   the application uses megabytes chosen by the user). Dataless files are skipped. Files inside packages are28   skipped unless `includePackageContents` is set. A node flagged `hardLinkDuplicate` is recorded under its29   file id as another name of the same inode and is not compared.302. **Sampled hash.** For files larger than three sample windows, `sampleHash` reads 16 KiB at the head, the31   middle and the tail with `pread` and hashes them. This only splits size groups cheaply; it never decides.323. **Full hash.** `fullHash` streams the file in 1 MiB chunks through CryptoKit `SHA256`. It opens with33   `O_NOFOLLOW`, requires a regular file, and returns nil if the size differs from the scanned size before or34   after reading, so a file that changed since the scan drops out.354. **Groups.** Files with the same size and digest form a `DuplicateGroup`, with members sorted by path and36   groups sorted by redundant content.375. **Verification at removal.** A duplicate `CleanupItem` carries `verifyAgainst`, the path of the copy that38   stays. `DeletionEngine` calls `identicalContents` (two `pread` streams and `memcmp`) immediately before39   moving the item, and skips it if the copies differ, if the kept copy is gone, if the kept copy is also40   selected, or if both paths are the same inode.4142Both hashing functions set `F_NOCACHE` on the descriptor so that hashing a large tree does not fill the unified43buffer cache.4445### Data structures4647| Type | Content |48|---|---|49| `DuplicateFile` | node index, path, modification date, allocated size, private size, file id, `mayShareBlocks`, clone id, `hardLinkPaths` |50| `DuplicateGroup` | hexadecimal digest, logical size, files; `redundantLogical`, `sharesStorage`, `recoverable(removing:)` |51| `DuplicateResult` | groups, candidate count, bytes hashed, duration, unreadable paths, cancelled |52| `DuplicateProgress` | stage (`grouping`, `sampling`, `hashing`, `done`), files done and total, bytes hashed |5354`redundantLogical` is `logicalSize * (count - 1)`: content held by the extra copies, not space that would be55freed. `sharesStorage` is true when two members have the same non-zero clone id or any member may share56blocks; the interface then says that removing a copy frees little. `recoverable(removing:)` returns a range57per the rules in `storage-accounting.md`.5859### Concurrency6061`parallelMap` starts up to `workers` dedicated threads at `.utility` quality of service. The default is half62the active processor count, clamped between 2 and 6. Workers pull indexes from a shared cursor and write63results into preallocated slots.6465Measured on the sample folder: 685 MB hashed in 0.069 s with 6 threads. This is a **warm-cache** figure: the66files had just been written and were in memory. A cold run is bound by the read speed of the disk, not by67SHA-256.6869### Invariants7071- Two files are in the same group only if their full SHA-256 digests and sizes are equal. The sampled hash72  cannot create a group (test `collisionsInThePreliminaryFilterDoNotCreateFalseGroups` forces every sample to73  collide).74- Hard links of one inode are one file, never a duplicate pair, and are not offered for removal.75- A cancelled run returns no groups.76- The engine never removes the last copy of a group: the kept copy must exist, differ in inode and be77  identical at removal time.7879### Failure handling8081| Situation | Result |82|---|---|83| File cannot be opened or read | Dropped from its group; path listed in `DuplicateResult.unreadable` |84| File changed size since the scan | Full hash returns nil; file dropped |85| Sample read fails | File dropped before full hashing |86| Symlink in place of the file | Refused by `O_NOFOLLOW` |87| Cancel | Workers stop at the next file or chunk; empty result with `cancelled == true` |8889### Not handled9091- Duplicate folders as units; only files are compared.92- Files inside packages by default (parts of an application or a photo library are not independent files).93- Dataless files: comparing them would download them.94- Automatic choice of the copy to keep in the application; the user chooses with "keep only". In a workflow95  the first path of each group, in path order, is kept.96- Link names are attached by file id alone, which is sufficient within one device.9798## Similar images99100### Method101102A 64-bit difference hash is the prefilter and Vision feature prints confirm. Clusters are built around a103representative image; similarity is not chained.104105```mermaid106flowchart TD107    Files[Image files by extension, 8 KiB or more, not dataless, not in packages] --> Thumb[ImageIO thumbnail, 448 px maximum, orientation applied]108    Thumb --> Hash[9 by 8 grey bitmap, 64-bit difference hash]109    Hash --> Pairs{Hamming distance of each pair}110    Pairs -->|4 bits or fewer| Strong[accepted on structure]111    Pairs -->|5 to 12 bits| Vision[Vision feature print distance]112    Pairs -->|more than 12 bits, fast mode| Drop[not similar]113    Pairs -->|more than 12 bits, thorough mode| Crop[Vision distance 0.25 or less]114    Vision -->|0.36 or less| Accept[accepted]115    Vision -->|more| Drop116    Crop --> Accept117    Strong --> Score[scored pairs, best first]118    Accept --> Score119    Score --> Cluster[join a cluster only if similar to its representative]120    Cluster --> Groups[SimilarGroup with confidence]121```122123- **Fingerprint.** `fingerprint` creates a thumbnail with `CGImageSourceCreateThumbnailAtIndex`, draws it into124  a 9 by 8 grey context and compares each pixel with its right neighbour, giving 64 bits. Pixel dimensions come125  from the image properties, swapped for rotated orientations. Fingerprints are computed in parallel.126- **Vision.** `VNGenerateImageFeaturePrintRequest` runs on the same thumbnail with `.scaleFill`; the distance127  is the Euclidean distance between the float vectors, computed with `vDSP_distancesq`. In fast mode the128  vector is computed lazily, only for images that appear in a pair needing it. In thorough mode it is computed129  for every image and every pair is judged, which also finds crops; thorough mode is limited to 3,000 images130  and falls back to fast above that (`SimilarResult.mode` reports the mode actually used).131- **Clustering.** Accepted pairs are sorted by score. The first pair founds a cluster with one image as132  representative. Another image joins only if it has an accepted score with that representative. "A is like133  B and B is like C" does not put A and C together.134- **Confidence.** The weakest link score in the cluster, clamped to 0 through 1. The structural score is135  `1 - bits / 32`; the perceptual score is `1 - distance / 0.72`.136137Supported extensions: jpg, jpeg, png, heic, heif, tiff, tif, gif, bmp, webp. Measured in fast mode on the138sample folder: 31 images in 0.21 s, about 150 images per second.139140### Rules in the application141142- Nothing is preselected. `AppModel.toggleSimilar` refuses to select the last remaining image of a group.143- A selected image is a `review`-risk item whose reason states that similar is not identical.144- There is no byte verification for similar images: they are different files by definition.145146### Failure handling147148- An image that cannot be decoded is counted in `SimilarResult.unreadable` and ignored (test149  `corruptImagesAreCountedNotCrashed`).150- If Vision returns no vector for an image, pairs that need it are rejected.151- A cancelled run returns no groups.152153### Not handled154155- RAW formats, videos, Live Photo pairs and bursts as such.156- Images inside photo libraries and other packages.157- Pair comparison is quadratic in the number of images; there is no index structure.158- Thresholds were chosen on generated test pictures and the sample folder, not on a labelled photo corpus.159
Files main
Menu

Theme