如何比较大型文本文件？

我对你对我的“技术”的看法有一个普遍的疑问。如何比较大型文本文件？

有两个文本文件（file_1和file_2）需要相互比较。两者都非常巨大（3-4千兆字节，每个3000万到4500万行）。我的想法是将file_1的几行（尽可能多）读到内存中，然后将这些行与全部行的file_2进行比较。如果匹配，则匹配的两个文件中的行应写入新文件。然后继续下一行1000行file_1，也比较那些全部行file_2，直到我完全通过file_1。

但这听起来确实非常耗时且对我来说很复杂。你能想出其他方法来比较这两个文件吗？

您认为比较可能需要多长时间？对于我的课程，时间并不重要。我没有处理这些庞大文件的经验，因此我不知道这可能需要多长时间。但不应该超过一天。 ;-)但我恐怕我的技术可能会永远...

刚才出现在我脑海中的Antoher问题：你会在内存中读多少行？越多越好？有没有办法在实际尝试之前确定可能的行数？我想尽可能多的阅读（因为我认为这样会更快），但我经常用完内存。

在此先感谢。

编辑我想我必须多解释一下我的问题。

目的不是看两个文件一般是否相同（它们不是）。每个文件中有一些共享相同“特征”的行。下面是一个例子： 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_2中提到的数字符合file_1中提及的范围。所以在我的例子中，我会找到一个匹配：file_1的第3行和file_2的第1行（因为mat3和10009都在10000和10010之间）。我希望这对你很清楚！

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

是的，我使用Java作为我的编程语言。

编辑我现在先分了巨大的文件，使我有被淘汰的内存没有问题。我也认为将比较（很多）较小的文件比两个大文件比较快。之后，我可以按照上面提到的方式比较它们。这可能不是完美的方式，但我仍然在学习;-) 但是，所有的方法都对我非常有帮助，谢谢你的回复！

来源

2011-08-18 Grrace

您标记'java'的问题，这是否意味着你只是想这样做在Java中？ –

我不知道这是否可以帮助你 http://stackoverflow.com/questions/964332/java-large-files-disk-io-performance –

听起来像是不错的使用情况内存映射（和首先对文件进行碎片整理），但我不知道Java是否提供了这种功能。 –

既然您已经提供了更多细节，我将采用的方法依赖于预分区，并且可以在搜索匹配之前进行排序。

这应该消除大量的比较，否则在天真的蛮力方法中无论如何不会匹配。为了争论起见，让我们把这两个文件夹在4000万行。

分区：通读file_1和发送的所有行与mat1开始file_1_mat1，等等。 file_2也一样。这是一个小的grep微不足道的，或者你是否应该用Java编程，这是一个初学者的练习。

这是一次读取总共8000万行读取的两个文件，产生两组平均每个80万行的50个文件。

排序：对于每个分区，排序根据仅在第二列中的数字值（从file_1下界和从file_2实际数量）。即使80万行不能放入内存中，我们也可以调整2路外部合并排序，并且比未排列的空间更快地执行此操作（读取次数更少）。

比较：现在你只需要遍历一次通过两对file_1_mat1和file_2_mat1，而不需要将你的东西在内存中，输出匹配到输出文件。依次重复其余的分区。不需要最终的“合并”步骤（除非您正在并行处理分区）。

即使没有分类阶段你已经做的工作应该更快速地50对文件的80万行，每行，而不是两个文件各40万线的幼稚比较。

来源

2011-08-18 15:18:47

谢谢，我昨天没有阅读你的评论，但尝试了你的解释，因为我认为它可以正常工作。只是一个小小的改变：我开始整理大文件，然后将它们分开，现在将继续进行比较。这比处理庞大的文件要容易得多，而且花费的时间也不多。 – Grrace

有一个折衷：如果您读取了一大块文件，则会保存光盘seek time，但您可能已经读取了您不需要的信息，因为在第一行中遇到了更改。

在平均情况下，您应该运行一些实验[基准测试]，使用不同的块大小来找出最佳读取块。

来源

2011-08-18 12:40:12 amit

尽量避免内存消耗并使其消耗光盘。我的意思是将每个文件分成可加载大小的部分并进行比较，这可能需要一些额外的时间，但会使您安全地处理内存限制。

来源

2011-08-18 12:44:03

我从来没有使用过如此巨大的文件，但这是我的想法，应该工作。

你可以看看哈希。使用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 Code example focusing on Text File

SO Question about computing SHA in JAVA (Possibly helpful)

Another sample of hashing code.

简单读取每个文件seperatley，如果每个文件的散列值是在所述过程结束时相同，则这两个文件是相同的。如果没有，那么有什么不对。

然后，如果你有不同的价值，你可以做超级耗时的逐行检查。

总体而言，似乎逐行读取逐行等将永远占用。如果你试图找出每个人的差异，我会这样做。但我认为散列会更快，看看它们是否相同。

SHA checksum

来源

2011-08-18 12:44:16 sealz

不知道如何很好的答案，这将是 - 但看看这个页面：http://c2.com/cgi/wiki?DiffAlgorithm - 总结了几个差异算法。 Hunt-McIlroy算法可能是更好的实现。从该页面还有一个指向GNU diff的java实现的链接。不过，我认为在C/C++中编译为本地代码的实现会更快。如果你坚持使用java，你可能会考虑JNI。

来源

2011-08-18 12:46:29

我想看看差异不会在3500万行上崩溃的机器...... – Ingo

我没有试过这个 - 但它可能是一个很好的测试。 –

