如何在Python中的超大型數據集上執行高效的成員資格搜索

Question

我的問題關於列表/集成員的搜索效率。我想比較一小組基因組kmers（核苷酸串）到一個非常大的kmers列表來測試成員資格。由於該算法是爲大型真核生物基因組設計的，因此該大型列表可以達到GB範圍的列表。

較小的列表只會在KB範圍內，但可能有數百萬個這樣的列表！顯然，我迫切需要一種有效的方式來搜索這個大名單。

根據我所看到的類似問題，我不應該把大列表轉換成一個集合，因爲它會花費太多的內存。我一直在使用較小的列表作爲集合，但它並不能爲我節省大量的時間。

最後，一旦腳本完成，它將被設計爲運行在通常用於大型基因組算法的大型內存機器上。

謝謝

Answer 1

BioPython有出於這樣的目的特里結構的實現。

from Bio import trie 
tr = trie.trie() 

Answer 2

一個trie可能爲基因組學的一個很好的數據結構，但你也可以考慮BloomFilter（概率數據結構，可提供驚人的有效空間集合成員資格測試 - 這是怎麼了一些拼寫檢查器例如存儲有效詞的大字典）。