Я ищу алгоритм и схему хранения для сопоставления строк со словарем, превышающим объем памяти.
Моя первоначальная попытка, вдохновленная https://swtch.com/~rsc/regexp/regexp4.html,, заключалась в том, чтобы хранить тригамы каждого словаНапример, в словаре слово apple разбито на $ap, app, ppl, ple и le$ в индексное время.Все эти триграммы связаны со словом, из которого они произошли.
Затем я запрашиваю время, я делаю то же самое для входной строки, которая должна совпадать.Я просматриваю каждую из этих триграмм в базе данных и сохраняю слова-кандидаты в сопоставлении, связанные с количеством совпадающих в них триграмм.Затем я приступаю к вычислению расстояния Левенштейна между каждым кандидатом и применяю следующую формулу:
score(query, candidate) = common_trigram_number(query, candidate) - abs(levenshtein(query, candidate))
В этом подходе есть две проблемы, во-первых, выбор кандидата слишком широк.Во-вторых, расстояние Левенштейна слишком медленно для вычисления.
Исправление первого может сделать второй бесполезным для оптимизации.
Я думал о другом подходе, во время индекса, вместо сохранения триграмм, ябудет хранить слова (возможно, связанные с частотой).Во время запроса я мог искать последовательные префиксы строки query и оценку, используя левенштейн и частоту.
В частности, я не ищу алгоритм, который дает мне строки на расстоянии 1, 2 и т. Д.... Я хотел бы просто получить постраничный список более или менее релевантных слов из словаря.Фактический выбор сделан пользователем.
Также должна быть возможность представить его в виде упорядоченного хранилища значений ключей, такого как rocksdb или wiredtiger.