Как работают полнотекстовые подсказки в поиске 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 на Хабрахабре.