Как работают полнотекстовые подсказки в поиске Mail.ru

Формирование поисковых подсказок у всех поисковиков в целом устроено одинаково: чем больше спрашивают какой-то запрос, тем выше он будет среди подсказок. Но некоторые моменты - различаются.

Общие требования к поисковым подсказкам:

1. Поиск по подсказкам должен быть полнотекстовым, то есть должен уметь искать по текстам подсказок все слова из пользовательского запроса в любой их последовательности. Например, если пользователь ввел запрос «смотреть», то он должен увидеть все варианты подсказок с этим словом, находящиеся в базе, несмотря на то, что слово «смотреть» находится в разных местах этих подсказок.

2. Запрос пользователя может быть неполным, пока он набирает его на клавиатуре. Поэтому поиск должен искать подсказки не по словам, а по их префиксам - например, «смотр».

3. Скорость реакции крайне важна, поэтому поиск должен выдавать подсказки за считанные миллисекунды.

4. Наконец, сервис поисковых подсказок должен быть надежной системой, работающей в режиме 24/7/365.

Специалисты поиска Mail.ru Group рассмотрели известные подходы к решению задачи поисковых подсказок и рассказали, как научились делать их полнотекстовыми и быстрыми, но при этом нежадными к ресурсам.

В основе полнотекстового поиска по подсказкам лежит классический подход к реализации полнотекстового поиска общего назначения, на котором базируется любой современный веб-поисковик. Полнотекстовый поиск в общем случае ведется среди так называемых документов, то есть текстов, внутри которых ищутся слова из запроса пользователя. Суть же алгоритма сводится к двум простым структурам данных, прямому и обратному индексам:

  • прямой индекс — список документов, в котором можно найти этот документ по его id. Иными словами, прямой индекс — это массив строк (вектор документов), где id документа — это его индекс
  • обратный индекс — список слов, которые были извлечены из всех документов. За каждым словом закреплен список отсортированных id документов (posting list), в которых это слово встретилось.

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

1. В обратном индексе: по словам из запроса найти списки id тех документов, где эти слова встречались. Получить пересечение этих списков — результирующий список id документов, где встречаются все слова из запроса.

2. В прямом индексе: по полученным id найти исходные документы и «отдать» их пользователю.

С подробным описанием алгоритма работы поисковых подсказок и механизма кэширования, а также c рабочим примером на C++, реализующим описанный в статье алгоритм, можно ознакомиться в блоге Mail.ru на Хабрахабре.

subscribe

Подпишитесь на рассылку SearchEngines

— Статьи мировых экспертов

— Аналитические обзоры

— Важные новости

— Горячие темы с нашего форума

MainLink: 13.6% сайтов находятся под АГС

Как известно, 8 сентября 2015 года представители поисковой системы Яндекс сообщили об обновлении легендарного фильтра АГС

Европейские издатели требуют расширения «налога на Google» на весь ЕС

Немецкий издательский концерн Axel Springer возглавил инициативу, призывающую Еврокомиссию к реформе европейского законодательства об авторском праве, сообщает Politico

Bing обновил поисковый алгоритм?

Специалисты отрасли заметили признаки возможного обновления поискового алгоритма Bing. На минувших выходных некоторые вебмастера наблюдали рост трафика из Bing от 10% до 75%

В конструкторе Яндекс.Карт появилась поддержка редактирования «Моих карт»

Команда Яндекс.Карт сообщила об обновлении Конструктора карт, в нем появилась поддержка редактирования «Моих карт», созданных в веб-версии Яндекс.Карт

Google не советует использовать общеизвестные факты в контент-наполнении сайта

На днях инженер отдела качества поиска Google Гэри Илш (Gary Illyes) заявил, что использовать общеизвестные факты в контент-наполнении сайта – не лучшая идея

Как получать качественные ссылки из Google+ для продвигаемых коммерческих проектов

Вопрос получения качественных ссылок из социальных сетей для продвигаемых коммерческих проектов сейчас волнует многих