我想递归几个目录并在n个目录之间找到重复文件。C#,最快(最佳?)在目录阵列中识别重复文件的方法
我的这个想法是让全局哈希表或其他数据结构来保存每个我找到的文件;然后检查每个后续文件以确定它是否在“主”文件列表中。显然,我认为这不会很有效率,而且“有更好的办法!”一直在我的大脑中响起。
任何意见,以更好的方式来处理这种情况,将不胜感激。
我想递归几个目录并在n个目录之间找到重复文件。C#,最快(最佳?)在目录阵列中识别重复文件的方法
我的这个想法是让全局哈希表或其他数据结构来保存每个我找到的文件;然后检查每个后续文件以确定它是否在“主”文件列表中。显然,我认为这不会很有效率,而且“有更好的办法!”一直在我的大脑中响起。
任何意见,以更好的方式来处理这种情况,将不胜感激。
您的方法对我来说听起来很健全。除非您有很好的理由认为它不足以满足您的性能要求,否则我只需按此方式实施并在必要时进行优化。请记住,“过早优化是邪恶的根源”。
您可以通过首先比较文件大小来避免哈希。如果你从来没有找到相同大小的文件,你不必对它们进行哈希处理。一旦找到具有相同大小的另一个文件,只会散列一个文件,然后将它们都散列在一起。
这应该比盲目散列每个文件快得多,尽管实现这个双层检查会更复杂。
老实说,使用适当的封装和类设计,不会增加太多的复杂性,我想。 – tster 2010-05-11 23:22:40
对于需要多次重复的字节比较,您可能最好使用已在查看的方法。
如果你真的关心效率,并知道重复文件总是具有相同的文件名,那么你可以从单独比较文件名开始,只有在找到重复名称时才使用散列字节。这样你可以节省哈希文件在树中没有重复的时间。
我建议保留多个文件的内存中索引。
创建一个索引的所有文件通过文件长度:
Dictionary<int, List<FileInfo>> IndexBySize;
当你正在处理新的文件Fu
,这是一个快速查找发现,大小相同的所有其他文件。
创建另一个指标的修改时间的所有文件:
Dictionary<DateTime, List<FileInfo>> IndexByModification;
鉴于文件Fu
,你可以找到在同一时间修改的所有文件。
对每个重要的文件特征重复。然后,您可以使用扩展方法Intersect()
来有效比较多个标准。
例如:
var matchingFiles
= IndexBySize[fu.Size].Intersect(IndexByModification[fu.Modified]);
这将使您避免逐字节扫描,直到您需要。然后,文件已被散列,创建另一个指标:
Dictionary<MD5Hash, List<FileInfo>> IndexByHash;
你可能想在同一时间,以减少碰撞计算哈希值多。
谢谢。两个问题:(1)你在(2)其次,你说:“你可能想同时计算多个散列以减少冲突” - >我不遵循 - 你能详细说明一下吗? – BKSpurgeon 2016-02-13 11:28:31
是的,'IndexBySize'是第一个字典的名称 - 它允许您查找所有其他文件,您已经看到特定大小的文件。 'IndexByModification'是第二个字典的名称 - 允许您根据修改时间戳找到已经看到的文件。两者都是查找当前正在考虑的文件的潜在重复的捷径。 – Bevan 2016-02-15 01:28:49
快速计算哈希函数也可能有碰撞 - 两个文件* *不同* *做*具有相同的散列。有两种方法可以解决这个问题 - 使用像SHA-256这样的散列函数,这种散列函数不太可能给出错误匹配,或者使用多个不同(但独立的)快速散列函数。 – Bevan 2016-02-15 01:31:07
正如John Kugelman所说,最佳实践是首先比较两个尺寸相同的文件,如果它们具有不同的尺寸,则很明显它们不是重复的。
如果您发现两个文件的大小相同,为了获得更好的性能,可以比较两个文件的前500 KB,如果前500 KB相同,则可以比较其余字节。通过这种方式,您不必读取(例如)500 MB文件的所有字节以获得其散列值,因此您可以节省时间并提高性能
对我来说听起来相当有效。 – tster 2010-05-11 22:48:24
您要在多大程度上查找重复文件(名称,名称/大小,名称/大小/内容,内容而不考虑名称)?预计会有很多重复的文件,或者会是例外吗?通常会处理多少个文件? – Ragoczy 2010-05-11 22:52:20
我需要一个直接名称比较,而且很可能是逐字节比较(用户选择的方法清楚地表明字节比较会更慢)。另外,是的,会有成千上万的重复。 :( – Nate222 2010-05-11 23:01:15