Алгоритм нечеткого поиска с фильтрацией

#алгоритм #нечеткий_поиск

Ищу решение для максимально быстрого нечеткого поиска по заранее известному множеству
сущностей (например, по географическим объектам). Классические алгоритмы (префиксный
бор, суффиксный автомат, автомат Левенштейна) сами по себе подходят, но ни один из
них (вполне ожидаемо) не предполагает дополнительной фильтрации (в случае с примером
по географическим объектам запрос "Площадь Ленина" может иметь необходимость быть отфильтрованным
по типу "станция метро" и региону "Санкт-Петербург"). Строить автомат для каждого поиска,
конечно, плохой вариант; поиск по единому общему автомату может дать чересчур большой
результат (запрос "Ленина" в этом случае выведет миллиард топонимов с Лениным по всей
России). Сам язык позволяет минимизировать эффект от раздутого результата (java / streaming
api), но хотелось бы решить чисто решить задачу изначально.

Есть ли какие-то известные решения для подобной задачи?
    

Ответы

Ответ 1

Почему этот вопрос - плохой

Я писал этот вопрос на знатно несвежую голову, и по-хорошему его вообще не должно
было возникнуть. То, что алгоритмы выполняют одну-единственную задачу - это их предназначение,
если по выходу из алгоритма получается большой объем данных - это не проблема алгоритма,
а алгоритм, который одновременно ищет и фильтрует - это нонсенс, это два разных алгоритма
(один из которых тривиален), соединенные в одной имплементации. Поиск по содержимому
не имеет ничего общего с дополнительными атрибутами, и если вы строите в своем приложении
автомат имени N, то он знать не должен, есть ли у того, что он ищет дополнительные
атрибуты - он просто должен возвращать дженерик, и всё.

Как правильно сделать

Именно так, как я написал под флагом "мне не нравится". Наивный способ предполагает
либо возврат большой коллекции, которая затем фильтруется, либо встраивание фильтра
прямо в движок поисковика (это можно сделать приемлимо с помощью интерфейсов, но вообще
идея отвратительная), либо возврат результата в виде итератора (и это, пожалуй, самая
лучшая из пришедших мне в голову наивных идей). Идея со Stream на самом деле является
околоидеальной - благодаря возможностям языка можно превратить просто итератор в поток,
который будет фильтроваться на лету, и тем самым избавиться как от сложных конструкций
с итератором, так и встроить фильтр практически у самого выхода из поискового алгоритма,
не устраивая драматичное вторжение в поисковый движок.

Подытоживая - лучше всего, если поисковой движок возвращает итератор или поток данных
(если язык имеет такие возможности) - это позволит как отфильтровать результаты на
ранней стадии (до того, как они коллекцией займут область памяти), так и галантно организовать
архитектуру без излишней боли.