比较大文件的内容

Question

我需要比较非常大的文件的内容。程序的速度很重要。我需要100%匹配。我读了很多信息，但没有找到最佳的解决方案。我正在考虑两个选择，两个问题都有。

1. 逐字节比较整个文件-对于大文件速度不够快
2. 使用哈希的文件比较-不是100%匹配具有相同哈希的两个文件

你有什么建议？也许我可以利用线程？MemoryMappedFile有帮助吗？

Answer 1

如果您确实需要100%保证文件100%相同，那么您需要进行逐字节比较。这只是问题的一部分——唯一有0%错误匹配风险的哈希方法是身份函数！

我们剩下的是一些快捷方式，可以快速给我们提供答案，让我们在某些时间跳过逐字节比较。

通常，证明平等的唯一捷径就是证明身份。在OO代码中，它将显示两个对象，而实际上是同一个对象。文件中最接近的是绑定或NTFS连接是否意味着两个路径指向同一个文件。这种情况很少发生，除非工作的性质使其比正常情况更为常见，否则这不会是一个净收益。

因此，我们只能在寻找不匹配的地方走捷径。没有增加我们的传球次数，但让我们的失败更快：

1. 大小不同，不是一个字节对一个字节相等。简单
2. 如果您要多次检查同一个文件，则对其进行散列并记录散列。不同的散列，保证不相等。需要一对一比较的文件数量大幅减少
3. 许多文件格式可能有一些共同之处。特别是许多格式的第一个字节往往是"幻数"、标题等。要么跳过它们，要么跳过然后检查最后一个（如果它们有可能不同，但很低）

然后是尽快进行实际比较的问题。将一次4个八位字节的批加载到整数中并进行整数比较通常比每八位字节加载八位字节快。

线程化会有所帮助。一种方法是将文件的实际比较拆分为多个操作，但如果可能的话，在不同的线程中进行完全不同的比较会获得更大的收益。我需要更多地了解您正在做什么，以提供更多建议，但最重要的是确保测试的输出是线程安全的。

如果您确实有多个线程在检查相同的文件，请让它们彼此远离。例如，如果您有四个线程，您可以将文件拆分为四个，或者您可以让一个线程占用字节0、4、8，而另一个线程则占用字节1、5、9等（或4位字节组0、4和8等）。后者比前者更有可能出现虚假共享问题，所以不要这样做。

编辑：

这也取决于你对这些文件做了什么。你说你需要100%的确定性，所以这一点不适用于你，但值得补充的是，更普遍的问题是，如果假阳性的成本是浪费资源、时间或内存，而不是实际的失败，那么通过模糊的捷径来减少它可能是一个净胜利，值得分析一下情况是否如此。

如果你使用哈希来加快速度（它至少可以更快地找到一些明确的错误匹配），那么Bob Jenkins的Spooky hash是一个不错的选择；它在加密方面并不安全，但如果这不是你的目的，它会非常快地创建128位哈希（比加密哈希快得多，甚至比许多GetHashCode()实现所采用的方法快得多），非常善于避免意外冲突（加密哈希避免的那种故意冲突是另一回事）。我为.Net实现了它，并将其放在nuget上，因为当我发现自己想使用它时，其他人都没有。

Answer 2

串行比较

