Хабрахабр

История одного запроса

image

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

В статье я расскажу, как команда Поиска 2ГИС делает всё возможное для того, чтобы жизнь в городах была удобнее и комфортнее для пользователей.
Важно понимать, что текст поискового запроса — лишь верхушка айсберга, малая часть того, с чем непосредственно взаимодействует пользователь. Что стоит за запросом «поесть на Курской» и как он обрабатывается, чтобы найти именно то, что нужно вам? В них входит персонализированная информация о местоположении пользователя, участке карты, который он видит, набор записей из его избранного и информация о режимах поиска. Сам поисковый запрос, помимо текста, содержит множество других данных. Данные — залог успеха хорошего поискового функционала. Например, поиск по карте или в здании, а может и поиск проезда.

Более того, сам алгоритм поиска в 2ГИС мы называем структурным поиском, потому что он заточен под эффективный и быстрый поиск в наших структурированных данных. Мы уделяем большое внимание нашим данным и их структуре. Не буду углубляться в детали, скажу лишь, что данные организованы так, чтобы быть достаточно простыми в обработке, хорошо сжимались, а главное позволяют нам быстро их обрабатывать даже на мобильных устройствах. Мы особым образом подготавливаем поисковый индекс и данные, из которых он строится.

Этой особенности мы уделяем большое внимание — постоянно сжимаем поисковый индекс, оцениваем быстродействие на всевозможных платформах и ускоряем функционал там, где специфичные поисковые кейсы превышают установленный лимит времени. Более того, поиск умеет работать офлайн, а потому предъявляет особые требования к быстродействию и объёму поискового индекса. К слову, можем похвастаться тем, что рядовой поисковый запрос в 2ГИС на мобильном устройстве выполняется быстрее, чем приложение рисует выпадающий список по результатам.

В качестве примера возьмём упомянутый запрос «поесть на Курской». Ниже я приоткрою завесу тайны, покрывающей магию нашего поиска. Итак, поехали! Рассмотрим этапы его обработки и что происходит на каждом из них.

Этап 1. Парсинг

Входные параметры: запрос «поесть на Курской»

Это важно, потому что после парсинга мы сможем работать не с текстом запроса, а с набором токенов, из которых он состоит. Прежде всего, нам необходимо провести парсинг текста запроса. В нашем случае мы получим набор из трёх токенов: «поесть», «на», «курской». Токены — это отдельные слова запроса. И порой всё бывает не так очевидно: например, в запросах «wi-fi» или «2-я» мы должны понимать, что обрабатывать такие сочетания следует целиком. Казалось бы, всё просто, но дьявол в мелочах.

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

Этап 2. Словарный поиск

Входные параметры: токены «поесть», «на», «курской»

image

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

Узлы в нём — это буквы, а точнее — символы. Словарный поиск мы представляем как алгоритм анализа словаря, представленного в виде графа. Результатом обхода нашего графа-словаря является множество словоформ, которые мы можем получить на основе переданных токенов из предыдущего этапа. Граф состоит из узлов-символов и переходов между этими узлами. При этом, как мы все с вами знаем, пользователи допускают опечатки, пропускают буквы или даже ошибаются в раскладке клавиатуры. Так мы пробуем найти в нашем словаре последовательность символов, которая совпадает с очередным токеном из запроса. В ход идут различные преобразования цепочки символов: вставки, замены, дописывание символов и тому подобное. Поэтому при обходе словаря мы применяем некоторые манипуляции с тем, чтобы учесть возможный человеческий фактор или попробовать угадать, что человек набирает прямо сейчас.

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

Так для токенов найдём словоформы:

  • 13 форм для «поесть»: «поест», «поесть», «paese», «payot», …
  • 3 формы для «на»: «na», «nu», «на»
  • 48 форм для «курской»: «курской», «курская», «курски», «курское», «курако», …

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

Так для токенов будут созданы термины:

  • «поесть»: «поедим», «поели», «поем», «поест», «поесть»
  • «на»: «на», «na», «nu»
  • «курской»: «курская», «курский», «курского», «курское», «курской»

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

Этап 3. Поиск вхождений в данные

Вход: набор терминов для каждой части запроса

  • «поесть»: «поедим», «поели», «поем», «поест», «поесть»
  • «на»: «на», «na», «nu»
  • «курской»: «курская», «курский», «курского», «курское», «курской»

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

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

  • «поесть»: 18 вхождений
  • «на»: 4304 вхождений
  • «курской»: 79 вхождений

