如何用 Node.js 写一个重复照片查找程序

站长

2023年09月20日 10:47 · 阅读数 17

背景

手机里经常会有重复文件占用大量的存储空间，通常我会借助第三方软件来删除重复照片，但作为前端开发，是不是能用 JavaScript 来实现呢？本文将介绍如何使用 JavaScript 实现一个简单的重复照片查找程序。

像素比较

要判断两张照片是否相同，最简单的方法是比较照片的像素点的色值。如果两张照片完全相同，它们每个像素的色值应该是一样的。

function comparePhotos() {
  var ctx1 = canvas1.getContext('2d'); 
  var ctx2 = canvas2.getContext('2d');
  
  // 省略部分代码
  
  var imageData1 = ctx1.getImageData(0, 0, width, height); 
  var imageData2 = ctx2.getImageData(0, 0, width, height);

  for (var i = 0; i < imageData1.data.length; i += 4) {
    if (
      imageData1.data[i] !== imageData2.data[i] ||
      imageData1.data[i + 1] !== imageData2.data[i + 1] ||
      imageData1.data[i + 2] !== imageData2.data[i + 2] ||
      imageData1.data[i + 3] !== imageData2.data[i + 3]
    ) {
      return false
    }
  }

  return true
}

上面的代码通过创建 canvas 并调用 getImageData 方法来获取图片的像素数据，然后与每张照片进行比较。

这种方法理论上可行，但是 getImageData 方法需要遍历所有像素点，并将像素数据复制到内存中的 ImageData 对象中，再进行逐一比较。对于大尺寸的图片，可能会导致性能开销较大，在处理大量照片时可能会非常耗时。因此，我们需要一种更高效的方法，以减少处理时间和资源消耗。

哈希值比较

熟悉 HTTP 的小伙伴可能知道，在进行协商缓存时，服务端会通过 ETag 来验证资源是否有更新。这让我想到是不是可以借用相同的方法比较断两张照片呢？于是我查阅了一下 koa-etag 中间的件源码。

/**
 * Generate an entity tag.
 *
 * @param {Buffer|string} entity
 * @return {string}
 * @private
 */

function entitytag (entity) {
  if (entity.length === 0) {
    // fast-path empty
    return '"0-2jmj7l5rSw0yVb/vlWAYkK/YBwk"'
  }

  // compute hash of entity
  var hash = crypto
    .createHash('sha1')
    .update(entity, 'utf8')
    .digest('base64')
    .substring(0, 27)

  // compute length of entity
  var len = typeof entity === 'string'
    ? Buffer.byteLength(entity, 'utf8')
    : entity.length

  return '"' + len.toString(16) + '-' + hash + '"'
}

通过 etag 源码，可以看出其核心代码是使用 Node.js crypto 模块的 createHash 方法来生成资源的哈希值，当哈希值发生改变时，就代表资源有更新。

借鉴这个思路，我们使用哈希算法来得到照片的哈希值，可以快速比较两张照片是否相同，无需逐像素对所有照片进行比较。

const crypto = require('node:crypto')
const fs = require('node:fs')
const path = require('node:path')
const kolorist = require('kolorist')

// 判断文件是否为图片文件
function isImageFile(file) {
  const exts = ['.jpg', '.jpeg', '.png']
  const extname = path.extname(file).toLowerCase()
  return exts.includes(extname)
}

// 计算文件的哈希值
function calcHash(filePath) {
  const hash = crypto.createHash('sha1')
  const data = fs.readFileSync(filePath)

  hash.update(data)
  return hash.digest('hex')
}

// 查找重复照骗
function findDuplicateImages(folderPath) {
  const files = fs.readdirSync(folderPath)
  const duplicatesMap = new Map()

  for (const file of files) {
    const fullPath = path.join(folderPath, file)

    if (isImageFile(fullPath)) {
      const hash = calcHash(fullPath)

      if (duplicatesMap.has(hash)) {
        duplicatesMap.get(hash).push(file)
      } else {
        duplicatesMap.set(hash, [file])
      }
    }
  }

  const duplicates = [...duplicatesMap.values()].filter(files => files.length > 1)
  return duplicates
}

const folderPath = path.resolve(__dirname, './assets')
const duplicateImages = findDuplicateImages(folderPath)

console.log(kolorist.green(`一共发现 ${duplicateImages.length} 组重复照片`))
console.log(kolorist.blue(JSON.stringify(duplicateImages, null, 2)))

测试一下效果，很完美。

如何用 Node.js 写一个重复照片查找程序

对于大文件的处理，我们可以将大文件分割成固定大小的块，并逐块计算哈希值，最后将所有块的哈希值再继续计算得到最终的哈希值，而不是一次性读取整个文件。这样可以减少内存占用并加快哈希计算的速度。

在查阅资料时发现七牛云存储公开了一个计算文件 hash 值的算法 qetag 来解决上传‘消重’问题。算法大体如下：

如果你能够确认文件 <= 4M，那么 hash = UrlsafeBase64([0x16, sha1(FileContent)])。也就是，文件的内容的sha1值（20个字节），前面加一个byte（值为0x16），构成 21 字节的二进制数据，然后对这 21 字节的数据做 urlsafe 的 base64 编码。
如果文件 > 4M，则 hash = UrlsafeBase64([0x96, sha1([sha1(Block1), sha1(Block2), ...])])，其中 Block 是把文件内容切分为 4M 为单位的一个个块，也就是 BlockI = FileContent[I*4M:(I+1)*4M]。

这很符合我的需求，替换上面的 calcHash 方法后一个简单的查找程序就完成了。接下来继续了解一下最核心的哈希算法。

哈希(Hash)算法

哈希算法，又称为散列算法，是一种常用的密码学和数据结构算法。它将任意长度的输入数据，通过计算映射成固定长度的输出，这个输出被称为哈希值（也称散列值或摘要值）。

可以简单描述为：digest = Hash(data)

哈希算法具有以下特点：

输入敏感：输入数据只要有微小的变化，都会导致产生完全不同的摘要。
不可逆性：哈希算法是单向函数，即在知道输出的情况下，无法逆向推出输入数据。
正向快速：输入一段任意长度的数据，会快速输出一个固定长度的、取值难以预测的数据。
低碰撞率：对于不同的输入数据，产生相同摘要的概率应该极低。

Node.js 加密模块支持各种哈希函数，如：

MD5：输出128位摘要
SHA-1：输出160位摘要
SHA256 ：输出256位摘要
SHA512：输出512位摘要

这些算法具有不同的性能特征和安全级别，需要根据实际需求选择合适的哈希算法。通常情况下，哈希算法的输出长度越长，产生碰撞的概率就越低，从而更安全，但同时计算时间也会增加。

哈希算法在许多领域都有广泛应用，常用于检验数据的一致性、加密存储、数字签名和去重等。

总结

本文介绍了使用 Node.js 实现的重复照片查找程序，并学习了哈希算法和计算文件哈希值的方法。然而，该程序在实际应用中存在一些问题，如无法处理相似照片等。后续可以进行进一步优化。希望本文对你有帮助！

往期文章推荐：