测试文件大小：118 MB
持续时间：579毫秒
相同的真实

    static bool Compare(string filePath1, string filePath2)
    {
        using (FileStream file = File.OpenRead(filePath1))
        {
            using (FileStream file2 = File.OpenRead(filePath2))
            {
                if (file.Length != file2.Length)
                {
                    return false;
                }
                int count;
                const int size = 0x1000000;
                var buffer = new byte[size];
                var buffer2 = new byte[size];
                while ((count = file.Read(buffer, 0, buffer.Length)) > 0)
                {
                    file2.Read(buffer2, 0, buffer2.Length);
                    for (int i = 0; i < count; i++)
                    {
                        if (buffer[i] != buffer2[i])
                        {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

并行比较

测试文件大小：118 MB
持续时间：340毫秒
相同的真实

    static bool Compare2(string filePath1, string filePath2)
    {
        bool success = true;
        var info = new FileInfo(filePath1);
        var info2 = new FileInfo(filePath2);
        if (info.Length != info2.Length)
        {
            return false;
        }
        long fileLength = info.Length;
        const int size = 0x1000000;
        Parallel.For(0, fileLength / size, x =>
        {
            var start = (int)x * size;
            if (start >= fileLength)
            {
                return;
            }
            using (FileStream file = File.OpenRead(filePath1))
            {
                using (FileStream file2 = File.OpenRead(filePath2))
                {
                    var buffer = new byte[size];
                    var buffer2 = new byte[size];
                    file.Position = start;
                    file2.Position = start;
                    int count = file.Read(buffer, 0, size);
                    file2.Read(buffer2, 0, size);
                    for (int i = 0; i < count; i++)
                    {
                        if (buffer[i] != buffer2[i])
                        {
                            success = false;
                            return;
                        }
                    }
                }
            }
        });
        return success;
    }

MD5比较

测试文件大小：118 MB
持续时间：702毫秒
相同的真实

    static bool Compare3(string filePath1, string filePath2)
    {
        byte[] hash1 = GenerateHash(filePath1);
        byte[] hash2 = GenerateHash(filePath2);
        if (hash1.Length != hash2.Length)
        {
            return false;
        }
        for (int i = 0; i < hash1.Length; i++)
        {
            if (hash1[i] != hash2[i])
            {
                return false;
            }
        }
        return true;
    }
    static byte[] GenerateHash(string filePath)
    {
        MD5 crypto = MD5.Create();
        using (FileStream stream = File.OpenRead(filePath))
        {
            return crypto.ComputeHash(stream);
        }
    }

---

tl；dr并行比较字节段，以确定两个文件是否相等。

Answer 3

为什么两者都不？

与第一次传递的散列进行比较，然后返回冲突并执行逐字节比较。这允许在保证100%比赛置信度的情况下实现最大速度。

Answer 4

如果你想要完美的比较，就无法避免进行逐字节的比较（文件仍然必须逐字节读取才能进行任何哈希），所以问题是如何读取和比较数据。

因此，有两件事你需要解决：

• 并发性-确保在检查数据的同时读取数据
• 缓冲区大小-每次读取文件1个字节会很慢，请确保将其读取到一个适当大小的缓冲区（对于非常大的文件，大约8MB应该可以很好地处理）

目标是确保您可以像硬盘读取数据一样快速地进行比较，并且您总是无延迟地读取数据。如果你做的每件事都以从驱动器读取数据的速度进行，那么这就是尽可能快的速度，因为硬盘读取速度成为了瓶颈。

Answer 5

最终，散列将逐字节读取文件。。。因此，如果你正在寻找一个准确的比较，那么你不妨进行比较。你能提供更多关于你正在努力实现的目标的背景信息吗？"大"文件有多大？你多久比较一次它们？

Answer 6

如果你有一大组文件，并且你试图识别重复的文件，我会尝试按费用顺序分解工作。我可能会尝试以下方法：

1） 按大小对文件进行分组。不同大小的文件显然不可能完全相同。这些信息检索起来非常便宜。如果每个组只包含一个文件，则完成，没有重复，否则继续执行步骤2。

2） 在每个大小组内生成文件的前n个字节的哈希。确定一个可能检测到差异的合理n。许多文件都有相同的头，所以你不需要确保n大于这个头的长度。按哈希分组，如果每组包含1个文件，则完成（该组中没有重复），否则继续执行步骤3。

3） 在这一点上，您可能需要做更昂贵的工作，比如生成整个文件的哈希，或者逐字节进行比较。根据文件的数量和文件内容的性质，您可能会尝试不同的方法。希望之前的分组能够缩小可能的重复，这样您实际上必须完全扫描的文件数量就会非常少。

Answer 7

要计算哈希，需要读取整个文件。

把这两个文件一起打开，然后逐块比较，怎么样？

伪代码：

open file A
open file B
while file A has more data
{
    if next chunk of A != next chunk of B return false
}
return true

这样，您就不会一起加载太多内容，如果之前发现不匹配，也不会读取整个文件。您应该设置一个改变区块大小的测试，以确定最佳性能的正确大小。