Как это сделано: префиксный поиск

Мы живем во времена, когда кажется, что все просто и все есть. Нужно сделать масштабируемый проект — используем MongoDB, нужна очередь — вот RabbitMQ, нужно поднять функционал поиска — раз плюнуть: ставим Sphinx, Solr, ElasticSearch (нужное подчеркнуть).

Но здесь лишь доля правды: — при определенном везении можно поставить нужный сервер и все зашевелится. Загвоздка с поиском состоит в том, что пользователи уже порядком привыкли к высокой планке, которую задают «большие ребята», а тот поиск, что поднимется у вас «из коробки», будет явно недотягивать. И если очередь или базу данных вы можете добить железом прежде, чем будете оптимизировать, то поиск железом не добьешь.

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

Мы посмотрим, как с помощью нашего проекта http://indexisto.com сделан поиск на сайте http://maximonline.ru и сравним его с тем, что есть на других сайтах.

Для начала несколько примеров. Возьмем запрос «Битва за Лос Анджелес» и представим, что его напишут неправильно «Лос Анжелес биттва». Как видно, пользователь не знает точно, как пишется имя города, и забыл, как звучит название фильма, а также у него дрогнула рука в конце на слове «битва».

Выберем достойные проекты рунета, в которых есть префиксный поиск, и попробуем поискать там наш запрос:

Проект Правильный запрос Неправильный запрос
afisha.ru 33ec81c7cb6e6b66eb86b16c66d86cac
все ОК
b457e3ef074e9cf0de0f7980bbbd2c17
Не найдено
ivi.ru a4586d49296f2a7793881a3d2d2ee485
все ОК
c5142684bd7e03b39bbec4495be210d8
Не найдено
vk.com 58c7297ec5daa02f037d9047c6c455d0
все ОК
cf2715f39df2a0f74ea85ccd5aa2ef5a
Не найдено
maximonline.ru 20f9e338aaebab27e3404f219b422d52
все ОК
3276adb902950ba3b1fba84dcd640099
все ОК


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

  • Не работает перестановка слов
  • Наблюдаются «скачки». То есть по мере набора искомый фильм то появляется в результатах, то пропадает.
  • Отсутствие нечеткого поиска
  • Не у всех есть морфология

Поехали настраивать

В статье речь будет идти о сервере ElasticSearch, однако эти же подходы можно использовать и при настройке SOLR, так как в итоге все высокоуровневые запросы все равно мапятся на запросы более низкоруровневой библиотеки поиска Lucene. Также не принципиально, делаете ли вы префиксный поиск с помощью ngram токенизаторов или с помощью префиксных запросов (довольно тяжеловесных, так как они мапятся на fuzzy-запросы).

Индексация

При индексации текст проходит через токенизатор и ряд фильтров (морфология, синонимы…). Оригинальное слово в итоге может быть заменено, приведено к нормальной форме или вообще выкинуто. Через какие бы фильтры вы ни прогоняли ваши токены, сохраняйте оригинальное слово в той же позиции, что и измененное/замененное. Что может случиться, если не сохранить оригинальное слово, показанно на картинке:

ec7cc2273c63a5b540ecd3896b3ebc59

Как видите, фильтр морфологии меняет слово (приводит к нормальной форме). В обычном поиске это работает хорошо, так как слово из запроса, который ввел пользователь, тоже будет приведено к нормальной форме. Но что делать, пока пользователь ввел только половину слова (префиксный поиск)? Сохраняем оригинальный токен в индексе!

2091c5e05c76dd161e5daff1a2085d38

У нас, кстати, возникли проблемы в стандартных плагинах Lucene, и мы сделали свои, которые лучше работают с позициями токенов в документе и сохранением оригинального слова. О том, какие проблемы вас могут поджидать, можно почитать, например, здесь:Lucene’s TokenStreams are actually graphs! 

Анализаторы запроса

Не используйте анализаторы, которые могут вам «подчистить» запрос, например, фильтр стоп-слов, который удаляет междометия и частицы. Вот пример:
95ce8660329d8c8fb5cf09fdaf2ea85e

Как видите, «а» это стоп-слово, и анализатор запроса ее удалил. На практике это означает, что будет «скачок», то есть человек набрал «Хаунита А» и видит документ по запросу Хуанита (без А). Если у нас много Хуанит в выдаче, то нет никакой гарантии, что нужная нам будет сверху.
Для того, чтобы это побороть, убираем фильтр стоп-слов из запроса:
87b950e626f1d46e834e09e7c7e37aca

Запрос

Не пытайтесь сделать все сразу одним путанным гигантским запросом. Разбейте задачу на подзадачи. Существуют булевы и dismax-запросы, которые помогут вам склеить результаты работы нескольких мелких запросов в один. Используйте boost в небольших запросах, чтобы, к примеру, увеличить вес точного совпадения в title страницы по сравнению с совпадением в body страницы. Примерно вот так:

