如何比较大型文本文件？

Question

我有一个关于“技术”的问题想请教您的意见。

有两个文本文件（file_1和file_2）需要相互比较。这两个文件非常大（每个文件都有3-4GB，从3000万到4500万行）。我的想法是将尽可能多的file_1行读入内存中，然后将这些行与file_2中的所有行进行比较。如果匹配成功，则将匹配的文件行写入新文件。然后继续读取file_1的下1000行，并将其与file_2中的所有行进行比较，直到完全遍历file_1。

但是这听起来实际上非常耗时且复杂。

您能否想到任何其他比较这两个文件的方法？

您认为比较需要多长时间？对于我的程序，时间并不是那么重要。我没有处理过如此庞大的文件，因此我不知道这可能需要多长时间。它不应该超过一天。;-) 但我担心我的技术可能需要永远...

另一个刚刚浮现在我脑海中的问题是：你会读取多少行进入内存中？尽可能多吗？是否有一种方法可以在实际尝试之前确定可能的行数？我想读取尽可能多的行（因为我认为这样更快），但我经常内存不足。

谢谢您提前的帮助。

编辑：我认为我需要更详细地解释我的问题。

目的不是查看两个文件是否完全相同（它们不同）。每个文件中都有一些共享相同“特征”的行。下面是一个示例：file_1看起来像这样：

mat1 1000 2000 TEXT      //this means the range is from 1000 - 2000
mat1 2040 2050 TEXT
mat3 10000 10010 TEXT
mat2 20 500 TEXT

file_2的内容如下:

mat3 10009 TEXT
mat3 200 TEXT
mat1 999 TEXT

TEXT 是一些对我没有兴趣的字符和数字，mat 可以是 mat1 - mat50 中的任意一个，并且没有顺序；此外，可能会有 1000x 的 mat2（但下一列中的数字不同）。我需要以这样的方式找到适合的行：在比较的两行中，matX 是相同的，并且在 file_1 中提到的数字适合于在 file_2 中提到的范围内。因此，在我的例子中，我将找到一个匹配项：文件1的第3行和文件2的第1行（因为两者都是mat3，且10009介于10000和10010之间）。希望我已经讲清楚了！

所以我的问题是：您如何搜索匹配行？

是的，我使用Java作为编程语言。 编辑 现在我首先将巨大的文件分成小文件，这样我就不会遇到内存溢出的问题了。我还认为将（许多）小文件彼此比较比两个巨大的文件彼此比较更快。之后我可以按照上述方法进行比较。这可能不是完美的方法，但我仍在学习;-) 尽管如此，你们所有人的方法对我来说都非常有帮助，谢谢你们的回复！

- Grrace

---

你在问题中标记了 java，这是否意味着你只想用Java来完成它？ - Igor Zinov'yev

我不知道那是否能帮到你。 - Jean-nicolas

听起来这是内存映射的一个很好的使用案例（并且首先要对文件进行碎片整理），但我不知道Java是否提供此功能。 - Kerrek SB

你需要找到这两个文件之间的共同行吗？还是说你真的想进行差异比较(diff)操作？我不确定我理解你的要求。 - Perception

在这种情况下，您需要对file_2进行预处理，以便您拥有50个数据结构（mat1..mat50），每个数据结构都有一个按下限排序的范围数组，以便您可以在其上执行二进制搜索。对于4000万行，不应超过1GB。然后按顺序遍历file_1并查找每一行。 - Ingo

Answer 1

在理想情况下，您可以将file_2的每一行都读入内存（可能使用快速查找对象，如HashSet，具体取决于您的需求），然后逐行读入file_1中的每一行，并将其与保存file_2行的数据结构进行比较。

由于您已经说过内存不足，因此我认为最好采用分治策略。您可以使用上述相同的方法，但是读取file_2的一半（或三分之一、四分之一等，具体取决于您可以使用多少内存）并存储它们，然后比较file_1中的所有行。然后再次读取下一半/三分之一/四分之一/任何数量的文件到内存中（替换旧行）并再次遍历file_1。这意味着您必须多次遍历file_1，但是必须考虑内存限制。

