Python - быстрый поиск файлов

Question

У меня есть файл с большим (0,5-1,5 миллиона) числом строк, каждая из которых является именем файла (длина составляет около 50-100 символов).Мне нужен быстрый поиск по этим строкам по заданному запросу.Теперь мой код выглядит следующим образом:

def similarity(haystack, needle):
    words = re.findall(r'\w+', haystack.lower()) # replacing by split with separators reduces time by about 4 seconds

    for word in words:
        if word == needle:
            return 10

    for word in words:
        if word.startswith(needle):
            return 10 ** (len(needle) / len(word))

    if needle in haystack:
        return 1

    return 0

def search(text):
    text = text.lower()
    lines = [(similarity(x, text), x) for x in lines]
    return [x[1] for x in sorted(lines, reverse = True)[:15]]

Он работает около 15 секунд с файлом примера на моем ПК (почти все время работает в функции similarity()), и я хочу, чтобы он запускался почти сразу, впару секунд.Как это можно сделать?

Я думаю, что индексация может помочь, но понятия не имею о ее возможной структуре.И, если возможно, я хочу, чтобы поиск был «более размытым» - например, с N-граммами или чем-то в этом роде.Но сейчас основной проблемой является скорость.

UPD:

Один и тот же lines выполняется многократный поиск.

needleвсегда одно слово.

«Более нечеткий» означает, что он должен находить строки, даже если needle немного опечатан.

Answer 1

1. Эта строка ничего не делает:

   10 ** (len(t) / len(word))

2. Вам нужны лучшие имена переменных, на данный момент неясно, что "s"и "т" есть.Однобуквенные имена переменных допустимы только в математике и в качестве переменных цикла.Это то, что вы ищете, или это то, что вы ищете?Используемая в настоящее время функция не имеет для меня особого смысла.

3. Поскольку вы сопоставляете только первое совпадение с любым объектом поиска, в некоторых случаях расщепление не имеет смысла, поэтому выВозможно, можно переместить разделение в последнюю очередь, но это зависит от того, что вы на самом деле ищете, что неясно (см. 2).

Обновление: чтобы действительно добиться максимальной производительности из этого,вам нужно профилировать и тестировать и профилировать и тестировать.Но я бы предложил это как первый старт:

def similarity(haystack, needle):

    if needle not in haystack:
        return 0

    words = haystack.lower().split()

    if needle in words:
        return 10

    for word in words:
        if word.startswith(needle):
            return 10 ** (len(needle) / len(word))

    return 1

Answer 2

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

Принимая во внимание вашу логику.Вы можете использовать это.

import shelve
import os

PERSISTENT_DICT_FILENAME = "my_persistent_dict"

def create_a_persitant_dict(haystack_filename):
    pd = shelve.open(PERSISTENT_DICT_FILENAME)
    f = open(haystack_filename)
    for filename in f:
        filename_len = len(filename) 
        filename = filename.lower()
        for i in range(1,filename_len):
            partial_filename = filename[:i]
                calculation = 10 ** ((len(partial_filename)*1.0)/filename_len)
                if pd.has_key(partial_filename):
                        if calculation > pd[partial_filename]:
                            pd[partial_filename] = calculation
                else:
                    pd[partial_filename] = calculation

    pd.close()

def search_string(needle):
    needle = needle.lower()
    pd = shelve.open(PERSISTENT_DICT_FILENAME)
    if pd.has_key(needle):
        return_val = pd[needle]
    else:
        return_val = 0
    pd.close()
    return return_val

if __name__ == "__main__":
    #create_a_persitant_dict("a_large_file.txt")
    needle = raw_input("Enter the string to search")
    print search_string(needle)

Объяснение:

create_a_persitant_dict(haystack_filename)

Создает постоянный словарь, читающий большой файл.Ключ - это строка, найденная в файле (Пример: если в файле есть строка «World.txt», то ключи будут «w», «wo», «wor», «worl» ... и т. Д.,а значение - это расчет (10 ** и т. д.) для каждого ключа.

Это только одна дорогостоящая операция, но идея состоит в том, чтобы ускорить поиск.

search_string(needle)

Функция будет искать строку в постоянном словаре и давать вам вычисления, основанные на вашей логике. Это будет быстрее, чем итерация каждый раз.