{
  "query":{
    "bool" : {
      "should" : [
        {
          "custom_boost_factor": {
            "query":{
              "match":{
                ....
              }
            },
            "boost_factor": 100
          }
        },
        {
          "custom_boost_factor": {
            "query":{
              "match":{
                ....
                }
              }
            },
            "boost_factor": 10
          }
        },
        .....
      ]
    }
  }
}

Точное совпадение фразы в заголовке статьи

Итак, наш поисковый запрос состоит из кучки маленьких запросов с разными boost-факторами. Boost-фактор — это множитель релевантности, который применяется, когда базовая текстовая релевантность уже посчитана.

Сначала у нас идет поиск на точное совпадение фразы в заголовке статьи (или title страницы). Точное совпадение означает, что мы не используем префикс. Например, запрос«КАК» выведет первыми статьи «Как правильно…», а не статью «Выращиваем кактус». Документы, найденные по такому запросу, получают буст, к примеру, 10000.

Префиксное совпадение фразы в заголовке статьи

Далее идет запрос на префиксное совпадние фарзы. Точные совпадения слова «КАК» нам уже нашел первый запрос, теперь время поискать «кактусы». Эти документы будут идти ниже точных совпадений за счет меньшего буста.
Мы также здесь используем параметр slop, который говорит, что слова в фразе могут отстоять друг от друга на несколько позиций вперед или назад. Многие забывают про этот параметр, а по умолчанию префиксный поиск ищет только вперед.

Вот какая выдача получается на текущий момент:

0c0d412340dd1c2810d4f17da7e16e40

Первыми идут точные совпадения, вторыми — префиксные.

Совпадения в теле статьи — полное и префиксное

Совпадения в заголовке мы нашли и сделали им приличный буст. Время перейти к самому телу статьи. В первую очередь мы опять ищем точное совпадение, и с меньшим boost-фактором префиксные совпадения.

Таким образом, совпадения в заголовке будут первыми в выдаче, а совпадения в теле статьи — ниже. Встает вопрос: не отдать ли подобную сортировку на откуп текстовой релевантности? Ведь стандартные алгоритмы учитывают длину текста, в котором найдено совпадение: чем короче текст, тем выше релевантность. Однако практика показала, что при префиксном поиске в теле статьи будет очень много совпадений. Представьте, вы набрали 1-2 буквы, а в теле статьи будет уже 200-300 совпадений, и, несмотря на длину текста, они перебьют релевантность совпадений в заголовке.

Нечеткие совпадения в заголовке или теле статьи

Последним (за счет буста) идет нечеткий поиск. Нечеткий поиск прощает некоторые опечатки в поисковом запросе, введенном пользователем. Внутри запроса используетсяLevenshtein distance. Нечеткий запрос имеет несколько настроек, которые выступают в качестве параметров к алгоритму, а также есть возможность указать минимальное необходимое совпадение префикса.

"custom_boost_factor": {
            "query":{
              "multi_match":{
                "query":"${q}",
                "fuzziness":0.005,
                "prefix_length" : 2,
                "operator":"and",
                "max_expansions":999,
                "fields":[
                  "article_name",
                  "article_body"
                ]
              }
            },
            "boost_factor": 1
          }
        }

Совпадения, найденные нечетким поиском, идут в самом низу за счет минимального boost-фактора.

Что в итоге

На картинке видно, как выстроились наши результаты в зависимости от совпадений:

  • в заголовке точные
  • в заголовке по префиксу
  • в теле статьи точные
  • в теле статьи по префиксу
  • в заголовке и теле статьи нечеткие (с опечатками)

2751ee2eecba1e3e8bdd2d75d28b74ba

Бонус-трек для тех, кто осилил статью

Мы собираем всю статистику поисковых запросов, клики по результатам выдачи, поиски без переходов, поиски с пустым результатом.
Интересно, что на maximonline.ru поиск довольно востребованный функционал, а 90% поисковых запросов это имена девушек. Здесь можно получить очень интересные данные :)

Итак, самые искомые читателями Maxim девушки в обратном порядке! Данные за ноябрь 2013.

5. Анна Семенович (телеведущая)
8e9090db8e9b1b2b4b9ef500efc60fec

4. Вера Брежнева (певица)
a200e2fd88969cb14397dc0a329cc3ca

3. Анна Хилькевич (актриса)
6e7d8630478703421023ccc9f68756dd

2. Мария Горбань (актриса)
289c6e60c61a3a35a2e5651bf254858b

1. Екатерина Волкова (актриса)
a1c0abde43edad735842eec9a892c923