在大文本文件中查找重複記錄

Question

我在Linux機器上（Redhat），我有一個11GB的文本文件。文本文件中的每行包含單個記錄的數據，並且該行的前n個字符包含記錄的唯一標識符。該文件包含超過2700萬條記錄。

我需要驗證文件中是否有多個具有相同唯一標識符的記錄。我還需要在一個80GB的文本文件上執行此過程，因此任何需要將整個文件加載到內存中的解決方案都不實際。

Answer 1

逐行讀取文件，因此您不必將其全部加載到內存中。

對於每一行（記錄）創建一個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) 

Answer 2

我絕不會建議您嘗試在Python中過濾如此龐大的文本文件。無論你如何處理它，你都需要經過一些複雜的步驟來確保你不會耗盡內存。

首先想到的是創建行的散列，然後使用散列來查找重複。既然您保存了行號，那麼您可以直接比較文本以確保沒有散列衝突。

但是，最簡單的解決方案是將文本文件轉換爲數據庫，以便您快速地對重複項目進行排序，搜索和過濾。然後，您可以使用該文件重新創建文本文件，如果這確實是需求。

Answer 3

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) 

也許這會幫助你弄好了，祝你好運。

Answer 4

假設我不能使用一個數據庫，我會嘗試像

# 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) 

Answer 5

試試這個：

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

這將輸出任何重複的識別碼，以及如何很多時候他們出現了。

Answer 6

我還沒有嘗試過這個文件相當大，但是...假設n個字符的固定位置是7，並且行不超過999 + 7個字符這可能會做作業：

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

Answer 7

該工作的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 

是的，我想大多數代碼，它應該工作:)