快速查找两个大文本文件之间的差异

Question

我有两个3GB的文本文件，每个文件大约有8000万行。它们共享99.9%相同的行（文件A有60000个唯一行，文件B有80000个唯一行）。

如何快速查找这两个文件中不同的行？是否有现成的命令行工具可以使用？我正在使用Python，但我猜想很难找到一种高效的Pythonic方法来加载文件并比较。

欢迎任何建议。

- jack

---

你的意思是99.9%的“文件”是相同的，还是说99.9%的“行”是相同的（即重复出现相同的行）？ - bstpierre

你在意这些行的顺序吗？B 中是否以与 A 相同的顺序拥有 A 的所有行？可以重排、删除行吗？有没有出现次数很重要的重复行（A 有 n 次，B 有 n-b 次-> 差别是 b*line）？ - Tony Veijalainen

如果您询问“现成的命令行工具”，您可能需要指定操作系统。在大多数情况下，“diff”要么是本地的，要么是移植的。但我无法确定您从问题中想要什么：也许在Linux上：sort --unique < file1 > uniq1; sort --unique < file2 > uniq1; diff uniq[12]。 - Tony Delroy

每行平均有多少字节？ - Daniel Stutzbach

@bstpierre，没错，这两个文件中99.9%的代码行都是相同的，但是独特的代码行随机分布在两个文件中。 - jack

Answer 1

如果顺序很重要，可以尝试使用comm工具。如果顺序不重要，可以使用sort file1 file2 | uniq -u。

- zwol

---

排序两个 3G 文件比 diff 快的原因是什么？ - bstpierre

@bstpierre: diff 实现通常是二次的，而排序在平均情况下通常是 n log n（快速排序）。 - tonfa

Answer 2

我认为这是最快的方法（无论是在Python还是其他语言中，都不应该太重要）。注意事项如下：

1.我仅存储每行的哈希值以节省空间（如果可能出现分页，则还可以节省时间）。

2.由于上述原因，我仅打印行号；如果您需要实际行，则只需重新读取文件即可。

3.我假设哈希函数的结果没有冲突。这几乎是确定的，但不是完全确定的。

4.我导入了hashlib，因为内置的hash()函数太短了，无法避免冲突。

import sys
import hashlib

file = []
lines = []
for i in range(2):
    # open the files named in the command line
    file.append(open(sys.argv[1+i], 'r'))
    # stores the hash value and the line number for each line in file i
    lines.append({})
    # assuming you like counting lines starting with 1
    counter = 1
    while 1:
        # assuming default encoding is sufficient to handle the input file
        line = file[i].readline().encode()
        if not line: break
        hashcode = hashlib.sha512(line).hexdigest()
        lines[i][hashcode] = sys.argv[1+i]+': '+str(counter)
        counter += 1
unique0 = lines[0].keys() - lines[1].keys()
unique1 = lines[1].keys() - lines[0].keys()
result = [lines[0][x] for x in unique0] + [lines[1][x] for x in unique1]

- max

---

对我来说，这是一个不错的答案，我只想建议在读取时保存每行的查找位置，以便快速恢复结果。 - Tony Veijalainen

Answer 3

有6万或8万个独特的行，您可以为每个唯一的行创建一个字典，并将其映射到一个数字。例如：mydict["hello world"] => 1等。如果您的平均行长约为40-80个字符，则这将在10 MB左右的内存范围内。

然后读取每个文件，通过字典将其转换为数字数组。它们将轻松适应内存（2个8字节* 3GB / 60k行的文件少于1 MB的内存）。然后比较列表。您可以反转字典并使用它来打印出不同的行的文本。

编辑：

针对您的评论，以下是一个示例脚本，它在读取文件时将数字分配给唯一的行。

#!/usr/bin/python

class Reader:

    def __init__(self, file):
        self.count = 0
        self.dict = {}
        self.file = file

    def readline(self):
        line = self.file.readline()
        if not line:
            return None
        if self.dict.has_key(line):
            return self.dict[line]
        else:
            self.count = self.count + 1
            self.dict[line] = self.count
            return self.count

if __name__ == '__main__':
    print "Type Ctrl-D to quit."
    import sys
    r = Reader(sys.stdin)
    result = 'ignore'
    while result:
        result = r.readline()
        print result

- Harold L

---

@Harold L，我很困惑。在不知道两个文件包含哪些行之前，我如何将 60,000 或 80,000 个唯一的行映射到一个字典中。 - jack

你可以在读取文件时直接构建字典。我将在上面添加一个辅助函数的代码。 - Harold L

dict.keys() 有 3 GB？我不相信你可以仅使用 seff.dict[line] 来保存哈希，而是它会将整行文本与哈希一起保存在键中。 - Tony Veijalainen

@Tony Veijalainen，是的，字典将保存整行内容，但每行只保存一次。因此，这种技术之所以在这里有效，仅因为Jack有许多重复的行：例如3GB可能是1亿行文本，但字典键集中只会存储8万个唯一行。 - Harold L

两个文件中没有重复的行。看看帖子作者在回复我的评论时说了什么，也许我没有正确理解他的英语。 - Tony Veijalainen

不幸的是，根据OP（对Tony的回应）的澄清，原始文件没有重复的行。 “99.9％相同的行”只是指这些行在两个文件中都存在的事实。有了这个澄清，您的方法不起作用，不幸的是。 - max

Answer 4

如果我理解正确，您想要这些文件中没有重复行。这个代码可以实现：

uniqA = set(open('fileA', 'r'))

- user97370

Answer 5

Python有difflib，声称与其他diff实用程序相当竞争，请参见： http://docs.python.org/library/difflib.html

- Tony Veijalainen

---

这个库能处理3GB的文本文件吗？！即使是好的数据库也很难完成这种任务...它们需要索引和其他优化才能在合理的时间内得出结果。 - Asaf

由于这些行是随机排列的，并且不需要找到行的更改，这可能不是最佳方法。如果两个文件是同一文件的版本（由于它们之间的行高度相似性而有可能），则会更合适。 - Tony Veijalainen