---

编辑：根据您问题中添加的细节，我会在部分回答中进行更改。与其读取所有file_2（或以块为单位），然后逐行读取file_1，不如反过来，因为file_1包含要检查的数据。

另外，关于搜索匹配行。我认为最好的方法是对file_1进行一些处理。创建一个HashMap<List<Range>>，将字符串（"mat1" - "mat50"）映射到Range列表（仅是一个起始范围int和结束范围int的包装器），并使用file_1中的数据填充它。然后编写一个类似于以下函数的函数（忽略错误检查）。

boolean isInRange(String material, int value)
{
    List<Range> ranges = hashMapName.get(material);
    for (Range range : ranges)
    {
        if (value >= range.getStart() && value <= range.getEnd())
        {
            return true;
        }
    }
    return false;
}

并且对于 file_2 中的每一行（已解析），都要调用它。

- epochengine

Answer 2

我认为你的方法相当合理。

我可以想象出不同的策略 -- 例如，您可以在比较之前对两个文件进行排序（其中有有效的文件排序实现，unix sort工具可以在几分钟内排序多个GB的文件），并且在排序后，您可以按顺序逐行比较文件。

但这是一种相当复杂的方式 -- 您需要运行外部程序（sort），或者自己编写可比较高效的Java文件排序实现 -- 这本身就不是一项容易的任务。因此，为了简单起见，我认为您分块读取的方式非常有前途；

至于如何找到合理的块 -- 首先，"越多越好"可能不正确 -- 我认为所有工作的时间会呈渐近增长，到达某个常数线。所以，也许您会比您想象中更快地接近该线 -- 您需要基准测试。

接下来 -- 您可以像这样将行读入缓冲区：

final List<String> lines = new ArrayList<>();
try{
    final List<String> block = new ArrayList<>(BLOCK_SIZE);
    for(int i=0;i<BLOCK_SIZE;i++){
       final String line = ...;//read line from file
       block.add(line);
    }
    lines.addAll(block); 
}catch(OutOfMemory ooe){
    //break
}

所以您需要读取尽可能多的行，留下最后 BLOCK_SIZE 的空闲内存。BLOCK_SIZE 应该足够大，以使您的程序在没有 OOM 的情况下运行。

- BegemoT

---

同意，在读取了几兆字节后，继续读取数据可能不会有太大的收益（考虑磁盘缓存的大小）。你需要确保将CPU密集型工作与磁盘密集型工作交替进行，让磁盘赶上并缓冲更多的数据。 - Kothar

Answer 3

我从未处理过这么大的文件，但这是我的想法，应该可行。

你可以研究一下哈希。使用SHA-1散列。

导入以下内容。

import java.io.FileInputStream;
import java.security.MessageDigest;

一旦您的文本文件等已加载，请让它循环遍历每一行，并在结束时打印出哈希值。下面的示例链接将更深入地介绍。

StringBuffer myBuffer = new StringBuffer("");
//For each line loop through
    for (int i = 0; i < mdbytes.length; i++) {
        myBuffer.append(Integer.toString((mdbytes[i] & 0xff) + 0x100, 16).substring(1));
    }
System.out.println("Computed Hash = " + sb.toString());

以文本文件为重点的SHA代码示例

关于在JAVA中计算SHA的SO问题（可能有帮助）

另一个哈希代码示例。

简单地分别读取每个文件，如果处理结束时每个文件的哈希值相同，则两个文件是相同的。否则就有问题。

然后，如果您得到不同的值，可以进行超级耗时的逐行检查。

总的来说，逐行读取等等似乎需要很长时间。如果您想找到每个单独的差异，我会这样做。但我认为哈希会更快地看出它们是否相同。

SHA校验和

- sealz

Answer 4

这里存在一个权衡：如果你读取了文件的大块内容，你可以节省磁盘寻道时间，但是你可能会读取一些不必要的信息，因为变化可能只出现在文件的前几行。

