Создать поиск: руководство по разработке

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

Если вы спросите разработчика “Как мне создать поиск?” или “Как вы встроите функцию поиска в свой продукт?”, вы услышите что-то вроде: “О, мы просто запустим кластер ElasticSearch. Поисковики сейчас совсем не сложные”.

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

Зачем это читать?

Эта статья — коллекция инсайтов и ресурсов, которые помогут вам создать функцию поиска. Я расскажу о самых популярных подходах, алгоритмах, методах и инструментах, основываясь на своем опыте работы над поисковиками разного размера в Google, Airbnb и ещё нескольких стартапах. Непонимание сложности проблем поиска может привести к плохому пользовательскому опыту, напрасной трате сил и провалу продукта.

Создать поиск: немного философии

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

Поиск — это сложная проблема

Запросы могут быть самыми разными, а проблемы поисковиков сильно зависят от потребностей продукта. Например, Facebook ищет графы людей, YouTube — отдельные видео, и эти проблемы сильно отличаются от планирования авиапутешествия с Kayak.

Качество, метрики и процессы имеют большое значение

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

Сначала используйте существующие технологии

Как и во многих инженерных проблемах, не стоит изобретать колесо. При возможности используйте существующие сервисы или инструменты с открытым исходным кодом. Если существующая SaaS (например, Algolia или ElasticSearch) подходит под ваши ограничения и вы можете себе это позволить, используйте её. Это решение, вероятнее всего, будет вашим лучшим первоначальным выбором для продукта, даже если потом вам нужно будет заменить его.

При использовании готового решения знайте детали

Даже если вы используете готовое общедоступное или коммерческое решение, вы должны иметь представление о сложности проблем поиска и возможных проблемах.

Теория: проблема поиска

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

1. Размер: насколько большой у вас свод документов? Это тысячи или миллиарды документов?
2. Медиа: вы ищете текст, изображения, графические взаимоотношения или пространственные данные?
3. Контроль над сводом и качеством: источники документов находятся под вашим контролем или принадлежат сторонним лицам? Готовы ли документы к индексированию или их нужно привести в порядок?
4. Скорость индексирования: нужна ли вам индексация в реальном времени или подойдет пакетная?
5. Язык запросов: запросы структурированы или вам нужна поддержка неструктурированных запросов?
6. Структура запросов: что входит в запрос? Текст, изображения, звук, лица людей или адреса?
7. Зависимость от контекста: зависят ли результаты от личности пользователя, их истории взаимодействия с продуктом, локации, времени суток и т.д.?
8. Предложение поддержки: вам нужна поддержка неполных запросов?
9. Время ожидания: какие требования у вас есть ко времени ожидания? Это 100 миллисекунд или 100 секунд?
10. Контроль над доступом: являются ли данные полностью публичными или пользователи должны видеть только ограниченный набор документов?
11. Соответствие: существуют ли организационные ограничения?
12. Интернационализация: нужна ли вам поддержка документов с разными кодировками или символов Unicode? (Подсказка: всегда используйте UTF-8, если только вы не уверены в своих действиях на 100%). Нужна ли вам поддержка мультиязычного корпуса документов? Мультиязычных запросов?

Этот список поможет вам сделать ряд основных решений для создания индивидуальных компонентов.

Теория: процесс поиска

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

Вам нужно решить следующие проблемы:

Подборка для индекса

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

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

Структура индекса

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

• Подумайте, нужно ли вам индексирование данных в режиме реального времени. Многие компании с большими объемами документов используют пакетный подход, который затем оказывается неподходящим для продукта, в котором пользователь ожидает мгновенного результата.
• В случае текстовых документов извлечение документов включает методы обработки естественного языка, такие как стоп-списки, стемминг и NER (named entity recognition). Для изображений и видео используется компьютерное зрение и т.д.
• Кроме того, документы содержат статистическую и метаинформацию, например, ссылки на другие документы, темы, частота запроса в документе, размер документа и др. Эту информацию в дальнейшем можно использовать для кластеризации документов или ранжирования. Крупные системы могут содержать несколько индексов, например, для документов разных типов.
• Форматы индекса. Структура и разметка индекса — это сложная тема, хотя её можно оптимизировать несколькими способами. Например, существуют методы сжатия списков, можно применить mmap()-представление данных или использовать LSM-дерево для постоянно обновляемого индекса.

Анализ запроса и возврат документа

Многие популярные поисковые системы поддерживают неструктурированные запросы. Это значит, что система должна самостоятельно извлекать структуру из запроса. В случае инвертированного индекса вам нужно извлекать ключевые слова при помощи методов NLP.

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

