python - 在大文本文件中查找重复记录

Question

我在 Linux 机器 (Redhat) 上，我有一个 11GB 的文本文件。文本文件中的每一行都包含一条记录的数据，该行的前 n 个字符包含该记录的唯一标识符。该文件包含略多于 2700 万条记录。

我需要验证文件中没有多个记录具有相同的唯一标识符。我还需要对一个 80GB 的文本文件执行此过程，因此任何需要将整个文件加载到内存中的解决方案都不实用。

Answer 1

逐行读取文件，因此您不必将其全部加载到内存中。

为每一行(记录)创建一个 sha256 哈希(32 字节)，除非您的标识符更短。

将散列/标识符存储在 numpy.array 中。这可能是存储它们的最紧凑的方式。 2700 万条记录乘以 32 字节/哈希是 864 MB。这应该适合如今体面的机器的内存。

为了加快访问速度，您可以使用第一个，例如2 个字节的散列作为 collections.defaultdict 的键，并将其余散列放在值的列表中。这实际上会创建一个包含 65536 个桶的哈希表。对于 27e6 条记录，每个桶平均包含大约 400 个条目的列表。这意味着比 numpy 数组搜索速度更快，但会使用更多内存。

d = collections.defaultdict(list)
with open('bigdata.txt', 'r') as datafile:
    for line in datafile:
        id = hashlib.sha256(line).digest()
        # Or id = line[:n]
        k = id[0:2]
        v = id[2:]
        if v in d[k]:
            print "double found:", id
        else:
            d[k].append(v)