在我的4GB PC上，350.000行文件上的差异已经失败。猜猜如果内存需求增长为线性，你需要多少内存！ – Ingo

在理想的世界中，您可以将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 s的列表（仅用于startOfRange int和endOfRange 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的每个（已分析）行调用它。

来源

2011-08-18 12:47:15

事实上，这可能需要一段时间。你必须做1,200.000,000行比较。有几种可能性，以加快顺序magnifying：

一个将排序file2并做文件级别的二进制搜索。另一种方法：计算每一行的校验和，然后搜索它。根据平均线长，有问题的文件会更小，你，如果你存储在固定格式校验（即长）

的行数从file_1读一次真的可以做一个二进制搜索不过不是的事。面对非常复杂的情况，这是微观优化。

来源

2011-08-18 12:47:31 Ingo

如果你想要一个简单的方法：你可以散列两个文件并比较散列。但它可能更快（特别是如果文件不同）使用你的方法。关于内存消耗：只要确保你使用足够的内存，使用没有缓冲区这种事情是一个坏主意。

所有那些关于散列，校验和等的答案：那些不是更快。在这两种情况下你都必须阅读整个文件。使用哈希/校验和，你甚至不得不计算一些东西......

来源

2011-08-18 12:47:41 duedl0r

你可以做的是对每个单独的文件进行排序。例如UNIX中的或类似的。您可以一次读取一行中的排序文件以执行合并排序。

来源

2011-08-18 12:50:57

我很好奇，所以我开始寻找如何有效地处理这种大文件。 http://stackoverflow.com/questions/930044/why-unix-sort-command-could-sort-a-very-large-file –

使用源码控制如Mercurial怎么样？我不知道，也许它不完全是你想要的，但这是一个旨在追踪修订之间变化的工具。您可以创建一个存储库，提交的第一个文件，然后用另一个覆盖它的承诺第二个：

hg init some_repo 
cd some_repo 
cp ~/huge_file1.txt . 
hg ci -Am "Committing first huge file." 
cp ~/huge_file2.txt huge_file1.txt 
hg ci -m "Committing second huge file."

从这里你可以得到一个差异，告诉你什么行不同。如果你能以某种方式使用该差异来确定哪些线是相同的，那么你将全部设置。

这只是一个想法，有人纠正我，如果我错了。

来源

2011-08-18 12:52:22

你不需要源控制，以获得差异，你可以使用Unix命令'diff '。 – Jeff

但在如此巨大的文件，差异可能不会正常工作。 – Jeff

我想，你的方式是比较合理的。

我能够想象不同的策略 - 例如，你可以比较前两个文件进行排序（其中是有效率的执行文件排序，而UNIX排序实用程序可以在几分钟内排序几个GB的文件），并且，同时排序，你可以比较顺序阅读文件，逐行阅读。

但是这是一种相当复杂的方式 - 你需要运行外部程序（排序），或者在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

来源

2011-08-18 12:57:21 BegemoT

同意，在几兆字节后，读取更多数据可能不会获得太多收益（例如，考虑磁盘缓存的大小）。您需要确保将一些CPU绑定的工作与磁盘绑定的工作交错，以让磁盘赶上并缓冲更多数据。 –

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

然而，如果文件是相同的，你可以做出一些启发式的方法来告诉你某种概率。 1）检查文件大小;这是最简单的。 2）取一个随机的文件位置并比较两个文件中从这个位置开始的字节块。 3）重复步骤2）以达到所需的概率。

您应该计算并测试您的程序有多少次读取（以及块的大小）。

来源

2011-08-18 13:12:07 Marii

我的解决方案是先生成一个文件的索引，然后用它来做比较。这与使用散列的其他一些答案类似。

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

因此，在充分，算法会是这样的：

创建一个哈希地图，龙映射到多头的列表（HashMap的<长，名单<龙>>）
获取第一个文件中每行的散列（Object。的hashCode应该是足够了）
获得该行的文件中的偏移，所以你可以再次找到它后
添加的偏移量与在哈希表
匹配哈希码线的列表进行比较的每一行第二个文件索引
设定线偏移保持具有匹配条目

编辑： 在回答你的问题，编辑，这不会真正本身帮助。你可以散列该行的第一部分，但它只会创建50个不同的条目。然后，您可以在数据结构中创建另一个级别，它将每个范围的开始映射到它所来自的行的偏移量。

所以像index.get("mat32")这样的东西会返回一个范围的TreeMap。您可以查找您要查找的值前面的范围lowerEntry()。在一起，这将给你一个相当快的检查，看看一个给定的matX /数字组合是否在你正在检查的范围之一。

来源

2011-08-18 13:19:12

我会尝试以下操作：对于您正在比较的每个文件，在磁盘上创建临时文件（以后称其为部分文件），以表示每个字母字母以及其他所有字符的附加文件。然后逐行读取整个文件。同时这样做，将行插入到与它开头的字母相对应的相关文件中。既然你已经完成了这两个文件，你现在可以限制一次加载两个较小文件的比较。例如以A开头的行只能出现在一个部分文件中，并且不需要多次比较每个部分文件。如果生成的文件仍然非常大，则可以对生成的部分文件（字母特定文件）应用相同的方法，通过根据文件中的第二个字母创建文件来进行比较。这里的交易将暂时使用大磁盘空间，直到该过程完成。在这个过程中，这里其他帖子中提到的方法可以帮助更有效地处理部分文件。

来源

2011-08-18 14:31:20

如何比较大型文本文件？

回答

相关问题