在C++中查找重复文件的最佳方法是什么？

Question

我想在C++中找到文件系统上的重复文件.有没有算法尽快做到这一点？我是否需要创建一个多线程应用程序,或者我可以使用一个线程来完成它？

Answer 1

我同意Kerrek SB的说法,有比C++更好的工具,但是,假设你真的需要在C++中这样做,这里有一些建议和要在你的实现中考虑的事情:

1. 使用boost :: filesystem进行可移植文件系统遍历

2. 每个文件建议的散列是非常合理的,但是首先制作文件大小为关键的多重映射可能更有效.然后仅在存在重复大小的文件时应用哈希.

3. 决定如何处理空文件和符号链接/捷径

4. 决定你想如何处理特殊文件,例如在unix上你有目录fifos,套接字等

5. 说明在算法运行时文件或目录结构可能会发生变化,消失或移动的事实

6. 考虑到某些文件或目录可能无法访问或损坏的事实(例如,递归目录链接)

7. 使线程数可配置为有意义的并行化数量取决于底层磁盘硬件和配置.如果你是一个简单的硬盘驱动器而不是昂贵的san,那将会有所不同.但是,不要做出假设; 测试一下.例如,Linux非常适合缓存文件,因此很多读取都来自内存,因此不会阻塞i/o.

Answer 2

1)不要使用C++.您需要的所有工具已经存在.

2)散列每个文件(例如with md5sum)并构建文件名,文件大小和散列值的索引.*

3)按哈希值排序并查找重复的哈希值和大小对(例如with sort).

4)diff对候选人做一个普通的重复.

您可以通过一些工作来并行化步骤2),但是您将受到存储的I/O速度的限制.您可以通过将大型索引文件拆分为位,对它们进行单独排序然后合并它们来并行化步骤3)(sort -m).

*)正如@frankc所说,实际上并不散列每个文件,而只是那些大小不是唯一的文件.从基于大小的索引开始.你需要散列很多小文件,但只有很少的大文件.

Answer 3

我会这样做：

• 扫描您感兴趣的目录，查看每个文件的大小；将文件大小/路径对存储在 a 中multimap，文件大小作为索引；
• 然后，扫描multimap每个键只有一个元素的桶，即大小唯一的文件；那些肯定不能重复。
• 对剩余文件的内容进行散列，并执行与之前相同的操作（multimap以散列作为键和路径作为值）。
• 然后仅对具有相同散列的文件执行实际（每字节字节）比较。

这个过程应该比盲目地散列所有文件要快得多，因为大多数文件都有不同的大小，并且可以通过查看来区分；并且检查文件大小比散列文件便宜得多，因为它只是一个文件系统属性查找，而不是读取文件的整个内容。

需要最后一步，因为不同文件可能具有相同的哈希值；但是有了良好的散列函数，大部分工作已经完成，因为不相关文件的散列冲突应该很少见。

请注意，您的哈希函数不需要加密安全，也不需要特别快（我认为这个过程的时间将由 IO 主导）。

此外，由于您实际上并不需要一个排序的容器，而不是multimap您可以使用 an unordered_multimap，因为它应该具有更快的查找时间，并且一旦您知道必须处理多少个文件，您就可以reserve使用确定的元素的最大数量，避免重新分配。