搜索文本以查找長串子列表

問題：給定一組約250000個整數用戶ID和大約1TB的JSON格式的每行記錄，將用戶ID匹配的記錄加載到數據庫。搜索文本以查找長串子列表

只有約1％的記錄與250000個用戶ID匹配。而不是JSON解碼每個記錄，這需要很長時間，我試圖使用字符串匹配來確定用戶ID是否在原始JSON中;如果匹配，那麼JSON將被解碼並檢查記錄，然後插入。

問題是將一個原始JSON字符串與包含〜250k字符串條目的集合匹配得很慢。

這裏是到目前爲止的代碼：

// get the list of integer user IDs 
cur.execute('select distinct user_id from users') 

// load them as text into a set 
users = set([]) 
for result in cur.fetchall(): 
    users.add(str(result[0])) 

// start working on f, the one-json-record-per-line text file 
for line in f: 
    scanned += 1 
    if any(user in line for user in users): 
     print "got one!" 
     // decode json 
     // check for correct decoded user ID match 
     // do insert

我這個接近的正確方法？什麼是匹配這些字符串的更快速的方法？目前，在尋找如此多的用戶ID時，這會在3ghz機器上每秒處理約2個條目（不太好）。當用戶ID列表非常短時，管理大約200000個條目/秒。

來源

2012-11-19 Leon Derczynski

看起來像一個真正的數據庫可能是這樣的更好的解決方案。不幸的是，我不使用數據庫，所以我不能推薦任何東西（雖然我猜別人會這麼做） – mgilson

這個，'for'循環中的'any'是非常昂貴的。你的行爲指數增長。 – Daenyth

Aho-Corasick出現此目的待建。甚至還有一個方便的Python模塊（easy_install ahocorasick）。

import ahocorasick 

# build a match structure 
print 'init empty tree' 
tree = ahocorasick.KeywordTree() 

cur.execute('select distinct user_id from users') 

print 'add usernames to tree' 
for result in cur.fetchall(): 
    tree.add(str(result[0])) 

print 'build fsa' 
tree.make() 

for line in f: 
    scanned += 1 
    if tree.search(line) != None: 
     print "got one!"

這達到了更接近每秒450條目。

來源

2012-11-19 17:03:05

如果你正在尋找**整數**值，你會從輸入行讀取我懷疑非常簡單的數組會更快。即而不是'tree.add（str（result [0]））'do'arrayValues [result [0]] = result [0];'然後代替'if tree.search（line）！= None：'do '如果arrayValues [line]！= null' –

嘗試反向匹配算法：

for digit_sequence in re.findall('[0-9]+', line): 
    if digit_sequence in users: 
     ...

來源

2012-11-19 16:58:28 ecatmur

我是C++的自由職業者，我的客戶通常都是一些慢python/java/.net/etc代碼的創業公司，他們希望它運行得更快。我通常可以使它快100倍。就在最近，我有類似的問題任務：實現以TB爲單位的文本數據搜索500萬個子串。

我測試了幾種算法。對於Aho-Corasick，我使用了開源的http://sourceforge.net/projects/multifast/。這不是最快的算法。最快的是我的算法，我從哈希表和從拉賓 - 卡普搜索算法中提取的一些想法混合在一起。這個簡單的算法快了x5倍，使用的內存比AC少了5倍。平均子串長度是32個字節。所以，AC可能不是這個最快的算法。

來源

2014-02-19 14:14:31

搜索文本以查找長串子列表

回答

相關問題