Как выполнить бинарный поиск по текстовому файлу для поиска по ключевому слову в python?

Question

Текстовый файл содержит два столбца - порядковый номер (5 пробелов) и символы (30 пробелов).Расположен в лексикографическом порядке.Я хочу выполнить бинарный поиск для поиска по ключевому слову.

Answer 1

Вот интересный способ сделать это с помощью встроенного в 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)

Answer 2

Вам нужно сделать бинарный поиск? Если нет, попробуйте преобразовать ваш плоский файл в cdb (постоянная база данных) . Это даст вам очень быстрый поиск хеша, чтобы найти индекс для данного слова:

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

Answer 3

Если вам нужно найти ключевое слово 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 .:

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(), предложенный @Mahmoud Abdelkader не требуется загружать весь файл в память.

Answer 4

Вполне возможно, с небольшой потерей эффективности, выполнить бинарный поиск по отсортированному текстовому файлу с записями неизвестной длины, многократно разделяя диапазон и читая вперед после разделителя строки.Вот что я делаю, чтобы искать в CSV-файле с 2 строками заголовка для числа в первом поле.Дайте ему открытый файл и первое поле для поиска.Это должно быть довольно легко изменить для вашей проблемы.Совпадение в самой первой строке со смещением ноль не удастся, поэтому может потребоваться специальный случай.В моих обстоятельствах первые 2 строки являются заголовками и пропускаются.

Прошу прощения за отсутствие полированного питона ниже.Я использую эту и аналогичную функцию для вычисления широты и долготы GeoCity Lite непосредственно из CSV-файлов, распространяемых Maxmind.

Надеюсь, это поможет

========================================

# 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

Answer 5

Попробуйте использовать набор вместо двоичного поиска для поиска ключевого слова в вашем файле.

Set:

O (n) для создания, O (1) для поиска, O (1) для вставки / удаления

Если ваш входной файл разделен пробелом, то:

f = open('file')
keywords = set( (line.strip().split(" ")[1] for line in f.readlines()) )
f.close()    

my_word in keywords
<returns True or False>

Словарь:

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>

Двоичный поиск:

O (n log n) create, O (log n) lookup

edit: для вашего случая 5 символов и 30 символов вы можете просто использовать нарезку строк

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]