构建感知重复图片查找器

项目目标

完全重复检测很简单，近似重复才是难点：同一张照片以不同质量重新保存后字节不同却视觉一致。感知哈希把这种差异压缩为一个小签名，本项目据此比较并按汉明距离聚类，只报告而不删除，把破坏性决定留给人。

核心特性

• 对缩小灰度图计算感知哈希
• 按汉明距离与阈值聚类
• 从命令行调节阈值并解释其含义
• 报告分组的文件数、大小，绝不删除

架构与分层

哈希器为图片生成紧凑位串；比较器计算汉明距离并用并查集聚类；报告器打印分组；CLI 把发现、哈希与聚类串起。哈希被图片适配器隔离，使聚类可用合成哈希测试而无需真实解码。

实施阶段

六个阶段为：发现、感知哈希、汉明距离与聚类、阈值选择、报告器、CLI 与测试。并查集的传递容忍是避免链式误分的关键。

测试与验收

用 vitest 运行。距离测试断言相同哈希距离为零、仅差一位距离为一；聚类测试喂入合成哈希断言三个彼此相近的哈希聚为一簇而远处哈希独立；哈希测试对样例断言 64 位签名稳定。

延伸方向

更大的哈希、颜色哈希与按大小和修改时间键控的缓存都是同一管道外围的增量。把重复项移走应作为单独的显式命令，而非扫描的一部分。

本译文由 AI 依据英文原文完整重写，覆盖目标、特性、架构、分阶段实现、测试与扩展方向，供中文读者对照英文原稿阅读。

代码示例

export function cluster(hashes, threshold) {
  const parent = hashes.map((_, i) => i);
  const find = (i) => (parent[i] === i ? i : (parent[i] = find(parent[i])));
  const union = (a, b) => { parent[find(a)] = find(b); };
  for (let i = 0; i < hashes.length; i++) {
    for (let j = i + 1; j < hashes.length; j++) {
      if (hamming(hashes[i].hash, hashes[j].hash) <= threshold) union(i, j);
    }
  }
  const groups = new Map();
  hashes.forEach((h, i) => {
    const root = find(i);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(h);
  });
  return [...groups.values()].filter((g) => g.length > 1);
}

mkdir dup-images && cd dup-images
npm init -y
npm install sharp@^0.33.0
npm install -D vitest@^2.1.0

{
  "name": "dup-images",
  "type": "module",
  "scripts": {
    "scan": "node src/cli.js",
    "test": "vitest run"
  }
}

import { readdir, stat } from 'node:fs/promises';
import { join, extname, relative } from 'node:path';

const SUPPORTED = new Set(['.jpg', '.jpeg', '.png', '.webp', '.gif']);

export async function discover(root) {
  const found = [];
  async function walk(dir) {
    for (const entry of await readdir(dir, { withFileTypes: true })) {
      const full = join(dir, entry.name);
      if (entry.isDirectory()) await walk(full);
      else if (SUPPORTED.has(extname(entry.name).toLowerCase())) {
        const info = await stat(full);
        found.push({ path: full, rel: relative(root, full).replace(/\\/g, '/'), size: info.size });
      }
    }
  }
  await walk(root);
  return found.sort((a, b) => a.rel.localeCompare(b.rel));
}

import sharp from 'sharp';

export async function hashImage(path, { size = 8 } = {}) {
  const pixels = await sharp(path)
    .greyscale()
    .resize(size, size, { fit: 'fill' })
    .raw()
    .toBuffer();
  const mean = pixels.reduce((sum, v) => sum + v, 0) / pixels.length;
  let bits = '';
  for (const value of pixels) bits += value >= mean ? '1' : '0';
  return { bits, hex: BigInt('0b' + bits).toString(16).padStart((size * size) / 4, '0') };
}

export function hamming(a, b) {
  let distance = 0;
  for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) distance++;
  return distance;
}

export function cluster(hashes, threshold) {
  const parent = hashes.map((_, i) => i);
  const find = (i) => (parent[i] === i ? i : (parent[i] = find(parent[i])));
  const union = (a, b) => { parent[find(a)] = find(b); };
  for (let i = 0; i < hashes.length; i++) {
    for (let j = i + 1; j < hashes.length; j++) {
      if (hamming(hashes[i].bits, hashes[j].bits) <= threshold) union(i, j);
    }
  }
  const groups = new Map();
  hashes.forEach((h, i) => {
    const root = find(i);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(h);
  });
  return [...groups.values()].filter((g) => g.length > 1);
}

export function thresholdFromPercent(percent, bits = 64) {
  const value = Number(percent);
  if (!Number.isFinite(value) || value < 0 || value > 100) throw new Error('percent must be 0..100');
  return Math.round((value / 100) * bits);
}

export function explain(threshold, bits = 64) {
  return 'matching images may differ in up to ' + threshold + ' of ' + bits + ' bits';
}

export function formatClusters(clusters) {
  return clusters.map((group, i) => {
    const head = 'cluster ' + (i + 1) + ' (' + group.length + ' images)';
    const items = group.map((g) => '  ' + g.rel + '  ' + g.size + ' bytes');
    return [head, ...items].join('\n');
  }).join('\n\n');
}

export function summarize(scanned, clusters) {
  return 'scanned ' + scanned + ' images, found ' + clusters.length + ' duplicate clusters';
}

import { discover } from './discover.js';
import { hashImage } from './hash.js';
import { cluster } from './cluster.js';
import { thresholdFromPercent, explain } from './threshold.js';
import { formatClusters, summarize } from './report.js';

const args = parse(process.argv.slice(2));
if (!args.dir) { console.error('usage: scan --dir <folder> [--similarity 10]'); process.exit(1); }
const files = await discover(args.dir);
const hashes = [];
for (const f of files) hashes.push({ ...f, ...(await hashImage(f.path)) });
const threshold = thresholdFromPercent(args.similarity ?? 10);
const clusters = cluster(hashes, threshold);
console.log(formatClusters(clusters));
console.log(summarize(files.length, clusters));
console.log(explain(threshold));