• Повторное взвешивание терминов.
• Проверка правописания. История поисковых запросов может быть полезной в качестве словаря.
• Соотношение синонимов.
• Извлечение сущностей.
• Классификация запросов. Определите запросы конкретного типа. Например, Google определяет запросы, которые содержат географическую сущность, порнографический запрос или запрос о чем-то из новостей. Алгоритм возврата затем может принять решение о структуре индекса.
• Расширение на основе персонализации или локального контекста. Полезно для запросов вроде “заправки около меня”.

Ранжирование

На основе списка документов, данных и обработанного запроса создайте оптимальный порядок (рейтинг) для этих документов. Изначально многие модели ранжирования были вручную отобранными комбинациями всех сигналов документа. Наборы сигналов могли включать PageRank, данные о кликах, информацию о темах и др. Многие из этих сигналов, например, PageRank, содержали параметры, которые влияли на производительность сигнала, и эти параметры должны быть также настроены вручную. Затем, по мере развития машинного обучения, основанные на сигнале дифференциальные контролируемые модели стали все популярнее. Некоторые популярные примеры: McRank и LambdaRank от Microsoft и MatrixNet от Яндекс.

В последнее время набирает популярность подход, основанный на векторном пространстве для семантического возврата и ранжирование. Идея состоит в том, чтобы изучить отдельные низкоуровневые векторные представления документа, а затем построить модель, которая представляет запросы в одном и том же векторном пространстве. Тогда возврат — это просто нахождение нескольких документов, ближайших по определенному показателю к вектору запроса. Ранжирование определяется расстоянием. Если схемы документов и запросов созданы хорошо, документы выбираются не по наличию какой-то модели (например, слова), а близостью к запросу по смыслу.

Пайплайн индексирования

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

Выдача результатов

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

• Производительность: пользователи замечают, когда система тормозит. Google провел обширное исследование и заметил, что количество запросов падает на 0,6%, если задержка системы составляет 300 мс. Они рекомендуют придерживаться времени ожидания менее 200 миллисекунд.
• Кэширование результатов часто необходимо для улучшения производительности. Но здесь возникает много сложностей. При обновлении индексов или присутствии некоторых результатов в черном списке могут отображаться старые версии страниц. Очистка кэша тоже не так проста: поисковая система может не иметь достаточную пропускную способность для обслуживания поискового запроса с пустым (холодным кэшем), поэтому до получения запросов кэш нужно разогреть. В целом, кэш препятствует производительности системы.
• Доступность: часто определяется временем непрерывной работы. Когда индекс составляется, система запрашивает результаты из всех своих частей. Это значит, что если одно устройство недоступно, вся поисковая система перестает работать. Чем больше машин вовлечено в составление индекса, тем выше вероятность того, что одна из них перестанет работать и приведет к падению всей системы.
• Управление множественными запросами: индексы для больших систем могут делиться на части по типу медиа или другим образом.
• Сбор результатов разных типов: например, Google отображает результаты для карт, новостей и др.

Качество, оценка и улучшение

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

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

Что такое качество? Вам нужно определить, что это в вашем случае:

• Счастье пользователя (включает UX)
• Релевантность возвращенных результатов (не включает UX)
• Удовлетворенность относительно конкурентов
• Удовлетворенность относительно предыдущей версии поисковика
• Вовлеченность пользователей

Метрики

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

• Точность и полнота измеряют, насколько точно набор документов соответствует тому, что вы ожидали увидеть.
• F-показатель — это число, которое представляет и точность, и полноту.
• Средняя точность (MAP) позволяет измерить релевантность результатов из топа рейтинга.
• Нормализованный дисконтированный кумулятивный коэффициент (nDCG) подобен MAP, но взвешивает релевантность результата по его позиции.
• Длинные и короткие клики позволяют оценить, насколько полезны результаты для реальных пользователей.

Человеческая оценка

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

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

Вот список некоторых типов человеческой оценки, которые можно применить к поисковой системе:

• Базовая пользовательская оценка: пользователь оценивает свою удовлетворенность всем опытом.
• Сравнительная оценка: сравнение с другими результатами поиска (более ранними версиями или конкурентами).
• Оценка возврата: анализ запросов и качество возврата часто оценивается при помощи созданных вручную наборов запрос-документ. Пользователь видит запрос и список возвращенных документов и отмечает, какие из них релевантны запросы, а какие нет. Из документов формируется “золотой набор”. Они невероятно полезны. При их помощи разработчик может создать автоматические регрессионные тесты возврата. Сигнал от золотых наборов также может использоваться в качестве эталоне для изменения моделей запроса.
• Оценка ранжирования: оценщики видят запрос и два документа, а затем выбирают, какой документ лучше подходит к запросу. Так создается определенный порядок для документов, который затем можно сравнить с выходными данными системы ранжирования.

