什麼是一個很好的數據結構，用於很長的字符串列表？

我有一個包含每行一個句子一個非常大的文件（80 GB）。我想搜索一個用戶給定的字符串來匹配這個文件中的匹配項（空格，連字符，大小寫忽略）。什麼是一個很好的數據結構，用於很長的字符串列表？

現在我有文件作爲文本，我正在使用grep，但它需要很多時間。什麼可能是更好的解決方案？

applachian 
rocky mountains 
andes 
sierra nevada 
long mountain ranges of the world

搜索查詢的例子：

的文本文件的內容示例

rocky (no match) 
sierra nevada (match found)

來源

2017-04-26 user110327

你要買什麼呢？是「單詞」還是「字母」或「短語」？ –

你關心文件中的句子排序嗎？ –

下一個：你在做這一次嗎？數百次循環？爲了響應網絡請求？ –

基於您的評論，你正在尋找完整的句子：

建立一個前綴索引。

排序文件。接下來，處理您的文件一次。計算將搜索減少到1000個句子所需的前綴長度。也就是說，你需要在給定句子的大約1000個句子中得到多少個前綴字符。

例如道：「」可能是英文常見的首發字。但是「快速」可能足以讓人接近，因爲「q」是低頻的，就像「快速的棕色狐狸......等等」

做到這一點的一種方法是將所有前綴長達一定的長度（比如40）放入Collections.counter中。找到每個長度的最大數量，然後選擇你的長度，使得最大值爲< = 1000。可能還有其他方法。 ;-)

現在，處理文件中的第二次。構建一個單獨的索引文件，由前綴長度（在文件頭中），前綴和偏移量組成。所有以前綴K開頭的句子都從偏移量V開始。由於文件已排序，索引也將被排序。

您的程序可以將索引讀入內存，打開文件並開始處理搜索。對於每個搜索，切斷前綴，在索引中查找，尋找文件偏移量，並掃描匹配。

來源

2017-04-26 16:49:48

您可以通過將句子映射到散列來構建可分片數據庫，然後您可以在潛在位置查找數據。

from collections import defaultdict 
from cStringIO import StringIO 

DATA = """applachian 
rocky mountains 
andes 
sierra nevada 
long mountain ranges of the world""" 


def normalize(sentence): 
    return "".join(sentence.lower().strip()) 


def create_db(inf): 
    db = defaultdict(list) 
    offset = 0 
    for line in inf: 
     l = len(line) 
     db[hash(normalize(line))].append((offset, l)) 
     offset += l 
    return db 


def main(): 
    db = create_db(StringIO(DATA)) 
    # save this db, and in a different script, load it to retrieve: 
    for needle in ["rocky", "sierra nevada"]: 
     key = hash(normalize(needle)) 
     for offset, length in db.get(key, []): 
      print "possibly found at", offset, length 


if __name__ == '__main__': 
    main()

這證明了主意：你建立一個數據庫（店作爲例如泡菜）所有標準化的搜索鍵映射到的位置，這些地方被發現。然後，您可以快速檢索偏移和長度，並在實際文件中尋找該位置，從而進行基於==的比較。

來源

2017-04-26 16:52:04 deets

什麼是一個很好的數據結構，用於很長的字符串列表？

回答

相關問題