Лучший способ сделать поиск нечеткого ключа в Python?

Question

У меня есть проблема, когда мне нужно сделать нечеткий поиск в хэш-карте, то есть вернуть значение, соответствующее ключу, который больше всего напоминает запрос, в моем случае измеренный расстоянием Левенштейна.

Мой текущий подход состоит в том, чтобы подкласс dict с помощью специального метода поиска, который вычисляет расстояние Левенштейна по всем ключам, а затем возвращает значение ключа с наименьшей оценкой. В основном это:

import Levenshtein

class FuzzyLookupDict(dict):

    def fuzzy_lookup(self, query):
        levs = [(key, Levenshtein.ratio(query, key)) for key in self.keys()]
        key, score = max(levs, key=lambda lev: lev[1])
        return self.get(key)

Это хороший подход или есть лучшее решение, о котором я не думал?

Answer 1

Эта проблема обычно решается с помощью автоматов Левенштейна. Автомат Левенштейна для строки w и числа n является автоматом конечных состояний, который может распознавать множество всех строк, у которых расстояние Левенштейна от w не больше n.

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

Сообщение в блоге Жюля Джейкоба Автоматы Левенштейна могут быть простыми и быстрыми, что является хорошей отправной точкой, а "Чертовы крутые алгоритмы" Ника Джонсона : "Автоматы Левенштейна" - более глубокое введение.

Вы можете найти некоторые реализации Python на Github, например https://github.com/antoinewdg/pyffs.