如何比较大文本文件？
关于你对我的“技巧”的看法，我有一个普遍的问题。
有2个文本文件（ file_1和file_2 ）需要相互比较。 两者都非常庞大（3-4千兆字节，每个30,000,000到45,000,000行）。 我的想法是将file_1几行（尽可能多的） file_1入内存，然后将它们与file_2 所有行进行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_2适合file_1提到的范围。 所以在我的例子中我会找到一个匹配： file_1第3行和file_1第1 file_2 （因为mat3和10009都在10000和10010之间）。 我希望这能让你清楚！
所以我的问题是：你将如何搜索匹配的行？
是的，我使用Java作为我的编程语言。
编辑我现在首先划分大文件，以便我没有内存不足的问题。 我还认为比这两个巨大的文件比较（很多）较小的文件要快。 之后，我可以按照上面提到的方式对它们进行比较。 它可能不是完美的方式，但我仍在学习;-)尽管如此，你所有的方法对我都非常有帮助，谢谢你的回复！
既然你已经给了我们更多的细节，我将采取的方法依赖于预分区，并且可选地在搜索匹配之前进行排序。
这应该消除大量的比较，这些比较在天真的暴力方法中无论如何都是不匹配的。 为了争论，让我们将这两个文件都固定在每个4000万行。
分区：读取file_1并将以file_1_mat1开头的所有行发送到file_1_mat1 ，依此类推。 对file_2执行相同file_2 。 这是一个微不足道的小grep ，或者如果你希望用Java编程，这是一个初学者的练习。
这是一次通过两个文件，总共读取了8000万行，产生了两组平均每个800,000行的50个文件。
排序：对于每个分区，仅根据第二列中的数值排序（ file_1和file_1的实际数字）。 即使800,000行不能适应内存，我想我们可以调整双向外部合并排序，并且比整个未分区空间更快地执行（整体读取更少）。
比较：现在你只需要通过两对file_1_mat1和file_2_mat1迭代一次 ，而不需要在内存中保留任何内容，输出匹配到输出文件。 依次重复其余分区。 无需最终的“合并”步骤（除非您并行处理分区）。
即使没有排序阶段，您已经在做的天真比较应该在50对文件中更快地工作，每个文件有800,000行，而不是两个文件，每个文件有4000万行。
我想，你的方式很合理。
我可以想象不同的策略 – 例如，您可以在比较之前对这两个文件进行排序（其中有高效的filesort实现，而unix排序实用程序可以在几分钟内对几个Gbs文件进行排序），并且，在排序后，您可以随后比较文件，阅读逐行。
但这是一个相当复杂的方法 – 你需要运行外部程序（排序），或者自己在java中编写类似的有效的filesort实现 – 这本身并不是一件容易的事。 因此，为了简单起见，我认为你的阅读方式很有前途;
至于如何找到合理的阻滞 – 首先，它可能不正确“越多越好” – 我认为，所有工作的时间将逐渐增长到一些恒定的线。 所以，你可能会比你想象的更接近那条线 – 你需要基准。
接下来 – 您可以像这样读取缓冲行：
final List lines = new ArrayList<>(); try{ final List block = new ArrayList<>(BLOCK_SIZE); for(int i=0;i
所以你可以尽可能多地阅读 - 留下最后一块BLOCK_SIZE的空闲内存。 对于你们其余的程序来说，BLOCK_SIZE应该很大，无需OOM即可运行
在理想的世界中，您可以将file_2的每一行读入内存（可能使用快速查找对象，如HashSet ，具体取决于您的需要），然后逐个读取file_1中的每一行并将其与保存来自file_2的行的数据结构。
正如你所说的那样，你的内存不足，我认为分而治之的策略是最好的。 您可以使用与我上面提到的相同的方法，但是读取文件_2中的行的一半（或三分之一，四分之一……取决于您可以使用多少内存）并存储它们，然后比较所有行在file_1中。 然后读入下一半/第三/四分之一/无论进入内存（替换旧行）并再次通过file_1。 这意味着您必须更多地浏览file_1，但您必须处理内存限制。
编辑：为了回答你问题中的更多细节，我会部分改变我的答案。 而不是一次读取所有file_2（或在块中）并在file_1中读取一行，而是反过来，因为file_1保存要检查的数据。
此外，关于搜索匹配的行。 我认为最好的方法是在file_1上进行一些处理。 创建一个HashMap ，将String（“mat1” – “mat50”）映射到Range s列表（只是startOfRange int和endOfRange int的包装器），并用file_1中的数据填充它。 然后编写一个函数（忽略错误检查）
boolean isInRange(String material, int value) { List ranges = hashMapName.get(material); for (Range range : ranges) { if (value >= range.getStart() && value <= range.getEnd()) { return true; } } return false; }
并为file_2的每个（已解析的）行调用它。
有一个权衡：如果你读了一大块文件，你就可以节省光盘搜索时间 ，但是你可能已经阅读了不需要的信息，因为在第一行遇到了变化。
您可能应该运行一些具有不同块大小的实验[基准测试]，以找出在一般情况下要读取的最佳块。
不确定答案会有多好 – 但请看一下这个页面： http ： //c2.com/cgi/wiki？DifAlgorithm – 它总结了一些差异算法。 Hunt-McIlroy算法可能是更好的实现。 从该页面还有一个指向GNU diff的java实现的链接。 但是，我认为在C / C ++中实现并编译成本机代码会更快。 如果你坚持使用java，你可能需要考虑JNI。
实际上，这可能需要一段时间。 您必须进行1,200.000,000行比较。 有几种可能性可以加快这个速度：
一种方法是对文件2进行排序，并在文件级别进行二进制搜索。 另一种方法：计算每一行的校验和，然后搜索。 根据平均线长度，相关文件会小得多，如果以固定格式存储校验和（即很长），您真的可以进行二进制搜索
但是，您从file_1一次读取的行数并不重要。 面对极大的复杂性，这是微观优化。
如果您想要一个简单的方法：您可以散列两个文件并比较散列。 但是使用你的方法可能会更快（特别是如果文件不同）。 关于内存消耗：只要确保你使用足够的内存，使用没有缓冲区这样的东西是个坏主意..
所有这些关于哈希，校验和等的答案：那些并不快。 在这两种情况下，您都必须阅读整个文件。 使用哈希/校验和，你甚至需要计算一些东西……
您可以做的是对每个单独的文件进行排序。 例如Java中的UNIX sort或类似的东西。 您可以一次读取一行的已排序文件以执行合并排序。
我从未使用过如此庞大的文件，但这是我的想法，应该可行。
你可以看看哈希。 使用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的问题（可能有帮助）
另一个散列代码示例。
简单读取每个文件seperatley，如果每个文件的哈希值在进程结束时相同，那么这两个文件是相同的。 如果没有，则出现问题。
然后，如果您获得不同的值，您可以逐行检查超级耗时。
总的来说，似乎逐行逐行阅读将需要永远。 如果你想找到每个人的差异，我会这样做。 但我认为哈希会更快看到它们是否相同。
SHA校验和
如果您想确切地知道文件是否不同，那么没有比您更好的解决方案 – 顺序比较。
但是，如果文件相同，您可以使用某种启发式方法告诉您某种可能性。 1）检查文件大小; 这是最简单的。 2）取一个随机文件位置，比较两个文件中此位置开始的字节块。 3）重复步骤2）以达到所需的概率。
您应该计算并测试有多少读取（以及块的大小）对您的程序有用。
我的解决方案是首先生成一个文件的索引，然后使用它来进行比较。 这类似于其他一些答案，因为它使用散列。
你提到线路数量高达约4500万。 这意味着你可以（可能）存储一个索引，每个条目使用16个字节（128位），它将使用大约45,000,000 * 16 = ~685MB的RAM，这在现代系统上并不合理。 使用我在下面描述的解决方案有一些开销，因此您可能仍然发现需要使用其他技术（如内存映射文件或基于磁盘的表）来创建索引。 有关如何在快速基于磁盘的哈希表中存储索引的示例，请参阅Hypertable或HBase 。
所以，完整的算法将是这样的：
- 创建一个将Long映射到Longs列表的哈希映射（HashMap
- 获取第一个文件中每行的哈希值（Object.hashCode应该足够）
- 获取行文件中的偏移量，以便稍后再次找到它
- 将偏移量添加到哈希映射中具有匹配hashCodes的行列表中
- 将第二个文件的每一行与索引中的行偏移量进行比较
- 保留任何具有匹配条目的行
编辑：回答您编辑的问题，这本身并没有多大帮助。 你可以只哈希该行的第一部分，但它只会创建50个不同的条目。 然后，您可以在数据结构中创建另一个级别，这会将每个范围的开头映射到它来自的行的偏移量。
所以像index.get("mat32")类的东西会返回范围的TreeMap。 您可以查找要查找lowerEntry（）的值之前的范围。 这将为您提供一个非常快速的检查，以查看给定的matX /数字组合是否在您正在检查的范围之一。
尽量避免使用内存并使其占用光盘。 我的意思是将每个文件分成可加载大小的部分并进行比较，这可能需要一些额外的时间，但会让你安全地处理内存限制。
如何使用像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."
从这里你可以得到一个差异，告诉你哪些线条不同。 如果你能以某种方式使用那个差异来确定哪些行是相同的，那么你就可以全部设置。
这只是一个想法，如果我错了，有人会纠正我。
我会尝试以下操作：对于您要比较的每个文件，在磁盘上创建临时文件（我将其称为部分文件），表示每个字母和其他所有字符的附加文件。 然后逐行读取整个文件。 在执行此操作时，将该行插入与其开头的字母对应的相关文件中。 既然你已经为这两个文件做了这些，你现在可以限制比较一次加载两个较小的文件。 例如，以A开头的行只能出现在一个部分文件中，并且不需要多次比较每个部分文件。 如果生成的文件仍然非常大，则可以通过根据文件中的第二个字母创建文件，对生成的部分文件（特定于字母的文件）应用相同的方法。 这里的交易将暂时使用大磁盘空间，直到该过程结束。 在此过程中，此处其他post中提到的方法可以帮助更有效地处理部分文件。