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

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

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

2013-05-02 Justin Kredible

听起来像它的时间为一个数据库。这是一个巨大的文件。 – squiguy 2013-05-02 21:10:58

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

对于每一行（记录）创建一个sha256散列（32字节），除非你的标识符更短。

将散列/标识符存储在numpy.array中。这可能是最紧凑的方式来存储它们。 27百万记录次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)

来源

2013-05-02 21:53:20

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

首先想到的是创建行的散列，然后使用散列来查找重复。既然您保存了行号，那么您可以直接比较文本以确保没有散列冲突。

但是，最简单的解决方案是将文本文件转换为数据库，以便您快速地对重复项目进行排序，搜索和过滤。然后，您可以使用该文件重新创建文本文件，如果这确实是需求。

来源

2013-05-02 21:12:39 eandersson

Read large text files in Python, line by line without loading it in to memory

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

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

也许这会帮助你弄好了，祝你好运。

来源

2013-05-02 21:16:54 0xhughes

假设我不能使用一个数据库，我会尝试像

# 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-02 21:17:48 John

如果你打算这样做，你*真的*希望'键'是一个集合，而不是一个列表。 – 2013-05-02 21:18:12

@NolenRoyalty，很好的电话，固定。 – John 2013-05-02 21:19:53

试试这个：

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

这将输出任何重复的识别码，以及如何很多时候他们出现了。

来源

2013-05-02 21:22:51 rzymek

排序27万字将是一个昂贵的操作。 – 2013-05-02 21:48:07

@glennjackman：如果有多个重复项，它可能是非常值得的。 – 9000 2013-05-02 22:07:57

与'sort 11gb_file |相似uniq -cdw $ n' – svante 2013-05-03 07:33:43

我还没有尝试过这个文件相当大，但是...假设n个字符的固定位置是7，并且行不超过999 + 7个字符这可能会做作业：

awk 'BEGIN{FIELDWIDTHS="7 999"} ! a[$1]++' file > newfile

来源

2013-05-02 21:48:05 tink

该工作的Rigth工具：将您的记录放入数据库。除非您已经安装了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-02 22:35:07 9000

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

回答

相关问题