Самый быстрый метод текстового поиска в большом текстовом файле

Question

Я делаю текстовый поиск в довольно большом текстовом файле (100 тыс. Строк, 7 месяцев). Текст не такой большой, но мне нужно много поисков.Я хочу найти целевую строку и вернуть строку, где она появляется.Мой текстовый файл отформатирован так, что цель может отображаться только в одной строке.

Какой самый эффективный способ?Я делаю много поисков, поэтому хочу улучшить скорость.Вот мой код прямо сейчас:

def lookup_line(target):
    #returns line of the target, or None if doesnt exist
    line=None
    dir=os.path.dirname(__file__)
    path=dir+'/file.txt'
    file=open(path,'r')
    while line==None:
        l=file.readline()
        l=unicode(l,'utf-8')
        if target in l:
            break
        if l=='': break #happens at end of file, then stop loop
    line=l
    if line=='':line=None #end of file, nothing has been found
    file.close()
    return line

Я использую этот код Python для приложения Google Appengine.

Спасибо!

Answer 1

1. Загрузка всего текста в оперативную память одновременно. Не читайте построчно.
2. Поиск шаблона в блобе. Если вы найдете его, используйте text.count('\n',0,pos), чтобы получить номер строки.
3. Если вам не нужен номер строки, найдите предыдущий и следующий EOL, чтобы вырезать строку из текста.

Цикл в Python медленный. Поиск строк очень быстрый. Если вам нужно найти несколько строк, используйте регулярные выражения.

Если этого недостаточно, используйте внешнюю программу, например grep.

Answer 2

Если вы просматриваете один и тот же текстовый файл снова и снова, рассмотрите возможность индексации файла. Например, создайте словарь, который сопоставляет каждое слово с какими строками. Создание займет некоторое время, но затем будет выполнен поиск O (1).

Если вы ищете разные текстовые файлы или не можете индексировать файл по какой-либо причине, вы, вероятно, не получите более быстрый алгоритм KMP .

РЕДАКТИРОВАТЬ: описанный мной индекс будет работать только для поиска по одному слову, а не по нескольким словам. Если вы хотите выполнить поиск по нескольким словам (любой строке), вы, вероятно, не сможете их проиндексировать.

Answer 3

Во-первых, не нужно явно декодировать байты.

from io import open

Во-вторых, рассмотрим такие вещи.

with open(path,'r',encoding='UTF-8') as src:
    found= None
    for line in src:
        if len(line) == 0: break #happens at end of file, then stop loop
        if target in line:
            found= line
            break
    return found

Это можно немного упростить, чтобы использовать return None или return line вместо break.Он должен работать быстрее, но вносить изменения несколько сложнее, если есть несколько возвратов.