Python二進制詞典搜索

我有一個巨大的.txt.gz文件，每個行有大約800kb的單詞和評分值，格式化爲「值詞」，並按單詞排序。查找給定單詞的價值最快的方法是什麼？Python二進制詞典搜索

我可以利用讀取文件：

import gzip 

f = gzip.open('somefile.txt.gz', 'rb') 
file_content = f.read()

請問最快的方法是二進制搜索某種？

樣本數據：

0.090909 CHEVRE＃N＃1

0.058824山形＃N＃1

0.071429山形＃N＃2

0.071429鼷鹿科＃N＃1

0.166667 chewa＃N＃1

來源

2013-05-14 user759885

你只需要查找一個詞的價值？如果是這樣，在讀取文件時間複雜度O（n）時，可能最快就是掃描該單詞。否則，它將是二進制搜索（O（log n） - 你的情況需要大約15個比較）和一個字典（O（1）它是一個哈希表）之間的競爭。如果這很關鍵，那麼您需要計時兩種方法。 – Bull

我想不出用二進制搜索的方式做到這一點，而無需將所有數據加載到另一個數據結構中。這真的取決於你會仰望多少。如果你不必做很多查找，那麼線性搜索就不會太糟糕。如果你不想加載像Dictionary這樣的新數據結構，那麼線性搜索是我能想到的唯一可行的選擇。 – minhaz1

我從一個基本的函數開始，打開文件併線性讀取，直到找到這個單詞。之後，你將不得不調查通過壓縮文件搜索;例如，http://stackoverflow.com/questions/429987/compression-formats-with-good-support-for-random-access-within-archives – dan

二進制搜索將做這樣的事情的有效方法，但你還是得從文本（只是一堆字節，畢竟）到像一個列表中的一些其他數據結構的數據移動。如果你有一個壽命短，或根本沒有長期記憶的限制程序，它會（可能）會更快整個事情只是加載到一個Python dict在啓動時（或當爲宜）：

# This may not work exactly right for your file format, but you get the idea. 
lookup = {} 
for line in f: 
    if line: 
     value, key = line.trim().split(): 
     lookup[key] = value

然後，您可以訪問使用Python的內置詞典，這是又好又快它：

def get_value(word): 
    return lookup.get(word)

編輯

如果您唯一的選擇是讀取每個單詞的整個文件，並且您正在搜索多個單詞，那麼通過實施一個聰明的搜索算法，您節省的時間可能會比您花費的時間稍微少一些並反覆閱讀文件。你真正想要的是一個數據庫，它可以快速處理這類事情。也就是說，鑑於這些參數，我可能會做這樣的事，如果我不得不使用文件系統：

import bisect 

# Define searchable (word, value) tuples for every word in the file. 
# I'm assuming your files are sorted, but if not, sort this list (SLOW!!) 
words = [(w[1], w[0]) for w in (line.strip().split() for line in f if line)] 

# Binary search for the word and return its associated value. 
def get_value(word): 
    idx = bisect.bisect_left(words, (word,None)) # Tuples compare element-wise 
    if idx != len(words) and words[idx][0] == word: 
     return words[idx][1] 
    raise ValueError('word not found')

最後，我注意到你正在使用gzip壓縮的文件，這是如果儲存空間感是一個問題，但它會讓您的流程更加緩慢。我再一次建議一個數據庫。無論如何，我不知道你是否在這裏遇到麻煩，但爲防萬一，閱讀gzipped文件並不比讀取普通文件更「困難」。只要看看gzip module。基本上，gzip文件就像普通文件一樣工作，所以你仍然可以編寫for line in file等等。

來源

2013-05-14 23:12:39

我有成千上萬的這些大文本文件。（每個單詞將一個單詞連接到每個其他單詞並給出一個相關性分數）。它們不可能全部加載到python字典中。我正在尋找最快的方法來找到包含我想要讀取分數值的單詞的正確行。我會認爲二分搜索會比逐行搜索更好，所以我正在尋找一種方法。但我不知道是否可以使用平分，因爲值排在前面。 – user759885

這聽起來像你有大量的數據。你會考慮加載到數據庫引擎，如MySQL？ – Miles

@ user759885那麼有80GB的數據，不只是800kB？如果你想得到一個很好的答案，你需要提供更多關於你想要做什麼的信息。 – Bull

Python二進制詞典搜索

回答

相關問題