Как строятся справочные системы?

#sql #база_данных #алгоритм #словари

Имеется какой-то справочник на N адресов к которому обращается многопользователей.

Казалось бы, размещай справочник в СУБД и все...

Но, обычно, справочные системы предлагают поиск по частичному совпадению => от пользователей
идет множество LIKE запросов, которые СУБД не может оптимизировать так как индексы
не работают.

Вот как выходят из такой ситуации? Неужели все решает покупкой более мощного железа?
    

Ответы

Ответ 1

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

Такой подход позволяет обнаруживать мелкие опечатки в словах или находить слова только
по кусочку сколько-нибудь существенной (от N+1) длины.

Реализаций достаточно, есть выбор.



Есть N-граммный токенизатор в ElasticSearch. Есть и в Apache Solr. В Sphinx N-граммный
поиск можно включить (утверждается, что он имеет смысл для корейского, японского и
китайского, где беда с разделением на слова).

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



А теперь что-нибудь менее обычное.

Для PostgreSQL имеется модуль триграммного поиска (pg_trgm). Как можно догадаться,
это N-граммный поиск, где N=3.

Для него практически необходим отдельный индекс GIN или GiST, составленный по классу
операторов из этого модуля. GIN довольно большой по объёму, не слишком быстро обновляется,
но быстр для поиска; тогда как GiST компактнее и быстрее обновляется, но может давать
ложные совпадения. Поэтому для редко обновляемых данных GIN оптимальнее.

Это неплохой вариант, если у вас уже используется PostgreSQL, он не особенно нагружен
(или есть возможность это обеспечить) и от поиска не нужна большая интеллектуальность.

У него есть и реализация полнотекстового поиска, но это уже не относится к N-граммному.