你应该进行一些实验[基准测试]，使用不同的块大小，以找到平均情况下最优的读取块大小。

- amit

Answer 5

不确定这个答案有多好，但是看一下这个页面：http://c2.com/cgi/wiki?DiffAlgorithm - 它总结了一些差异算法。Hunt-McIlroy算法可能是更好的实现。从那个页面还有一个链接到GNU diff的Java实现。然而，我认为在C/C++中实现并编译成本地代码会更快。如果你被困在Java中，你可能需要考虑JNI。

- Aleks G

---

在我的4GB电脑上，对于350000行文件的差异检测已经失败了。想象一下如果内存需求仅呈线性增长，你需要多少内存！ - Ingo

Answer 6

确实，这可能需要一段时间。您必须进行1,200,000,000行比较。 有几种可能的方法可以将其加速一个数量级：

其中之一是对file2进行排序，并在文件级别上进行二进制搜索。 另一种方法：计算每行的校验和，并搜索该校验和。根据平均行长度，所涉及的文件会小得多，如果以固定格式（即长整型）存储校验和，则确实可以进行二进制搜索。

然而，从file_1中一次读取的行数并不重要。在面对巨大的复杂性时，这是微观优化。

- Ingo

Answer 7

如果你想要一个简单的方法：你可以对两个文件进行哈希并比较哈希值。但是如果文件不同，使用你的方法可能会更快。关于内存消耗：只需确保你使用足够的内存，不使用缓冲区处理这种事情是一个坏主意。

而所有关于哈希、校验和等的答案：它们并不更快。在两种情况下都必须读取整个文件。使用哈希/校验和甚至还需要计算某些东西...

- duedl0r

Answer 8

你可以对每个文件进行排序，例如使用UNIX的sort命令或Java中的类似命令。然后逐行读取已排序的文件以执行归并排序。

- Peter Lawrey

---

我很感兴趣，于是我开始寻找如何使排序在处理如此大的文件时更加高效。https://dev59.com/4HNA5IYBdhLWcg3wgeOk - Kothar

Answer 9

如果你想确切地知道文件是否不同，那么没有比逐个比较更好的解决方案。

但是，你可以使用一些启发式方法来告诉你文件是否相同。 1）检查文件大小；这是最简单的方法。 2）随机选择一个文件位置，并比较两个文件中从该位置开始的字节块。 3）重复步骤2）以达到所需的概率。

你应该计算和测试你的程序需要多少读取（和块大小）才是有用的。

- Mariy

Answer 10

我的解决方案是先生成一个文件的索引，然后使用它来进行比较。这类似于其他答案中使用哈希的方法。

你提到行数最多达到了约4500万。这意味着你可以（可能）使用每个条目16字节（128位）的索引，并且它将使用约45,000,000*16 = ~685MB的RAM，这在现代系统上并不算过大。在使用我下面描述的解决方案时会有一些开销，因此您可能仍然需要使用其他技术，如内存映射文件或磁盘表来创建索引。请参见Hypertable或HBase，了解如何将索引存储在快速磁盘哈希表中。

因此，完整的算法应该是：

1. 创建一个哈希映射，将Long类型映射到Long列表中（HashMap<Long，List<Long>>）
2. 获取第一个文件中每行的哈希（Object.hashCode应该足够了）
3. 获取行在文件中的偏移量，以便之后可以找到它
4. 将偏移量添加到与哈希码匹配的行列表中
5. 将第二个文件的每一行与索引中的行偏移量集合进行比较
6. 保留具有匹配条目的任何行

编辑： 针对您修改过的问题，这本身并不会有太大的帮助。您可以只对行的前一部分进行哈希处理，但这样只会创建50个不同的条目。但是，您可以在数据结构中创建另一层，将每个范围的开头映射到它所来自的行的偏移量。

因此，类似于index.get("mat32")的东西将返回一个TreeMap范围。您可以寻找您要查找的值之前的范围lowerEntry()。这样一来，您就可以快速检查给定的matX/数字组合是否在您正在检查的范围内。

- Kothar