6

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

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

4

7 回答 7

7

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

为每一行（记录）创建一个 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)
于 2013-05-02T21:53:20.473 回答
1

正确的工作工具：将您的记录放入数据库。除非你手头有 Postgres 或 MySQL 安装，否则我会选择 sqlite。

$ sqlite3 uniqueness.sqlite
create table chk (
  ident char(n), -- n as in first n characters
  lineno integer -- for convenience
);
^D

然后我将唯一标识符和行号插入到该表中，可能使用如下 Python 脚本：

import sqlite3 # install pysqlite3 before this
n = ... # how many chars are in the key part
lineno = 0

conn = sqlite3.connect("uniqueness.sqlite")
cur = conn.cursor()
with open("giant-file") as input:
  for line in input:
    lineno +=1
    ident = line[:n]
    cur.execute("insert into chk(ident, lineno) values(?, ?)", [ident, lineno])
cur.close()
conn.close()

在此之后，您可以索引表并使用 SQL：

$ sqlite3 uniqueness.sqlite
create index x_ident on chk(ident); -- may take a bit of time

-- quickly find duplicates, if any
select ident, count(ident) as how_many
from chk
group by ident
having count(ident) > 1;

-- find lines of specific violations, if needed
select lineno 
from chk
where ident = ...; -- insert a duplicate ident

是的，我尝试了大部分代码，它应该可以工作:)

于 2013-05-02T22:35:07.017 回答
0

尝试这个：

n=unique identifier size
cat 11gb_file | cut -c-$n | sort | uniq -cd

这将输出任何重复的标识符以及它们出现的次数。

于 2013-05-02T21:22:51.020 回答
0

我永远不会建议您尝试在 Python 中过滤如此庞大的文本文件。不管你如何处理它，你都需要通过一些复杂的步骤来确保你不会耗尽内存。

首先想到的是创建行的散列，然后使用散列查找重复项。由于您还保存了行号，因此您可以直接比较文本以确保没有哈希冲突。

但是，最简单的解决方案是将文本文件转换为允许您快速排序、搜索和过滤重复项目的数据库。然后，如果确实需要，您可以使用它重新创建文本文件。

于 2013-05-02T21:12:39.587 回答
0

在 Python 中逐行读取大型文本文件，而不将其加载到内存中

这个问题的答案是这样的，

with open("log.txt") as infile:
    for line in infile:
        do_something_with(line)

也许这会对你有所帮助，祝你好运。

于 2013-05-02T21:16:54.133 回答
0

假设我不能使用数据库，我会尝试类似的东西

# read the file one line at a time http://stackoverflow.com/a/6475407/322909,
#be sure to read the comments

keys = set()

with open("bigfile.txt") as f:
    for line in f:
        key = get_key(line)
        if key in keys:
            print "dup"
        else:
            keys.add(key)
于 2013-05-02T21:17:48.387 回答
0

我没有在那么大的文件上尝试过这个，但是......假设 n 个字符的固定位置是 7，并且行不超过 999+7 个字符，这可能会完成这项工作：

 awk  'BEGIN{FIELDWIDTHS="7 999"} ! a[$1]++' file > newfile
于 2013-05-02T21:48:05.907 回答