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 that you have read and understand our privacy policy and code of conduct.

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