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

Question

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

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

Answer 1

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

除非您的标识符较短，否则为每一行（记录）创建一个 sha256 哈希（32 字节）。

将散列/标识符存储在numpy.array. 这可能是最紧凑的存储方式。2700 万条记录乘以 32 字节/哈希为 864 MB。这应该适合这些天像样的机器的记忆。

为了加快访问速度，您可以使用散列的前例如 2 个字节作为 a 的键，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)