文本文件包含两列-索引号（5个空格）和字符（30个空格）。它按字典顺序排列。我想执行二进制搜索来搜索关键字。
这是使用Python的内置bisect模块实现的一种有趣的方法。
import bisect
import os
class Query(object):
def __init__(self, query, index=5):
self.query = query
self.index = index
def __lt__(self, comparable):
return self.query < comparable[self.index:]
class FileSearcher(object):
def __init__(self, file_pointer, record_size=35):
self.file_pointer = file_pointer
self.file_pointer.seek(0, os.SEEK_END)
self.record_size = record_size + len(os.linesep)
self.num_bytes = self.file_pointer.tell()
self.file_size = (self.num_bytes // self.record_size)
def __len__(self):
return self.file_size
def __getitem__(self, item):
self.file_pointer.seek(item * self.record_size)
return self.file_pointer.read(self.record_size)
if __name__ == '__main__':
with open('data.dat') as file_to_search:
query = raw_input('Query: ')
wrapped_query = Query(query)
searchable_file = FileSearcher(file_to_search)
print "Located @ line: ", bisect.bisect(searchable_file, wrapped_query)
您需要进行二进制搜索吗？如果不是，请尝试将您的平面文件转换为cdb (constant database)。这将使您非常快速地进行哈希查找，以找到给定单词的索引：
import cdb
# convert the corpus file to a constant database one time
db = cdb.cdbmake('corpus.db', 'corpus.db_temp')
for line in open('largecorpus.txt', 'r'):
index, word = line.split()
db.add(word, index)
db.finish()
在单独的脚本中，对它运行查询：
import cdb
db = cdb.init('corpus.db')
db.get('chaos')
12345
如果您需要在文件中找到single关键字：
line_with_keyword = next((line for line in open('file') if keyword in line),None)
if line_with_keyword is not None:
print line_with_keyword # found
要查找多个关键字，您可以将set()用作@kriegar suggested：
def extract_keyword(line):
return line[5:35] # assuming keyword starts on 6 position and has length 30
with open('file') as f:
keywords = set(extract_keyword(line) for line in f) # O(n) creation
if keyword in keywords: # O(1) search
print(keyword)
您可以使用上面的dict()代替set()来保存index信息。
这里是您可以对文本文件进行二进制搜索的方式：
import bisect
lines = open('file').readlines() # O(n) list creation
keywords = map(extract_keyword, lines)
i = bisect.bisect_left(keywords, keyword) # O(log(n)) search
if keyword == keywords[i]:
print(lines[i]) # found
与set()变体相比没有优势。
注意：除第一个变量外，所有变量都将整个文件加载到内存中。 FileSearcher() suggested by @Mahmoud Abdelkader不需要将整个文件加载到内存中。
考虑使用集合而不是二进制搜索来在文件中查找关键字。
设置：
要创建的O（n），要查找的O（1），要插入/删除的O（1）
如果输入文件由空格分隔，则：
FileSearcher()字典：
f = open('file')
keywords = set( (line.strip().split(" ")[1] for line in f.readlines()) )
f.close()
my_word in keywords
<returns True or False>
二进制搜索是：
O（n log n）创建，O（log n）查找
编辑：对于您的5个字符和30个字符，您可以只使用字符串切片
f = open('file')
keywords = dict( [ (pair[1],pair[0]) for pair in [line.strip().split(" ") for line in f.readlines()] ] )
f.close()
keywords[my_word]
<returns index of my_word>
通过重复地将范围一分为二并向前读经过行终止符，很有可能会在效率不高的情况下对具有未知长度记录的已排序文本文件执行二进制搜索。这是我通过在第一个字段中具有2个标题行的数字的csv文件查找外观的方法。给它一个打开的文件，并寻找第一个字段。为您的问题修改它应该很容易。偏移量为零的第一行匹配将失败，因此可能需要特殊设置。在我的情况下，前两行是标题，并且被跳过。
请原谅我下面缺少的精美python。我使用此功能以及类似的功能，直接从Maxmind分发的CSV文件中执行GeoCity Lite纬度和经度计算。
希望这会有所帮助
========================================>
f = open('file')
keywords = set( (line[5:-1] for line in f.readlines()) )
f.close()
myword_ in keywords
or
f = open('file')
keywords = dict( [(line[5:-1],line[:5]) for line in f.readlines()] )
f.close()
keywords[my_word]
我写了一个简单的Python 3.6+包就可以做到这一点。 （有关更多信息，请参见其# See if the input loc is in file
def look1(f,loc):
# Compute filesize of open file sent to us
hi = os.fstat(f.fileno()).st_size
lo=0
lookfor=int(loc)
# print "looking for: ",lookfor
while hi-lo > 1:
# Find midpoint and seek to it
loc = int((hi+lo)/2)
# print " hi = ",hi," lo = ",lo
# print "seek to: ",loc
f.seek(loc)
# Skip to beginning of line
while f.read(1) != '\n':
pass
# Now skip past lines that are headers
while 1:
# read line
line = f.readline()
# print "read_line: ", line
# Crude csv parsing, remove quotes, and split on ,
row=line.replace('"',"")
row=row.split(',')
# Make sure 1st fields is numeric
if row[0].isdigit():
break
s=int(row[0])
if lookfor < s:
# Split into lower half
hi=loc
continue
if lookfor > s:
# Split into higher half
lo=loc
continue
return row # Found
# If not found
return False
页面！）