Оценка наборов данных:

Задумываться о наборах данных для оценки нужно как можно раньше. Как вы будете их собирать и обновлять? Как вы внедрите их в оценку системы? Существуют ли в них встроенные предрассудки?

Эксперименты вживую

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

Время цикла оценки

Скорость совершенствования качества поиска зависит от того, насколько быстро вы завершаете цикл измерения и улучшения. Этот вопрос стоит задать себе заранее. Потребуются вам дни, часы, минуты или секунды, чтобы увидеть изменения? Проведение оценки должно быть простым для инженеров и не занимать много времени.

Создать поиск: практика

1. Как я говорил выше, если вы можете себе это позволить — купите существующую SaaS (некоторые хорошие указаны в списке ниже). Сервис подходит вам, если:

• Ваш сервис или приложение подключены к интернету.
• Поддерживает ли он всю нужную функциональность по умолчанию? Это может быть поддержка медиа, которое вы ищете, индексирование в реальном времени, гибкость запроса.
• Основываясь на размере собрания документов и ожидаемого числа запросов в секунду, подумайте, сможете ли вы платить за сервис следующие 12 месяцев?
• Может ли сервис поддерживать ожидаемый трафик с требуемым временем задержки? Если ваш сервис находится в приложении, убедитесь, что для всех ваших пользователей будет доступен достаточно быстрый доступ.

2. Если готовое решение не подходит под ваши ресурсы, вы можете использовать открытые библиотеки или инструменты. В случае приложений или сайтов я бы посоветовал ElasticSearch. Для встроенных опытов существует множество других инструментов, описанных ниже.
3. Вы, вероятно, захотите сделать селекцию индекса и почистить свои документы (выделить релевантный текст из HTML-страниц) перед загрузкой в свой поисковик. Это снизит размер индекса. Если ваш корпус документов находится в одном хранилище, просто напишите для этого скрипт. Если нет, используйте Spark.

SaaS

Algolia — SaaS, которая индексирует сайт клиента и предоставляет API для поиска по страницам сайта. У них также есть API для загрузки ваших документов и поддержки зависимых от контекста запросов.

Различные поставщики ElasticSearch: AWS (ElasticSearch Cloud), elastic.co и Qbox.

Azure Search — SaaS-решение от Microsoft. Доступное через REST API, оно может масштабироваться до миллиардов документов. Имеет интерфейс запросов Lucene, чтобы упростить миграцию с решений, основанных на Lucene.

Swiftype  — корпоративное SaaS, которое индексирует внутренние сервисы вашей компании, например, Salesforce, G Suite, Dropbox.

Инструменты и библиотеки

• Lucene  — самая популярная библиотека, позволяющая создать поиск собственными силами. Включает анализ запросов, возврат индекса и ранжирование. Все компоненты можно заменить альтернативами.
• Solr — сервер, основанный на Lucene.Это часть экосистемы Hadoop.
• Hadoop  — самая широко используемая открытая система MapReduce, изначально созданная как индексирующий фреймворк для Solr. Он постепенно отдает лидирующие позиции Spark в области фреймворков для индексации с пакетной обработкой данных. EMR — это частное применение MapReduce на AWS.
• ElasticSearch также основан на Lucene. Он получает все больше внимания в последнее время, и не зря: он хорошо поддерживается, имеет обширный API, интегрируется с Hadoop.
• Xapian  — библиотека для C++.
• Sphinx  — полнотекстовый поисковой сервер. Язык запросов похож на MySQL.
• Nutch  может использоваться вместе с Solr.
• Lunr  — компактная библиотека для веб-приложений на клиентской стороне.
• searchkit  — UI-компоненты для ElasticSearch.
• Norch - основанная на LevelDB поисковая библиотека для Node.js.
• Whoosh  — быстрая библиотека, написанная на Python.

Наборы данных

Эти наборы позволят оценить качество запросов.

• Commoncrawl  — обновляемые данные поиска по вебу.
• Openstreetmap data dump — богатый источник данных для поисковика, связанного с геолокациями.
• Google Books N-grams может быть полезным для создания языковых моделей.
• Wikipedia dumps — классический источник для создания целого графа.
• IMDb dumps — набор данных для забавного небольшого поисковика.