4

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

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

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

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

6
  • Если поиск идет по началу или концу строки, то индексы очень даже работают например в Оракле. То есть запросы вида like '%text' и like 'text% вполне себе работают по индексам. В дополнение справочники обычно не очень большие, и поиск даже без индексов работает быстро
    – Viktorov
    21 окт 2016 в 19:18
  • @lDrakonl, да. Про это я знаю. Но если искать с середины слова, то индексы уже не работают.
    – iluxa1810
    21 окт 2016 в 19:23
  • 3
    Используйте полнотекстовый поиск. Может быть встроен прямо в субд или быть отдельным приложением. И вообще, кто-то забивает буквы в компьютер с середины слова? Может при этом ещё и в обратном порядке, от середины к началу, потом от конца к середине? Такое тоже надо предусмотреть. Обязательно!
    – Sergey
    21 окт 2016 в 23:29
  • @iluxa1810 все еще зависит от самого справочника. Размер, распределение данных. Не всегда полный скан таблицы хуже доступа по индексу. Возможно дело вообще не в лайках по тексту, а чем то другом.
    – Viktorov
    22 окт 2016 в 7:23
  • 2
    Я бы не ограничивался использованием RDBMS. Почитайте о ElasticSearch (или SOLR) и Hadoop (в качестве платформы)... 22 окт 2016 в 8:18

1 ответ 1

2

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

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

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


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

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


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

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

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

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

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

3
  • N-граммный поиск предназначен для нечеткого поиска (когда нужно избавиться от дублей с опечатками, например, или искать все более или менее похожие варианты). Для точного поиска по справочнику его использование сомнительно.
    – minamoto
    25 окт 2016 в 11:13
  • @minamoto как раз для адресов этот поиск подходит очень неплохо, т. к. топонимы в адресах пользователи частенько вводят с некоторыми отклонениями, на букву-другую. А свой ответ зря стёрли. Понимать, почему решение плохое, тоже полезно. Но дело ваше, разумеется.
    – user181100
    25 окт 2016 в 11:20
  • Про отклонения в адресах на букву-другую есть смешной анекдот: "xxx: все, я приехал, я на ленинградском вокзале xxx: я взял такси, напомни адрес yyy: ул. паперника, дом xx xxx: вот жеж вы москвачи со своим олбанским xxx: коперника улица, коперника xxx: николай коперник, польский ученый, великий астроном, а вы его так, эх, не стыдно? yyy: точно, езжай уже туда"
    – minamoto
    25 окт 2016 в 11:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.