2

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

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

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

4

7 回答 7

9

如果你真的需要保证 100% 的文件是 100% 相同的，那么你需要做一个字节到字节的比较。这只是问题的一部分——唯一具有 0% 错误匹配风险的散列方法是恒等函数！

我们剩下的是捷径，可以快速给我们快速的答案，让我们在某些时候跳过逐字节的比较。

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

因此，我们在寻找不匹配方面是走捷径。不会增加我们的通行证，但会使我们的失败更快：

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

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

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

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

编辑：

它还取决于您对文件所做的工作。您说您需要 100% 的确定性，所以这一点不适用于您，但是对于更普遍的问题，如果误报的成本是浪费资源、时间或内存而不是实际失败，则值得添加，然后通过模糊的捷径减少它可能是一个净赢，值得分析看看是否是这种情况。

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

于 2012-08-24T21:34:52.860 回答
2

串行比较

测试文件大小：118 MB
持续时间：579 ms
是否相等？真的

    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 ms
是否相等？真的

    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 并行比较字节段以确定两个文件是否相等。

于 2012-08-24T22:06:03.950 回答
1

最终，哈希无论如何都会逐字节读取文件......因此，如果您正在寻找准确的比较，那么您不妨进行比较。您能否提供更多有关您要完成的工作的背景信息？“大”文件有多大？您需要多久比较一次它们？

于 2012-08-24T21:20:51.040 回答
1

如果您想要完美的比较，则无法避免进行逐字节比较（仍然必须逐字节读取文件才能进行任何散列），因此问题在于您如何读取和比较数据。

因此，您需要解决两件事：

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

目的是确保您可以像硬盘读取数据一样快地进行比较，并且您始终可以毫无延迟地读取数据。如果您所做的一切都尽可能快地从驱动器中读取数据，那么这就是尽可能快的速度，因为硬盘读取速度成为瓶颈。

于 2012-08-24T21:15:03.140 回答
1

如果您有大量文件并且您正在尝试识别重复文件，我会尝试按费用顺序分解工作。我可能会尝试以下方法：

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

2) 在每个大小组内生成文件前 n 个字节的哈希值。确定一个可能会发现差异的合理 n。许多文件具有相同的标头，因此您不必确保 n 大于该标头长度。按哈希分组，如果每个组包含 1 个文件，则完成（该组内没有重复），否则继续执行步骤 3。

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

于 2012-08-24T21:31:03.670 回答
1

为什么不兼得？

与第一遍的哈希值进行比较，然后返回冲突并执行逐字节比较。这允许在保证 100% 匹配置信度的情况下实现最大速度。

于 2012-08-24T21:13:25.450 回答
0

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

如何同时打开两个文件，然后逐块比较它们？

伪代码：

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

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

于 2012-08-24T21:30:00.123 回答