时间戳

首页 > 解决方案 > 比较同一数组中的元素（图像文件）以查找附近重复项的算法

arrays - 比较同一数组中的元素（图像文件）以查找附近重复项的算法

问题描述

我正在研究一种算法的实现，给定表示在文件夹中找到的文件的定义明确的对象数组，应该比较它们以找到类似重复的克隆以进行删除。这个算法完成后，应该考虑任何类型的文件，但为了让事情更容易，让我们只讨论这个问题的图像。

这个问题的 TL;DR 是：在比较一个非常大的数组中的文件时，我可以实施什么类型的算法/规则来最小化我的 big(O) 表示法的复杂性。我不是在谈论比较本身（我使用的是 Levenshtein / Hamming 距离和基于被比较的 2 个文件的 Dice 系数的组合），而是细分一百万个文件数组并应用某种逻辑的实际决定后面的“加工”部分比较。

当我说这些对象是“定义明确的”时，我的意思是我已经有了可以通过快速扫描获得的信息基础。像absolutePath, createDate,size以字节为单位的东西，extension还有一个 MD5 哈希，它把所有东西都放在我可以用作标识符的东西上，因为即使是两个相同的文件也至少有不同的日期，所以哈希就足够了。在图像的情况下，我也得到了pHash比较。所有这些都出现在实际算法之前，因此还没有影响性能。

当我有一个包含所有这些对象的非常大的数组（想想arr.length > 1000000）时，问题就开始了，突然之间，白痴证明 O(n log n) 两个 for 循环不再剪切了：

for (var i = 0; i < arr.length; i++) {
    var fileBeingCompared = arr[i];
    for (var j = 0; j < arr.length; j++) {
        var fileToCompare = arr[j];

        if (methodThatComparesFiles(fileBeingCompared, fileToCompare)) { // files are similar
            // do stuff
        }
    }
}

在相当不错的 PC 上，在相对较小的小于 10000 张图像的测试文件夹上，这实际上花费了 4 多小时。显然，我开始进行一些改进，以尽量减少超过 10000^2 Levenshtein 比较的开销。

没有特别的顺序，这就是我所做的：

var arrayX = []; // contains 1000 or so files
var arrayY = []; // starts empty but is filled with the already-compared elements

while (arrayX.length) {
    var fileBeingCompared = arrayX.pop();

    for (var i = 0; i < arrayY.length; i++) {
        var fileToCompare = arrayY[j];

        if (methodThatComparesFiles(fileBeingCompared, fileToCompare)) { // files are similar
            // do stuff
        }
    }

    arrayY.push(fileBeingCompared);
}

但即便如此，这些改进虽然很明显，但还远远不够好。不仅如此，特定的实现本身也存在缺陷。假设我有 2 个视频，一个 480P，另一个 1080p：每个属性都会有所不同；大小、名称（可能）、日期等。由于我目前按大小排序，它们最终会出现在不同的线程中，而不是直接比较，留下重复。

如果有人可以提出某种可以帮助我获得性能的适用算法或建议，我正在使用带有 NodeJs 的 JS ES6，所以如果有任何推荐的库，请记住这一点。感谢读到最后的人。

标签： arraysalgorithmperformancecomparison

解决方案

如果您的相似性计算没有什么结构，那么您将不得不测试每一对。如果它（或它的某种变换）至少服从三角不等式，您可以尝试构建某种结构来回答精确或近似的最近邻搜索，并为每个点找到它的最近邻。一个只需要计算距离的最近邻数据结构是https://en.wikipedia.org/wiki/Cover_tree，但除非您的点主要位于低维子空间附近，否则您可能会看到很少的加速。

推荐阅读