Очевидно, что предлог «на» встречается очень много раз и потому попадает в множество заголовков документов — «кофе на вынос», «поиграть на приставке», «постановка на учёт машины». «Поесть» и «курской» тоже используются неоднократно. Второе слово с его терминами встречается в наших данных значительно чаще, чем первое.

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

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

Этап 4. Сердце поиска

Вход: список попаданий

  • «поесть»: 18 вхождений
  • «на»: 4304 вхождений
  • «курской»: 79 вхождений

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

Поэтому правильнее будет отобразить входные данные следующим образом:
Вход: контейнер узлов-документов

  • документ1:
  • документ2: { попадания, … }
  • документ3: { попадания, … }
  • документ4: { попадания, … }
  • ...

Первым делом поиск начинает обход дерева документов и каждый узел отдаёт в анализатор, который оценивает пригоден ли документ из этого узла быть результатом для попадания в выдачу. Чтобы понимать, с какими объёмами приходится работать анализатору, скажу, что на старте контейнер содержит более 3000 узлов! А ведь узлы могут добавляться в процессе обхода, поэтому реально обрабатывается ещё больше. Не будет преувеличением сказать, что анализ — самая затратная часть поиска и в то же время одна из самых сложных и больших функций проекта. И тем не менее она выполняется крайне быстро даже на мобильных устройствах.

Этап 5. Анализ

Вход: Узел документ: { попадания, … }

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

На основе лучшей цепочки и будет проведена оценка полезности тайтла. Для каждого из тайтлов отбираются лучшие из цепочки попаданий — лучшие по длине и словарной оценке, составленной из похожести попаданий. Грубо говоря, чем чаще слово встречается в документе, тем оно важнее (TF-IDF). Чтобы определить полезность цепочки, мы в том числе используем механизм на основе частотности слов в документах. Тайтл также может быть полезным, если его попадания полностью покрывают слова из заголовка документа. Так, если цепочка содержит попадание в важное слово из заголовка документа без сильных морфологических отличий, например отличное число или род — считаем тайтл полезным.

Эта маска даёт нам представление о токенах запроса, покрываемых анализируемым узлом. С помощью полезности все тайтлы образуют маску полезности для узла. И с её помощью мы во многом определяем, следует ли дальше анализировать узел.

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

Этап 6. Оценка

Вход: Узел документ: { попадания, … }

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

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

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

Важно, что эти оценки из ранжированного тайтла будут участвовать в отборе лучших оценок. Оценка — структура с информацией о числе задействованных в тайтле слов из запроса и множество других факторов о том, как слово было найдено и обработано — начиная с этапа словарного поиска. Некоторые из них будут помечены как выбранные и внесут свой вклад в конечную оценку того результата, который увидит пользователь.

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

Ясность может быть хорошей, слабой и плохой. На основе информации о полезности тайтлов определяется ясность результата. Все эти данные оказывают драматическое влияние на дальнейшую судьбу результатов и порядок их выдачи. И вычисляется она с участием всех выбранных тайтлов для обрабатываемого узла.

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

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

Этап 7. Постобработка

Вход: результат, сконструированный из узла

Анализатор отсеивает множество записей из индекса, прежде чем те станут результатами. Однако в ходе анализа может быть оценено и отправлено на обработку множество потенциальных результатов. Чтобы показать пользователю только самые полезные из них в порядке релевантности, нам нужно отсечь худшие варианты, найденные анализатором.

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

В сортировке участвует множество факторов, рассчитанных и агрегированных на разных этапах поиска. Перед тем, как отдать голодному пользователю информацию о кафе, мы проводим завершающую обработку — сортируем по релевантности. Многие из них были найдены одинаковым путём, а потому имеют одинаковую оценку. И в конечном итоге поисковая выдача по запросу «поесть на Курской» составляет более 500 результатов. Они будут отсортированы по степени популярности у пользователей.

Вывод

Мы получили выдачу с множеством кафе и ресторанов и, радостные, отправляемся обедать. Все результаты мы получили за доли секунд. И при этом нам даже не нужно интернет-соединение.

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

Надеюсь, было познавательно. Сегодня же я постарался приоткрыть капот нашего поискового движка и показать, как мы помогаем пользователям находить в городе то, что им нужно, причём делать это быстро и удобно.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»